Submission #602617

#TimeUsernameProblemLanguageResultExecution timeMemory
602617nguyentuKitchen (BOI19_kitchen)C++14
31 / 100
1090 ms6140 KiB
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; #define ii pair<int , int> #define iv pair<ii , ii> #define iii pair<int , ii> #define fi first #define se second #define int long long const int inf = 1e18 + 7; const int MAX_N = 3e2 + 7; const int MOD = 1e9 + 7; const int MAX_V = 300 * 301; int n , m , K; bitset<MAX_V> f[2][301]; bitset<MAX_V> g; bitset<MAX_V> dp; int a[MAX_N]; int b[MAX_N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> K; int W = 0 , w = 0; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; if (a[i] < K) { cout << "Impossible"; return 0; } W += a[i]; } vector<int> c , d; for (int i = 1 ; i <= m ; i++) { cin >> b[i]; if (b[i] >= K) c.push_back(b[i]); else d.push_back(b[i]); w += b[i]; } if (W > w || K > m) { cout << "Impossible"; return 0; } int l1 = c.size(); int l2 = d.size(); f[0][0] = 1; for (int i = 0 ; i < l1; i++) { int now = i & 1; int nxt = now ^ 1; f[now][0][0] = 1; for (int j = 0 ; j < l1 ; j++) { f[nxt][j + 1] = f[now][j + 1] | ((f[now][j] << c[i])); } for (int j = 0 ; j < l1 ; j++) { f[now][j] = f[nxt][j]; } } g[0] = 1; for (int i = 0 ; i < l2 ; i++) { g = g | (g << d[i]); } for (int i = K ; i <= m ; i++) { dp = dp | f[l1 & 1][i]; } //cout << dp[231]; // for (int i = 50 ; i <= 100 ; i++) { // cout << dp[i] << " "; // } //cerr << w << " " << W; int ans = inf; for (int i = 0 ; i <= w ; i++) { for (int j = 0 ; j <= w ; j++) { if ((i + j) >= W && g[j] && dp[i]) { ans = min(ans , (i + j) - W); } } } if (ans == inf) cout << "Impossible"; else cout << ans; return 0; }
#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...