글 읽기 - 시간 초과가 뜹니다.

qsccsq22 1년 전 0

어느 부분 때문에 시간 초과가 날까요 ㅠㅠ..

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, pair<int, int>> PI;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, K, a, b, cnt = 0, sum = 0;
	PI t;
	cin >> N >> K;
	vector <bool> visit(N, false);
	vector <int> d(N);
	priority_queue <PI, vector<PI>, greater<PI>> q;

	cin >> a;
	for (int i = 1; i < N; i++)
	{
		cin >> b;
		d[i] = b - a;
		q.push(make_pair(d[i], make_pair(i - 1, i)));
		a = b;
	}

	while (cnt != K)
	{
		while (visit[q.top().second.first] || visit[q.top().second.second])
			q.pop();
		t = q.top();
		q.pop();
		sum += t.first;
		cnt++;
		int l = t.second.first, r = t.second.second;
		visit[l] = visit[r] = true;
		if ((l - 1 >= 0 && r + 1 < N) && (!visit[l - 1] && !visit[r + 1]))
			q.push(make_pair(d[l] + d[r+1] - t.first, make_pair(l - 1, r + 1)));
	}
	cout << sum;

	return 0;
}

applemade 1년 전 0

input

6 3

output

TLE

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과가 뜹니다.

qsccsq22 1년 전 0

applemade 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말