글 읽기 - 틀리는이유를 모르겠습니다

njchung99 6년 전 0

그리디로 도착하는 마을을 기준으로 정렬을 하고 그 다음에 그 마을 사이에 박스를 몇개 가져갈 수 있는 지를 확인하고 택배를 가져가도록 했는데 정올 사이트에 내보니까 답이 나와야되는 것보다 더작은 값이 나오던데

코드를 잘못 짠건지 아니면 방식이 잘못된것인지를 모르겠습니다. 방식이 잘못됬으면 왜 잘못된건지도...모르겟어서 최적인거같은데 더작게 나오는 이유를 모르겠습니다.

#include<cstdio>
#include<algorithm>
using namespace std;
pair<pair<int, int>, int> a[10010];
int ch[2010];
int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < k; i++)
	{
		scanf("%d%d%d", &a[i].first.second, &a[i].first.first, &a[i].second);
		if (a[i].second > m)
			a[i].second = m;
	}
	sort(a, a + k);
	int dap = 0;
	for (int i = 0; i < k; i++)
	{
		int sum = 0;
		for (int y = a[i].first.second+1; y <= a[i].first.first; y++)
		{
			sum += ch[y];
		}
		if (sum>= m)continue;
		if (sum + a[i].second >= m) {
			ch[a[i].first.first] = m - sum + ch[a[i].first.first];
			dap = dap+m - sum;
		}
		else {
			ch[a[i].first.first] = ch[a[i].first.first] + a[i].second;
			dap += a[i].second;
		}
	}
	printf("%d", dap);
}

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

문제

문제

출처

ICPC

틀리는이유를 모르겠습니다

njchung99 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말