Submission #862358

#TimeUsernameProblemLanguageResultExecution timeMemory
862358maks007Kitchen (BOI19_kitchen)C++14
50 / 100
190 ms8536 KiB
// Bismi Allah #include "bits/stdc++.h" using namespace std; #define int long long int dp[1700][50][50]; signed main () { int n, m, k; cin >> n >> m >> k; int meal[n], chef[m], mealCopy[n]; for(int i = 0; i < n; i ++) cin >> meal[i]; for(int i = 0; i < m; i ++) cin >> chef[i]; if(*min_element(meal, meal + n) < k) { cout << "Impossible"; return 0; } if(m < k) { cout << "Impossible"; return 0; } if(k == 1) { int szdp = accumulate(meal, meal + n, 0LL); vector <int> dp((int)1e6, 0); dp[0] = 1; for(auto j : chef) { for(int i = (int)1e6-1; i >= 0; i --) { if(!dp[i]) continue; dp[i+j] = 1; } } int mn = 1e9; for(int i = 0; i < dp.size(); i ++) { if(dp[i] == 0) continue; if(i < szdp) continue; mn = min(mn, i-szdp); } if(mn == 1e9) cout << "Impossible\n"; else cout << mn << "\n"; return 0; } if(*max_element(meal, meal + n) > 40){ int ans = 1e9; for(int mask = 0; mask < (1 << m); mask ++) { if(__builtin_popcount(mask) < k) continue; vector <int> cook; for(int i = 0; i < m; i ++) { if(mask & (1 << i)) { cook.push_back(chef[i]); } } if(accumulate(cook.begin(), cook.end(), 0LL) < accumulate(meal, meal + n, 0LL)) continue; int cnt = 0, other = 0; for(int i = 0; i < cook.size(); i ++) { if(cook[i] >= n) cnt ++; else { other += cook[i]; } } cnt += (other / n); if(cnt >= k) ans = min(ans, accumulate(cook.begin(), cook.end(), 0LL) - accumulate(meal, meal + n, 0LL)); } if(ans == 1e9) cout << "Impossible"; else cout << ans; return 0; } int szdp = accumulate(meal, meal + n, 0); dp[0][0][0] = 1; for(auto coin : chef) { for(int i = 1699; i >= 0; i --) { for(int full = 0; full < 41; full ++) { for(int rezerv = 0; rezerv < 41; rezerv ++) { if(dp[i][full][rezerv]) { if(coin >= n) dp[i+coin][full+1][rezerv] = 1; else { dp[i+coin][full+(rezerv + coin)/n][(rezerv + coin) % n] = 1; } } } } } } int ans = 1e9; for(int i = szdp; i < 1700; i ++) { for(int full = k; full < 50; full ++) { for(int rezerv = 0; rezerv < 50; rezerv ++) { if(dp[i][full][rezerv]) ans = min(ans, i-szdp); } } } if(ans == 1e9) cout << "Impossible"; else cout << ans; return 0; }

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:35:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i = 0; i < dp.size(); i ++) {
      |                  ~~^~~~~~~~~~~
kitchen.cpp:57:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for(int i = 0; i < cook.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~
kitchen.cpp:13:24: warning: unused variable 'mealCopy' [-Wunused-variable]
   13 |  int meal[n], chef[m], mealCopy[n];
      |                        ^~~~~~~~
#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...