Submission #688491

#TimeUsernameProblemLanguageResultExecution timeMemory
688491stanislavpolynKitchen (BOI19_kitchen)C++17
100 / 100
21 ms724 KiB
#include <bits/stdc++.h> #define fr(i, a, b) for (int i = (a); i <= (b); ++i) #define rf(i, a, b) for (int i = (a); i >= (b); --i) #define fe(x, y) for (auto& x : y) #define fi first #define se second #define pb push_back #define mp make_pair #define mt make_tuple #define all(x) (x).begin(), (x).end() #define pw(x) (1LL << (x)) #define sz(x) (int)(x).size() using namespace std; mt19937_64 rng(228); #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define fbo find_by_order #define ook order_of_key template <typename T> bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; } template <typename T> bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; } using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; template <typename T> using ve = vector<T>; const int N = 305; const int M = 305 * 305; int n, m, k, sumA; int a[N], b[N]; int dp[M]; //int ndp[M]; int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else ios::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> m >> k; fr (i, 1, n) { cin >> a[i]; if (a[i] < k) { cout << "Impossible\n"; return 0; } sumA += a[i]; } fr (i, 1, m) { cin >> b[i]; } { fr (i, 0, M - 1) { dp[i] = -1e9; } dp[0] = 0; fr (i, 1, m) { rf (sum, M - 1, b[i]) { umx(dp[sum], dp[sum - b[i]] + min(b[i], n)); } } fr (i, sumA, M - 1) { if (dp[i] >= n * k) { cout << i - sumA << "\n"; return 0; } } cout << "Impossible\n"; } // int best = 2e9; // fr (mask, 0, pw(m) - 1) { // int sum = 0; // int sum2 = 0; // fr (i, 1, m) { // if (mask & pw(i - 1)) { // sum += b[i]; // sum2 += min(n, b[i]); // } // } // // if (sum >= sumA && sum2 >= n * k) { // umn(best, sum - sumA); // } // } // // if (best == 2e9) { // cout << "Impossible\n"; // } else { // cout << best << "\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...