Submission #1224989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224989		alicecute	Kitchen (BOI19_kitchen)	C++20	100 / 100	17 ms	1168 KiB

kitchen

/*************************************
*  Author: Alice_in_Wonderland^^ 
*************************************/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r), _l = (l); i >= _l; i--)
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
 
const int N = 300 * 300 + 5;
const int MOD = 1e9 + 7;
const int block = 470;
const int LOG = 21;
const int INF = 1e18;

template<class A, class B>
bool umin(A& var, const B& val){ return (val < var) ? (var = val, true) : false; }
template<class A, class B>
bool umax(A& var, const B& val){ return (var < val) ? (var = val, true) : false; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> int random(const int& l, const int& r) {
    return uniform_int_distribution<int>(l,r)(rng);
}

#define DBG(x) cerr << #x << " = " << x << ' ';
#define DBGn(x) cerr << #x << " = " << x << '\n';
int n , m , k;
int a[N];
int b[N];
int mn_val = INF;
int sum = 0;
int sum2 = 0;
int dp[N + 1];


void solve(void) {
    cin >> n >> m >> k;

    FOR(i , 0 , n - 1) {
       cin >> a[i];
       mn_val = min(mn_val , a[i]);
       sum += a[i];
    }

    FOR(i , 0,  m - 1) {
        cin >> b[i];
        sum2 += b[i];
    }

    if(mn_val < k){
        cout << "Impossible";
        return;
    }

    FOR(i , 0,  N - 1) dp[i] = -N;
    dp[0] = 0;

    FOR(i , 0 , m - 1){
        FOD(j , sum2 , 0){
            if(b[i] + j <= N){
                dp[b[i] + j] = max(dp[b[i] + j] , dp[j] + min(b[i] , n));
            }
        }
    }

    FOR(i , sum , N - 1){
        if(dp[i] >= n * k){
            cout << i - sum;
            return;
        }

    }
    cout << "Impossible";

}


signed main(void) {
    if (fopen("TASK.INP", "r")) {
        freopen("TASK.INP", "r", stdin);
        freopen("TASK.OUT", "w", stdout);
    } 

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCase = 1; 
    //cin >> testCase;
    FOR(i ,1 ,testCase){
        solve();
    }


    cerr << "Time elapsed: " << TIME << "s.\n";
    
    
    return 0;
}

Compilation message (stderr)

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

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