Submission #651026

#TimeUsernameProblemLanguageResultExecution timeMemory
651026dooompyKitchen (BOI19_kitchen)C++17
100 / 100
72 ms119708 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; int a[305], b[305]; int dp[305][100005]; // int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n, m, k; cin >> n >> m >> k; int totala = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; totala += a[i]; if (a[i] < k) { cout << "Impossible"; return 0; } } for (int i = 1; i <= m; i++) cin >> b[i]; fill(&dp[0][0], &dp[0][0] + sizeof(dp) / sizeof(dp[0][0]), -1); dp[0][0] = 0; int sum = 0; for (int i = 1; i <= m; i++) { sum += b[i]; for (int j = sum; j >= 0; j--) { if (dp[i-1][j] < 0) continue; dp[i][j] = dp[i-1][j]; dp[i][j + b[i]] = max(dp[i][j + b[i]], dp[i-1][j] + min(n, b[i])); } } for (int i = totala; i <= 100000; i++) { if (dp[m][i] >= n * k) { cout << i - totala; return 0; } } cout << "Impossible"; }
#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...