Submission #126000

#TimeUsernameProblemLanguageResultExecution timeMemory
126000miguelKitchen (BOI19_kitchen)C++14
21 / 100
20 ms1400 KiB
#pragma optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define rc(x) return cout<<x<<endl,0 #define pb push_back #define dbg(x) cout << #x << '=' << x << '\n'; #define ll long long #define sz size() #define x first #define y second #define pi pair <int, int> #define pii pair <int, pi> #define vi vector <int> #define int ll const ll mod = 1e9 + 7; int n, m, k, s; int a[301], b[301], dp[2][1000001]; int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(); cout.tie(); cin>>n>>m>>k; if(m<k) return cout<<"Impossible", 0; for(int i=1; i<=n; i++){ cin>>a[i]; s+=a[i]; if(a[i]<k) return cout<<"Impossible", 0; } for(int i=1; i<=m; i++) cin>>b[i]; dp[0][0]=0; int cur=0; for(int i=1; i<=m; i++){ for(int h=0; h<=cur; h++){ dp[1][h+b[i]]=max(dp[0][h+b[i]], dp[0][h]+min(b[i], n)); } cur+=b[i]; for(int h=0; h<=cur; h++) dp[0][h]=dp[1][h]; } int ans=1e9; //cout<<"xd"; for(int h=0; h<=cur; h++){ //cout<<h<<" "<<dp[0][h]<<endl; if(dp[0][h]>=n*k && h>=s) ans=min(h-s, ans); } if(ans==1e9) cout<<"Impossible"; else cout<<ans; }

Compilation message (stderr)

kitchen.cpp:1:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("Ofast")
#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...