oj.uz

Submission #205719

# Submission time Handle Problem Language Result Execution time Memory
205719 2020-02-29T15:22:52 Z ics0503 Kitchen (BOI19_kitchen) C++17
0 / 100
 119 ms 26848 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

short D[313][91919];
vector<int>Q[313];
vector<int>V[91919];
int A[313], B[313], S[313], tmp[313];
bool simul(vector<int>B, int n, int k) {
	priority_queue<int>H;
	for (int v : B)H.push(-v);
	for (int i = n; i >= 1; i--) {
		// int g = A[i] - k;
		for (int j = 0; j < k; j++) {
			tmp[j] = -H.top() - 1; H.pop();
			if (tmp[j] < 0)return false;
		}
		for (int j = 0; j < k; j++)H.push(-tmp[j]);
	}
	return true;
}
bool sort_a(int a, int b) {
	return a > b;
}
int main() {
	int n, m, k, i, j, aSum = 0; scanf("%d%d%d", &n, &m, &k);
	for (i = 1; i <= n; i++) {
		scanf("%d", &A[i]), aSum += A[i];
		if (A[i] < k) {
			puts("Impossible");
			return 0;
		}
	}
	for (i = 1; i <= m; i++) scanf("%d", &B[i]);
	sort(A + 1, A + 1 + n);
	sort(B + 1, B + 1 + m, sort_a);
	for (i = 1; i <= m; i++)S[i] = S[i - 1] + B[i];
	D[0][0] = 0;
	for (i = 1; i <= S[1]; i++)D[0][i] = -1;
	for (i = 1; i <= m; i++) {
		for (j = 0; j <= S[i]; j++) {
			D[i][j] = D[i - 1][j];
			if (B[i] <= j && D[i - 1][j - B[i]] != -1) {
				if (D[i][j] == -1 || D[i][j] < D[i-1][j - B[i]] + 1) {
					D[i][j] = D[i - 1][j - B[i]] + 1;
				}
			}
		}
		for (j = S[i] + 1; j < S[i + 1]; j++)D[i][j] = -1;
	}
	int ans = -1;
	for (i = aSum; i <= S[m]; i++) for (int v = 1; v <= m; v++) if (D[v][i] >= k && V[i].empty()) {
		Q[D[v][i]].push_back(i);
		int now = i;
		for (j = v; j > 0; j--) {
			if (D[j][now] == D[j - 1][now - B[j]] + 1) {
				V[i].push_back(B[j]);
				now -= B[j];
			}
		}
		if (simul(V[i], n, k)) {
			printf("%d\n", i - aSum);
			return 0;
		}
	}
	printf("Impossible");
	return 0;
}

Compilation message

kitchen.cpp: In function 'int main()':
kitchen.cpp:53:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = -1;
      ^~~
kitchen.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, k, i, j, aSum = 0; scanf("%d%d%d", &n, &m, &k);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:30:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]), aSum += A[i];
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
kitchen.cpp:36:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= m; i++) scanf("%d", &B[i]);
                           ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 6 ms 2552 KB Output is correct
3 Correct 6 ms 2424 KB Output is correct
4 Correct 6 ms 2552 KB Output is correct
5 Incorrect 7 ms 2424 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 6 ms 2552 KB Output is correct
3 Correct 6 ms 2424 KB Output is correct
4 Correct 6 ms 2552 KB Output is correct
5 Incorrect 7 ms 2424 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 26848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Incorrect 8 ms 2684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 6 ms 2552 KB Output is correct
3 Correct 6 ms 2424 KB Output is correct
4 Correct 6 ms 2552 KB Output is correct
5 Incorrect 7 ms 2424 KB Output isn't correct
6 Halted 0 ms 0 KB -