제출 #1099279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099279		vjudge1	Kitchen (BOI19_kitchen)	C++17	100 / 100	85 ms	120596 KiB

kitchen

#include<bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 300 + 7;
const int LOG = 20;
const int ALP_BET = 26;
const long long base = 311;
const long long MOD = (long long)(1e9) + 7LL;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

const int INF = (int)(1e9) + 7;
const int maxSum = (int)(1e5) + 7;

int n, k;
int a[maxn];

int sum_a;

int m;
int b[maxn];

int sum_b;

int dp[maxn][maxSum];

int ans = INF;

void solve_sub_2(){
    // INIT
    ans = INF;

    // DUYET
    int max_state = 1 << m;
    for(int state = 1; state < max_state; ++state){

        int sum = 0;
        int sum_r = 0;
        for(int i = 0; i < m; ++i) if(state & (1 << i)){
            sum = sum + b[i + 1];
            int val = b[i + 1] % n;
            if(b[i + 1] >= n)
                val = n;
            sum_r = sum_r + val;
        }

        if(sum >= sum_a && sum_r >= n * k){
            ans = min(ans, sum - sum_a);
        }

    }

    if(ans == INF){
        cout << "Impossible\n";
    } else
        cout << ans << "\n";

    return;
}

void solve_sub_3(){
    // INIT
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    // DP
    for(int i = 0; i < m; ++i)
    for(int sum = 0; sum <= sum_b; ++sum) if(dp[i][sum] == 1){
        dp[i + 1][sum] = 1;
        if(sum + b[i + 1] <= sum_b)
            dp[i + 1][sum + b[i + 1]] = 1;
    }

    // ANS
    ans = INF;
    for(int sum = sum_a; sum <= sum_b; ++sum) if(dp[m][sum] == 1){
        ans = min(ans, sum - sum_a);
    }
    if(ans == INF){
        cout << "Impossible\n";
    } else
        cout << ans << "\n";
    return;
}

void solve(){
    // INIT
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    // DP
    for(int i = 0; i < m; ++i)
    for(int sum = 0; sum <= sum_b; ++sum) if(dp[i][sum] != -1){
        dp[i + 1][sum] = max(dp[i + 1][sum], dp[i][sum]);
        if(sum + b[i + 1] <= sum_b){
            int val = b[i + 1] % n;
            if(b[i + 1] >= n)
                val = n;
            dp[i + 1][sum + b[i + 1]] =
                max(dp[i + 1][sum + b[i + 1]], dp[i][sum] + val);
        }
    }

    // ANS
    ans = INF;
    for(int sum = sum_a; sum <= sum_b; ++sum) if(dp[m][sum] >= n * k){
        ans = min(ans, sum - sum_a);
    }
    if(ans == INF){
        cout << "Impossible\n";
    } else
        cout << ans << "\n";
    return;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // READ
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= m; ++i)
        cin >> b[i];

    // CHECK
    bool ok = true;
    for(int i = 1; i <= n; ++i) if(a[i] < k){
        ok = false;
        break;
    }
    if(ok == false){
        cout << "Impossible\n";
        return 0;
    }

    // INIT
    sum_a = 0;
    sum_b = 0;
    for(int i = 1; i <= n; ++i){
        sum_a = sum_a + a[i];
    }
    for(int i = 1; i <= m; ++i){
        sum_b = sum_b + b[i];
    }

    // SUBTASK
    if(m <= 15){
        solve_sub_2();
    } else
    if(k == 1){
        solve_sub_3();
    } else
        solve();

    return 0;
}

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