oj.uz

Submission #643908

# Submission time Handle Problem Language Result Execution time Memory
643908 2022-09-23T08:28:04 Z mychecksedad Kitchen (BOI19_kitchen) C++17
0 / 100
 87 ms 644 KB 
/* 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;

    if(k == 1){
        if(m == 1){
            if(b[1] >= S) cout << b[1] - S;
            else cout << "Impossible";
        }
        else if(m == 2){
            int ans = MOD;
            if(b[1] - k*n >= S) ans = min(ans, b[1] - S);
            if(b[2] - k*n >= S) ans = min(ans, b[2] - S);
            if(b[1] + b[2] - k*n >= S) ans = min(ans, b[1] + b[2] - S - k*n);
            if(ans==MOD) cout << "Impossible";
            else cout << ans;
        }
        return;
    }else if(k == 2){
        if(S <= b[1] + b[2] - k*n) cout << b[1] + b[2] - S - k*n;
        else cout << "Impossible";
        return;
    }



    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 = 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

kitchen.cpp: In function 'int main()':
kitchen.cpp:114:16: warning: unused variable 'aa' [-Wunused-variable]
  114 |     int T = 1, aa;
      |                ^~
kitchen.cpp: In function 'void solve()':
kitchen.cpp:41:72: warning: iteration 305 invokes undefined behavior [-Waggressive-loop-optimizations]
   41 |     for(int j = 0; j < M; ++j) for(int i = 0; i < M * M; ++i) dp[j][i] = 0;
      |                                                               ~~~~~~~~~^~~
kitchen.cpp:41:49: note: within this loop
   41 |     for(int j = 0; j < M; ++j) for(int i = 0; i < M * M; ++i) dp[j][i] = 0;
      |                                               ~~^~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -