Submission #643926

#	Time	Username	Problem	Language	Result	Execution time	Memory
643926		mychecksedad	Kitchen (BOI19_kitchen)	C++17	30 / 100	83 ms	111968 KiB

kitchen

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 305, F = 2147483646, K = 20;



int n, m, k, m1, m2, a[N], b[N], b1[N], b2[N], S = 0, mn, mx[M*M], suf[M][M*M];
bool dp[M*M], p[M*M];
void solve(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i]; 
        S += a[i];
    }
    m1 = m2 = 0;
    for(int i = 1; i <= m; ++i){
        int x; cin >> x;
        if(x < n) b1[++m1] = x;
        else b2[++m2] = x;
        b[i] = x;
    }

    mn = *min_element(a + 1, a + 1 + n);
    if(mn < k || m < k){
        cout << "Impossible";
        return;
    }


    for(int i = 0; i < M * M; ++i) p[i] = dp[i] = mx[i] = 0;
    for(int i = 0; i < M * M; ++i) for(int j = 0; j < M; ++j) suf[j][i] = -1;


    p[0] = dp[0]     = 1;

    for(int i = 1; i <= m1; ++i){
        for(int s = M * M - 1; s >= b1[i]; --s){
            p[s] |= p[s - b1[i]];
        }
    }

    for(int i = 1; i <= m2; ++i){
        for(int s = M * M - 1; s >= b2[i]; --s){
            dp[s] |= dp[s - b2[i]];
            if(dp[s - b2[i]]){
                mx[s] = max(mx[s], mx[s - b2[i]] + 1);
            }
        }
    }

    for(int i = m2; i >= 0; --i){
        for(int s = M*M - 2; s >= 0; --s){
            if(mx[s] >= i){
                suf[i][s] = s;
            }else{
                suf[i][s] = suf[i][s + 1];
            }
        } 
    }
    // for(int i = 0; i <= m2; ++i){
    //     for(int j = 0; j < 20; ++j){
    //         cout << suf[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    bool ok = 0;
    int ans = MOD;
    int po = 0;

    S -= k * n;

    

    for(int s = 0; s < M*M; ++s){
        if(!p[s]) continue;
        int sum = s - min(s/n, k) * n;
        int rem = max(k - s/n, 0);
        int req = rem * n + max(S - sum, 0);
        if(rem <= m2 && suf[rem][req] != -1){
            ok = 1;
            ans = min(ans, suf[rem][req] - rem*n + sum - S);
        }
    }


    if(ok)
        cout << ans;
    else
        cout << "Impossible";

    
}



int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message (stderr)

kitchen.cpp: In function 'void solve()':
kitchen.cpp:40:57: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   40 |     for(int i = 0; i < M * M; ++i) p[i] = dp[i] = mx[i] = 0;
      |                                                   ~~~~~~^~~
kitchen.cpp:79:9: warning: unused variable 'po' [-Wunused-variable]
   79 |     int po = 0;
      |         ^~
kitchen.cpp: In function 'int main()':
kitchen.cpp:109:16: warning: unused variable 'aa' [-Wunused-variable]
  109 |     int T = 1, aa;
      |                ^~

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