Submission #332841

#TimeUsernameProblemLanguageResultExecution timeMemory
332841sinamhdvKitchen (BOI19_kitchen)C++11
100 / 100
96 ms100588 KiB
// https://oj.uz/problem/view/BOI19_kitchen // n3 solution #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 1000 * 1000 * 1000; const ll LINF = (ll)INF * INF; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod) #define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod) #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 320 int asum, bsum; int dp[MAXN][MAXN * MAXN]; int a[MAXN], b[MAXN]; int n, m, k; int32_t main(void) { fast_io; cin >> n >> m >> k; FOR(i, 1, n + 1) { cin >> a[i]; if (a[i] < k) { cout << "Impossible\n"; return 0; } asum += a[i]; } FOR(i, 1, m + 1) { cin >> b[i]; bsum += b[i]; } fill(dp[0], dp[0] + bsum + 10, -INF); dp[0][0] = 0; FOR(i, 1, m + 1) { FOR(j, 0, bsum + 1) { dp[i][j] = dp[i - 1][j]; if (j >= b[i]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + min(b[i], n)); } } } FOR(i, asum, bsum + 1) { if (dp[m][i] >= n * k) { cout << i - asum << endl; return 0; } } cout << "Impossible\n"; return 0; }
#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...