Submission #1004339

#TimeUsernameProblemLanguageResultExecution timeMemory
1004339HasanV11010238Kitchen (BOI19_kitchen)C++17
9 / 100
1 ms860 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define INF 1000000000 int main(){ ll n, m, k, su = 0, bsu = 0; cin>>n>>m>>k; bool ca = 0; if (m < k){ ca = 1; } vector<ll> a(n + 1), b(m + 1); for (int i = 0; i< n; i++){ cin>>a[i + 1]; su += a[i + 1]; if (a[i + 1] < k){ ca = 1; } } for (int i = 0; i < m; i++){ cin>>b[i + 1]; bsu += b[i + 1]; } if (ca || bsu < su){ cout<<"Impossible"; return 0; } ll ans = INF; if (m == 1){ ans = b[1] - su; } else if (m == 2){ if (k == 1 && max(b[1], b[2]) >= su){ if (b[1] >= su){ ans = min(ans, b[1] - su); } if (b[2] >= su){ ans = min(ans, b[2] - su); } } else{ ans = bsu - su; } } else{ vector<vector<ll>> dp(m + 1, vector<ll>(m + 1, 0)); for (int i = 1; i <= m; i++){ for (int j = 1; j <= i; j++){ ll va1 = dp[i - 1][j - 1] + b[j], va2 = dp[i - 1][j]; if (va1 > va2){ swap(va1, va2); } if (dp[i][j] < su){ dp[i][j] = max(dp[i][j], va2); } else if (dp[i][j] >= su && va1 >= su){ dp[i][j] = min(dp[i][j], va1); } else if (dp[i][j] >= su && va2 >= su){ dp[i][j] = min(dp[i][j], va2); } } } ll ans = INF; for (int i = 1; i <= m; i++){ if (dp[m][i] >= su) ans = min(ans, dp[m][i] - su); } } cout<<ans; }
#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...