Submission #920643

#	Time	Username	Problem	Language	Result	Execution time	Memory
920643		rainboy	요리 강좌 (KOI17_cook)	C++17	100 / 100	277 ms	156572 KiB

cook

/* https://oj.uz/submission/366848 (leinad2) */
/* used solution to find bugs */
#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], dq[K][N], qu[K][N], 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]--;
	ans = INF;
	for (i = 0; i < n; i++) {
		h1 = h2 = h3 = -1;
		for (h = 0; h < k; h++) {
			if (i >= l && dq[h][i - l] != INF) {
				while (cnt[h] && dq[h][qu[h][head[h] + cnt[h] - 1]] >= dq[h][i - l])
					cnt[h]--;
				qu[h][head[h] + cnt[h]++] = i - l;
			}
			if (cnt[h] && qu[h][head[h]] == i - r - 1)
				head[h]++, cnt[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;
			if (n - i <= r && dq[h][i] != INF)
				ans = min(ans, dq[h][i] + ss[h][n]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

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