Submission #920613

#	Time	Username	Problem	Language	Result	Execution time	Memory
920613		rainboy	요리 강좌 (KOI17_cook)	C++17	0 / 100	2 ms	10844 KiB

cook

#include <stdio.h>

#define N	3000
#define K	3000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int main() {
	static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
	int n, k, l, r, t, h, h1, h2, h3, h_, i, ans;

	scanf("%d%d%d%d%d", &k, &n, &l, &r, &t);
	for (h = 0; h < k; h++)
		for (i = 1; i <= n; i++)
			scanf("%d", &ss[h][i]), ss[h][i] += ss[h][i - 1];
	for (h = 0; h < k; h++)
		scanf("%d", &pp[h]), pp[h]--;
	for (i = 0; i <= n; i++) {
		h1 = h2 = h3 = -1;
		for (h = 0; h < k; h++) {
			dp[h][i] = (i == 0 ? -t : (cnt[h] ? dq[h][qu[h][head[h]]] : INF));
			if (dp[h][i] != INF) {
				dp[h][i] += ss[h][i];
				if (h1 == -1 || dp[h1][i] > dp[h][i])
					h3 = h2, h2 = h1, h1 = h;
				else if (h2 == -1 || dp[h2][i] > dp[h][i])
					h3 = h2, h2 = h;
				else if (h3 == -1 || dp[h3][i] > dp[h][i])
					h3 = h;
			}
		}
		for (h = 0; h < k; h++) {
			if (h1 != h && h1 != pp[h])
				h_ = h1;
			else if (h2 != h && h2 != pp[h])
				h_ = h2;
			else
				h_ = h3;
			dq[h][i] = h_ == -1 ? INF : dp[h_][i] - ss[h][i] + t;
		}
		for (h = 0; h < k; h++) {
			if (i >= l - 1 && dq[h][i - l + 1] != INF) {
				while (cnt[h] && dq[h][qu[h][head[h] + cnt[h] - 1]] >= dq[h][i - l + 1])
					cnt[h]--;
				qu[h][head[h] + cnt[h]++] = i - l + 1;
			}
			if (cnt[h] && qu[h][head[h]] == i - r)
				head[h]++, cnt[h]--;
		}
	}
	ans = INF;
	for (h = 0; h < k; h++)
		ans = min(ans, dp[h][n]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

cook.cpp: In function 'int main()':
cook.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d%d%d%d", &k, &n, &l, &r, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:16:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |    scanf("%d", &ss[h][i]), ss[h][i] += ss[h][i - 1];
      |    ~~~~~^~~~~~~~~~~~~~~~~
cook.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &pp[h]), pp[h]--;
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 44