oj.uz

Submission #643926

# Submission time Handle Problem Language Result Execution time Memory
643926 2022-09-23T09:08:11 Z mychecksedad Kitchen (BOI19_kitchen) C++17
30 / 100
 83 ms 111968 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;
    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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 111940 KB Output is correct
2 Correct 64 ms 111800 KB Output is correct
3 Correct 67 ms 111800 KB Output is correct
4 Correct 71 ms 111868 KB Output is correct
5 Correct 69 ms 111912 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 61 ms 111828 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 111940 KB Output is correct
2 Correct 64 ms 111800 KB Output is correct
3 Correct 67 ms 111800 KB Output is correct
4 Correct 71 ms 111868 KB Output is correct
5 Correct 69 ms 111912 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 61 ms 111828 KB Output is correct
9 Correct 68 ms 111968 KB Output is correct
10 Correct 69 ms 111860 KB Output is correct
11 Correct 81 ms 111836 KB Output is correct
12 Correct 67 ms 111856 KB Output is correct
13 Incorrect 62 ms 111824 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 111936 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 75 ms 111896 KB Output is correct
2 Correct 83 ms 111884 KB Output is correct
3 Correct 81 ms 111828 KB Output is correct
4 Correct 77 ms 111820 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 111940 KB Output is correct
2 Correct 64 ms 111800 KB Output is correct
3 Correct 67 ms 111800 KB Output is correct
4 Correct 71 ms 111868 KB Output is correct
5 Correct 69 ms 111912 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 61 ms 111828 KB Output is correct
9 Correct 68 ms 111968 KB Output is correct
10 Correct 69 ms 111860 KB Output is correct
11 Correct 81 ms 111836 KB Output is correct
12 Correct 67 ms 111856 KB Output is correct
13 Incorrect 62 ms 111824 KB Output isn't correct
14 Halted 0 ms 0 KB -