Submission #1151922

#TimeUsernameProblemLanguageResultExecution timeMemory
1151922tntKitchen (BOI19_kitchen)C++20
100 / 100
35 ms1096 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #define pb push_back #define ll long long #define sz(s) int(s.size() #define all(v) v.begin(),v.end() int mod = 1e8; const int N = 2e5; const int inf = 2e9; vector <int> dp(N,INT_MIN); signed main(){ //freopen("shuffle.in", "r", stdin); //freopen("shuffle.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,m,k; cin >> n >> m >> k; int a[n + 1],b[m + 1]; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= m; i++) cin >> b[i]; int ans = -1,sum = 0; if(m < k){ cout << "Impossible"; return 0; } int w = 300 * 300; for(int i = 1; i <= n; i++){ cin >> a[i]; sum += a[i]; if(a[i] < k){ cout << "Impossible"; return 0; } } dp[0] = 0; for(int i = 1; i <= m; i++){ for(int j = w; j >= b[i]; j--){ dp[j] = max(dp[j],dp[j - b[i]] + min(n,b[i])); } } for(int i = 1; i <= w; i++){ if(i >= sum && dp[i] >= n * k){ ans = i - sum; break; } } if(ans == -1) cout << "Impossible"; else cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...