Submission #862347

#TimeUsernameProblemLanguageResultExecution timeMemory
862347maks007Kitchen (BOI19_kitchen)C++14
31 / 100
7 ms624 KiB
// Bismi Allah #include "bits/stdc++.h" using namespace std; #define int long long 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(5001, 0); dp[0] = 1; for(auto j : chef) { for(int i = 5000; 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; } 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; }

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:33: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]
   33 |   for(int i = 0; i < dp.size(); i ++) {
      |                  ~~^~~~~~~~~~~
kitchen.cpp:54: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]
   54 |   for(int i = 0; i < cook.size(); i ++) {
      |                  ~~^~~~~~~~~~~~~
kitchen.cpp:11:24: warning: unused variable 'mealCopy' [-Wunused-variable]
   11 |  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...