oj.uz

Submission #862416

# Submission time Handle Problem Language Result Execution time Memory
862416 2023-10-18T08:07:18 Z iskhakkutbilim Kitchen (BOI19_kitchen) C++17
29 / 100
 27 ms 1272 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()

const int mod = 1e17;
const int N = 300;
int can[300 * 300 + 10];

int goal(vector<int> &srt, int k){
	int cnt = 0;
	while(true){
		sort(srt.rbegin(), srt.rend());
		if(srt[k-1] <= 0){
			break;
		}
		int mn = srt[k-1];
		for(int i = 0;i < k; i++){
			srt[i]-= mn;
		}
		cnt+= mn;
	}
	return cnt;
}

main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   int n, m, k; 
	vector<int> a, b;
	cin >> n >> m >> k;
	a.resize(n);
	for(auto &e : a) cin >> e;
	b.resize(m);
	for(auto &e : b) cin >> e;
	int ans = mod;
	if(k > m or *min_element(all(a)) < k){
		cout << "Impossible";
		return 0;
	}
	int sumX = accumulate(all(a), 0LL);
//	if(sumX > accumulate(all(b), 0LL)){
//		cout << "Impossible";
//		return 0;
//	}
	vector<int> B = b;
	if(goal(B, k) < n * k){
		cout << "Impossible";
		return 0;
	}

	for(int i = N*N; i >= 0; i--) can[i] = INT_MIN;
		can[0] = 0;
	for(int x : b){
		for(int i = N*N; i - x >= 0; i--){
			if(can[i-x] >= 0)
			can[i] = max(can[i], can[i-x] + min(x, n));
		}
	}
	
	
	for(int i = sumX; i <= N*N; i++){
		if(can[i] >= n * k){
			cout << i-sumX;
			return 0;
		}
	}
//	cout << 't';
//	if(k == 1 && m > 15){
//		can[0] = 1;
//		for(int x : b){
//			for(int i = N*N; i - x >= 0; i--){
//				can[i]|= can[i-x];
//			}
//		}
//		int sumX = accumulate(all(a), 0LL);
//		if(goal(b, k) < n){
//			cout << "Impossible";
//			return 0;
//		}
//		for(int i = sumX; i <= N*N; i++){
//			if(can[i]){
//				cout << i-sumX;
//				return 0;
//			}
//		}
//		cout << "Impossible";
//		return 0;
//	}
	cout << "Impossible";
	return 0;
}

Compilation message

kitchen.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~
kitchen.cpp: In function 'int main()':
kitchen.cpp:39:6: warning: unused variable 'ans' [-Wunused-variable]
   39 |  int ans = mod;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1272 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1272 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1116 KB Output is correct
2 Correct 23 ms 1168 KB Output is correct
3 Correct 23 ms 1172 KB Output is correct
4 Correct 27 ms 1116 KB Output is correct
5 Correct 22 ms 1172 KB Output is correct
6 Correct 14 ms 1116 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1272 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -