제출 #126113

#제출 시각아이디문제언어결과실행 시간메모리
126113mechfrog88Kitchen (BOI19_kitchen)C++14
0 / 100
1071 ms7076 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("unroll-loops,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; ll n,m,k; ll ans = LLONG_MAX; vector <ll> chef; vector <ll> arr; void func(vector <ll> temp,ll index){ if (index == m && temp.size() >= k){ bool ok = true; ll left = 0; ll c = 0; while (c < arr.size() && ok){ sort(temp.rbegin(),temp.rend()); ll count = 0; for (int z=0;count<k;z++){ while (temp[z] == 0 && z < temp.size()){ z++; } if (z == temp.size()){ ok = false; break; } count++; temp[z]--; } if (arr[c] < k){ ok = false; break; } left += arr[c]-k; c++; } ll s = 0; for (int z=0;z<temp.size();z++){ s += temp[z]; } if (s >= left && ok) ans = min(ans,s-left); return; } if (index == m) return; func(temp,index+1); temp.push_back(chef[index]); func(temp,index+1); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; arr.resize(n); ll s = 0; for (int z=0;z<n;z++){ cin >> arr[z]; s += arr[z]; } chef.resize(m); for (int z=0;z<m;z++){ cin >> chef[z]; } if (k == 1){ bitset<90001> dp[n]; vector <bool> ok(90001,false); for (int z=0;z<n;z++){ dp[z][0] = true; } dp[0][chef[0]] = true; for (int z=1;z<n;z++){ for (int x=0;x<=90000;x++){ if (dp[z-1][x] && x+chef[z] <= 90000) { dp[z][x+chef[z]] = true; ok[x+chef[z]] = true; } } } ll ans = -1; ll c = 0; for (int z=s;z<=90000;z++){ if (ok[z]) { ans = z; break; } c++; } if (ans == -1) cout << "Impossible" << endl; else cout << ans-s << endl; return 0; } vector <ll> temp; func(temp,0); if (ans == LLONG_MAX){ cout << "Impossible" << endl; } else { cout << ans << endl; } }

컴파일 시 표준 에러 (stderr) 메시지

kitchen.cpp: In function 'void func(std::vector<long long int>, ll)':
kitchen.cpp:22:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (index == m && temp.size() >= k){
                    ~~~~~~~~~~~~^~~~
kitchen.cpp:26:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (c < arr.size() && ok){
          ~~^~~~~~~~~~~~
kitchen.cpp:30:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (temp[z] == 0 && z < temp.size()){
                            ~~^~~~~~~~~~~~~
kitchen.cpp:33:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (z == temp.size()){
         ~~^~~~~~~~~~~~~~
kitchen.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int z=0;z<temp.size();z++){
                ~^~~~~~~~~~~~
#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...