Submission #300085

#	Time	Username	Problem	Language	Result	Execution time	Memory
300085		BeanZ	Kitchen (BOI19_kitchen)	C++14	100 / 100	40 ms	1656 KiB

kitchen

// I_LOVE_LPL
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int lim = 3e2;
ll dp[N], is[N], a[N];
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.inp", "r")){
                freopen("test.inp", "r", stdin);
                freopen("test.out", "w", stdout);
        }
        ll n, m, k;
        cin >> n >> m >> k;
        ll sum = 0;
        for (int i = 1; i <= n; i++){
                cin >> a[i];
                if (a[i] < k) return cout << "Impossible", 0;
                sum = sum + a[i];
        }
        is[0] = 1;
        for (int i = 1; i <= m; i++){
                ll a;
                cin >> a;
                for (int j = lim * lim; j >= a; j--){
                        if (is[j - a]){
                                ll cost = min(a, n);
                                is[j] = 1;
                                if (dp[j] < (dp[j - a] + cost)){
                                        dp[j] = dp[j - a] + cost;
                                }
                        }
                }
        }
        for (int i = sum; i <= (lim * lim); i++){
                if (dp[i] >= (n * k)){
                        cout << i - sum;
                        return 0;
                }
        }
        cout << "Impossible";
}
/*
*/

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |                 freopen("test.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |                 freopen("test.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28