oj.uz

Submission #423301

# Submission time Handle Problem Language Result Execution time Memory
423301 2021-06-10T23:12:48 Z abdzag Kitchen (BOI19_kitchen) C++17
31 / 100
 302 ms 262148 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 1e15;

using namespace std;
int main() {
	cin.sync_with_stdio(false);
	ll n, m, k;
	cin >> n >> m >> k;
	vector<ll> v(n);
	vector<ll> v2(m);
	rep(i, 0, n) {
		cin >> v[i];
		if (v[i] < k) {
			cout << "Impossible" << endl;
			return 0;
		}
	}
	rep(i, 0, m)cin >> v2[i];
	ll sum = 0;
	rep(i, 0, n)sum += v[i];
	vector < pair < priority_queue<ll>,ll>> dp0;
	priority_queue<ll> definer;
	dp0.push_back(make_pair(definer, 0));
	vector < pair < priority_queue<ll>, ll>> dp=dp0;
	rep(i, 0, m) {
		trav(a, dp0) {
			dp.push_back(a);
			dp.back().first.push(-v2[i]);
			dp.back().second+=v2[i];
		}
		dp0 = dp;
	}
	ll ans = inf;
	trav(a, dp) {
		if (a.first.size() >= k) {
			ll cur = 0;
			while (1) {
				if (a.first.size() < k) {
					break;
				}
				cur += -a.first.top();
				a.first.pop();
				if (cur >= n)break;
			}
			if (a.second >= sum&&cur>=n) {
				ans = min(a.second, ans);
			}
		}
	}
	if (ans == inf)cout << "Impossible" << endl;
	else cout << ans - sum << endl;
	return 0;
}

Compilation message

kitchen.cpp: In function 'int main()':
kitchen.cpp:46:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   46 |   if (a.first.size() >= k) {
      |       ~~~~~~~~~~~~~~~^~~~
kitchen.cpp:49:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   49 |     if (a.first.size() < k) {
      |         ~~~~~~~~~~~~~~~^~~

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 13 ms 10744 KB Output is correct
10 Correct 14 ms 10768 KB Output is correct
11 Correct 12 ms 10744 KB Output is correct
12 Correct 14 ms 10720 KB Output is correct
13 Correct 13 ms 10692 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 295 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 302 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 13 ms 10744 KB Output is correct
10 Correct 14 ms 10768 KB Output is correct
11 Correct 12 ms 10744 KB Output is correct
12 Correct 14 ms 10720 KB Output is correct
13 Correct 13 ms 10692 KB Output is correct
14 Runtime error 295 ms 262148 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -