Submission #1280414

#TimeUsernameProblemLanguageResultExecution timeMemory
1280414Bui_Quoc_CuongKitchen (BOI19_kitchen)C++20
100 / 100
92 ms111476 KiB
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for (int i = a; i >= (int)b; i--)
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define MASK(a) (1LL<<(a))
#define BIT(mask, a) ((mask >> (a))&1)
template <class A, class B> bool minimize (A &a, const B b) {if (a > b) {a = b;return true;} return false;}
template <class A, class B> bool maximize (A &a, const B b) {if (a < b) {a = b;return true;} return false;}
const int MAXN = 300 + 5;

int n, m, k;
int a[MAXN], b[MAXN];
int dp[MAXN][MAXN * MAXN];

void init (void) {
    cin >> n >> m >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, m) cin >> b[i];
}

void process (void) {
    if (m < k || *min_element(a + 1, a + 1 + n) < k) {
        cout << "Impossible";
        return;
    }
    int allTime = 0;
    FOR(i, 1, n) allTime+= a[i];
    int allTimeB = 0;
    FOR(i, 1, m) allTimeB+= b[i];
    memset(dp, - 0x3f, sizeof dp);
    dp[0][0] = 0;
    FOR(i, 1, m) FOR(j, 0, allTimeB) {
        maximize (dp[i][j], dp[i - 1][j]);
        if (j >= b[i]) {
            maximize (dp[i][j], dp[i - 1][j - b[i]] + min(b[i], n));
        }
    }
    int ans = 2e9;
    FOR(j, allTime, allTimeB) if (dp[m][j] >= n * k) {
        ans = min (ans, j - allTime);
    }
    if (ans >= 2e9) {
        cout << "Impossible";
    } else {
        cout << ans;
    }
}

int main (void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "boi19_kitchen"
    if (fopen(kieuoanh".inp", "r")) {
        freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
    }
    init();
    process();
    return 0;
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:59:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...