oj.uz

Submission #643960

# Submission time Handle Problem Language Result Execution time Memory
643960 2022-09-23T10:04:00 Z mychecksedad Kitchen (BOI19_kitchen) C++17
30 / 100
 77 ms 111964 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, 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;

    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

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: In function 'int main()':
kitchen.cpp:108:16: warning: unused variable 'aa' [-Wunused-variable]
  108 |     int T = 1, aa;
      |                ^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 111820 KB Output is correct
2 Correct 60 ms 111804 KB Output is correct
3 Correct 65 ms 111820 KB Output is correct
4 Correct 74 ms 111860 KB Output is correct
5 Correct 60 ms 111820 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 69 ms 111856 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 111820 KB Output is correct
2 Correct 60 ms 111804 KB Output is correct
3 Correct 65 ms 111820 KB Output is correct
4 Correct 74 ms 111860 KB Output is correct
5 Correct 60 ms 111820 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 69 ms 111856 KB Output is correct
9 Correct 63 ms 111840 KB Output is correct
10 Correct 69 ms 111928 KB Output is correct
11 Correct 65 ms 111916 KB Output is correct
12 Correct 65 ms 111900 KB Output is correct
13 Incorrect 63 ms 111928 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 111892 KB Output is correct
2 Correct 67 ms 111964 KB Output is correct
3 Correct 64 ms 111920 KB Output is correct
4 Correct 77 ms 111840 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 111820 KB Output is correct
2 Correct 60 ms 111804 KB Output is correct
3 Correct 65 ms 111820 KB Output is correct
4 Correct 74 ms 111860 KB Output is correct
5 Correct 60 ms 111820 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 69 ms 111856 KB Output is correct
9 Correct 63 ms 111840 KB Output is correct
10 Correct 69 ms 111928 KB Output is correct
11 Correct 65 ms 111916 KB Output is correct
12 Correct 65 ms 111900 KB Output is correct
13 Incorrect 63 ms 111928 KB Output isn't correct
14 Halted 0 ms 0 KB -