Submission #264942

#TimeUsernameProblemLanguageResultExecution timeMemory
264942HeheheKitchen (BOI19_kitchen)C++14
100 / 100
112 ms114296 KiB
#include<bits/stdc++.h> //:3 using namespace std; typedef long long ll; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<int, int> #define sz(x) (int)((x).size()) //#define int long long const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const ll inf = 2e9; const ll mod = 1e9 + 7; const int N = 3e2 + 11; const ll INF64 = 3e18 + 1; const double eps = 1e-14; const double PI = acos(-1); //ifstream in(".in"); //ofstream out(".out"); int n, m, k, a[N], b[N], dp[N][N*N], s; void solve(){ cin >> n >> m >> k; for(int i = 1; i <= n; i++){ cin >> a[i]; s += a[i]; } for(int i = 1; i <= m; i++){ cin >> b[i]; } for(int i = 1; i <= n; i++){ if(a[i] < k){ cout << "Impossible" << '\n'; return; } } for(int i = 1; i < N*N; i++)dp[0][i] = -inf; for(int i = 1; i <= m; i++){ for(int j = 0; j < N*N; j++){ dp[i][j] = dp[i - 1][j]; if(b[i] <= j){ dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + min(n, b[i])); } } } for(int i = s; i < N*N; i++){ if(dp[m][i] >= k*n){ cout << i - s << '\n'; return; } } cout << "Impossible" << '\n'; } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); //cout << setprecision(6) << fixed; int T = 1; //cin >> T; while(T--){ solve(); } }
#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...