Submission #921368

#TimeUsernameProblemLanguageResultExecution timeMemory
921368penguin133Kitchen (BOI19_kitchen)C++17
0 / 100
29 ms221008 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int memo[305][305][605], A[305], B[305], dp2[305][305], n, m, k, mx, mn = 1e9, ans = 2e9, sm; int dp(int x, int y, int cur){ if(x == m + 1){ if(cur < mx || y < k)return 2e9; return (cur >= mx ? cur * n - sm : 2e9); } if(memo[x][y][cur] != -1)return memo[x][y][cur]; if(cur >= mx){ return memo[x][y][cur] = (dp2[x][max(0, k - y)] + cur) * n - sm; } return memo[x][y][cur] = min(dp(x + 1, y, cur), dp(x + 1, y + 1, cur + B[x])); } void solve(){ cin >> n >> m >> k; for(int i = 1; i <= n; i++)cin >> A[i], mx = max(mx, A[i]), sm += A[i], mn = min(mn, A[i]); if(mn < k){ cout << "Impossible\n"; return; } for(int i = 1; i <= m; i++)cin >> B[i]; dp2[m+1][0] = 0; for(int i = 1; i <= m; i++)dp2[m+1][i] = 2e9; for(int i = m; i >= 1; i--){ for(int j = 0; j <= m; j++){ dp2[i][j] = min(dp2[i+1][j], (j ? dp2[i+1][j-1] + B[i] : (int)1e18)); } } memset(memo, -1, sizeof(memo)); int res = dp(1, k, 0); if(res > 1e9)cout << "Impossible\n"; else cout << res << '\n'; } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

Compilation message (stderr)

kitchen.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      | ^~~~
#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...