Submission #643916

#	Time	Username	Problem	Language	Result	Execution time	Memory
643916		mychecksedad	Kitchen (BOI19_kitchen)	C++17	72 / 100	1091 ms	28228 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;
bool dp[M][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] = 0;
    for(int j = 0; j < M; ++j) for(int i = 0; i < M * M; ++i) dp[j][i] = 0;


    p[0] = dp[0][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 j = m2; j >= 1; --j)
            for(int s = M * M - 1; s >= b2[i]; --s){
                dp[j][s] |= dp[j - 1][s - b2[i]];
            }
    }
    bool ok = 0;
    int ans = MOD;
    int po = 0;

    S -= k * n;

    

    for(int i = 0; i <= m2; ++i){
        po = 0;
        for(int s = M * M - 1; s >= 0; --s){
            if(dp[i][s]){
                int sum = s - min(i, k) * n;
                int rem = max(0, k - i) * n;
                po = max(po, rem + max(0, S - sum));
                while(po < M * M && !p[po]) po++;
                if(po == M * M){
                    break;
                }
                ok = 1;
                ans = min(sum + (po - rem) - S, ans);
            }
        }
    }
    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 'int main()':
kitchen.cpp:94:16: warning: unused variable 'aa' [-Wunused-variable]
   94 |     int T = 1, aa;
      |                ^~

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