oj.uz

Submission #745848

# Submission time Handle Problem Language Result Execution time Memory
745848 2023-05-21T08:46:43 Z vjudge1 Kitchen (BOI19_kitchen) C++11
51 / 100
 24 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;

int n,m,k;
int a[301];
int b[301];
int sum=0;

void subtask1() {
    int ans=1e9;
    if (m<k) {
        cout << "Impossible" << endl;
        return;
    }
    if (k==1) {
        for (int i=1;i<=m;i++) {
            if (b[i]>=sum) {
                ans=min(ans,b[i]-sum);
            }
        }
        int u=0;
        for (int i=1;i<=m;i++) {
            u+=b[i];
        }
        if (u>=sum) {
            ans=min(ans,u);
        }
        if (ans==1e9) {
            cout << "Impossible" << endl;
        } else {
            cout << ans-sum << endl;
        }
        return;
    } else if (k==2) {
        int u=0;
        for (int i=1;i<=m;i++) {
            u+=b[i];
        }
        if (u>=sum) {
            ans=min(ans,u);
        }
        if (ans==1e9) {
            cout << "Impossible" << endl;
        } else {
            cout << ans-sum << endl;
        }
        return;
    } else {
        cout << "Impossible" << endl;
        return;
    }
}

int check(int mask) {
    int u=0;
    int db=0;
    int su=0;
    for (int i=0;i<m;i++) {
        if ((mask>>i)%2==1) {
            if (b[i+1]>=n) {
                db++;
            } else {
                u+=b[i+1];
            }
            su+=b[i+1];
        }
    }
    if ((k<=db+(int(u/n))) && (sum<=su)) {
        return(su-sum);
    } else {
        return(1e9);
    }
}

void subtask2() {
    for (int i=1;i<=n;i++) {
        if (a[i]<k) {
            cout << "Impossible" << endl;
            return;
        }
    }
    int ans=1e9;
    for (int i=0;i<pow(2,m);i++) {
        ans=min(ans,check(i));
    }
    if (ans>=1e9) {
        cout << "Impossible" << endl;
    } else {
        cout << ans << endl;
    }
}

void subtask3() {
    vector<bool> g;
    g.assign(sum+1+300+300,0);
    g[300]=1;
    for (int i=1;i<=m;i++) {
        for (int j=min(i*300,sum+1+300);j>max(0,sum-(m-i)*300-300);j--) {
            g[j+300]=g[j+300] | g[j+300-b[i]];
        }
    }
    int ans=-1;
    for (int i=sum+300;i<sum+300+300;i++) {
        if (g[i]) {
            ans=i-300;
            break;
        }
    }
    /*
    for (int i=0;i<g.size();i++) {
        cout << i << ": " << g[i] << endl;
    }
    cout << endl;
    */
    if (ans==-1) {
        cout << "Impossible" << endl;
    } else {
        cout << ans-sum << endl;
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        sum+=a[i];
    }
    for (int i=1;i<=m;i++) {
        cin >> b[i];
    }
    /*
    if (m<=2) {
        subtask1();
        return(0);
    }
    */

    if (m<=15) {
        subtask2();
        return(0);
    }

    if (k==1) {
        subtask3();
        return(0);
    }
    return 0;
}

/*
1 8 1
100
12 56 8 23 6 4 59 163
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 320 KB Output is correct
12 Correct 3 ms 224 KB Output is correct
13 Correct 3 ms 212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 332 KB Output is correct
2 Correct 10 ms 332 KB Output is correct
3 Correct 24 ms 332 KB Output is correct
4 Correct 12 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 212 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 320 KB Output is correct
12 Correct 3 ms 224 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 16 ms 332 KB Output is correct
15 Correct 10 ms 332 KB Output is correct
16 Correct 24 ms 332 KB Output is correct
17 Correct 12 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 8 ms 212 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -