oj.uz

Submission #920634

# Submission time Handle Problem Language Result Execution time Memory
920634 2024-02-02T19:58:19 Z rainboy None (KOI17_cook) C++17
13 / 100
 1000 ms 11100 KB 
#include <assert.h>
#include <stdio.h>

#define N	3000
#define K	3000
#define INF	1000000000

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, j, 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]--;
		}
	}
		*/
	for (i = 0; i <= n; i++)
		for (h = 0; h < k; h++)
			dp[h][i] = i == 0 ? -t : INF;
	for (i = 0; i <= n; i++)
		for (h = 0; h < k; h++)
			if (dp[h][i] != INF)
				for (j = i + 1; j <= n; j++)
					for (h_ = 0; h_ < k; h_++)
						if (h != h_ && h != pp[h_] && (j == n || j - i >= l) && j - i <= r)
							dp[h_][j] = min(dp[h_][j], dp[h][i] + ss[h_][j] - ss[h_][i] + t);
	ans = INF;
	for (h = 0; h < k; h++)
		ans = min(ans, dp[h][n]);
	printf("%d\n", ans);
	return 0;
}

Compilation message

cook.cpp: In function 'int main()':
cook.cpp:11:48: warning: unused variable 'dq' [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                ^~
cook.cpp:11:62: warning: unused variable 'qu' [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                              ^~
cook.cpp:11:76: warning: unused variable 'head' [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                                            ^~~~
cook.cpp:11:85: warning: unused variable 'cnt' [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                                                     ^~~
cook.cpp:12:24: warning: unused variable 'h1' [-Wunused-variable]
   12 |  int n, k, l, r, t, h, h1, h2, h3, h_, i, j, ans;
      |                        ^~
cook.cpp:12:28: warning: unused variable 'h2' [-Wunused-variable]
   12 |  int n, k, l, r, t, h, h1, h2, h3, h_, i, j, ans;
      |                            ^~
cook.cpp:12:32: warning: unused variable 'h3' [-Wunused-variable]
   12 |  int n, k, l, r, t, h, h1, h2, h3, h_, i, j, ans;
      |                                ^~
cook.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d%d%d%d", &k, &n, &l, &r, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:17:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |    scanf("%d", &ss[h][i]), ss[h][i] += ss[h][i - 1];
      |    ~~~~~^~~~~~~~~~~~~~~~~
cook.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d", &pp[h]), pp[h]--;
      |   ~~~~~^~~~~~~~~~~~~~
cook.cpp: At global scope:
cook.cpp:11:85: warning: 'cnt' defined but not used [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                                                     ^~~
cook.cpp:11:76: warning: 'head' defined but not used [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                                            ^~~~
cook.cpp:11:62: warning: 'qu' defined but not used [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                              ^~
cook.cpp:11:48: warning: 'dq' defined but not used [-Wunused-variable]
   11 |  static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
      |                                                ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Execution timed out 1008 ms 11100 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Execution timed out 1008 ms 11100 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Execution timed out 1008 ms 11100 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Execution timed out 1008 ms 11100 KB Time limit exceeded
11 Halted 0 ms 0 KB -