Submission #465647

#TimeUsernameProblemLanguageResultExecution timeMemory
465647bonopoKitchen (BOI19_kitchen)C++14
100 / 100
42 ms716 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define pb push_back #define rc (i<<1)|1 #define lc (i<<1) #define el "\n" #define f first #define s second typedef long long ll; const int MM=1e5+5, MOD=1e9+7, LOG=19; int N, M, K, dp[MM], mn=1e9, sm; int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); cin>>N>>M>>K; for(int i=1, x; i<=N; ++i) { cin>>x, sm+=x, mn=min(mn, x); } memset(dp, -0x3f, sizeof(dp)); dp[0]=0; if(mn<K) { return cout<<"Impossible", 0; } for(int i=1, x; i<=M; ++i) { cin>>x; for(int j=MM-1; j>=x; --j) dp[j]=max(dp[j], dp[j-x]+min(x, N)); } for(int i=sm; i<MM; ++i) if(dp[i]>=N*K) { return cout<<i-sm<<el, 0; } cout<<"Impossible"<<el; } // MM
#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...