oj.uz

답안 #643972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643972 2022-09-23T11:01:13 Z mychecksedad Kitchen (BOI19_kitchen) C++17
30 / 100
 89 ms 111988 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 && rem < M * M){
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 111924 KB Output is correct
2 Correct 76 ms 111852 KB Output is correct
3 Correct 88 ms 111852 KB Output is correct
4 Correct 64 ms 111896 KB Output is correct
5 Correct 64 ms 111828 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 76 ms 111988 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 111924 KB Output is correct
2 Correct 76 ms 111852 KB Output is correct
3 Correct 88 ms 111852 KB Output is correct
4 Correct 64 ms 111896 KB Output is correct
5 Correct 64 ms 111828 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 76 ms 111988 KB Output is correct
9 Correct 70 ms 111804 KB Output is correct
10 Correct 78 ms 111832 KB Output is correct
11 Correct 68 ms 111856 KB Output is correct
12 Correct 64 ms 111896 KB Output is correct
13 Incorrect 81 ms 111868 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 111868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 111872 KB Output is correct
2 Correct 89 ms 111848 KB Output is correct
3 Correct 69 ms 111840 KB Output is correct
4 Correct 73 ms 111860 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #5
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 111924 KB Output is correct
2 Correct 76 ms 111852 KB Output is correct
3 Correct 88 ms 111852 KB Output is correct
4 Correct 64 ms 111896 KB Output is correct
5 Correct 64 ms 111828 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 76 ms 111988 KB Output is correct
9 Correct 70 ms 111804 KB Output is correct
10 Correct 78 ms 111832 KB Output is correct
11 Correct 68 ms 111856 KB Output is correct
12 Correct 64 ms 111896 KB Output is correct
13 Incorrect 81 ms 111868 KB Output isn't correct
14 Halted 0 ms 0 KB -