oj.uz

Submission #586930

# Submission time Handle Problem Language Result Execution time Memory
586930 2022-07-01T05:25:42 Z 박상훈(#8395) Kitchen (BOI19_kitchen) C++17
0 / 100
 20 ms 724 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[303], b[303], mn[90090], n, m, k;
bool dp[2][303][90090], dp2[2][90090];

void calc1(vector<int> &a){
    dp[0][0][0] = 1;
    for (int i=0;i<(int)a.size();i++){
        for (int j=0;j<=i;j++){
            for (int k=n*j;k<=300*j;k++) if (dp[i&1][j][k]){
                dp[(i+1)&1][j+1][k+a[i]] = 1;
            }
        }
    }
}

void calc2(vector<int> &a){
    dp2[0][0] = 1;
    for (int i=0;i<(int)a.size();i++){
        for (int j=0;j<90090;j++) if (dp2[i&1][j]){
            dp2[(i+1)&1][j+a[i]] = 1;
        }
    }

    mn[90001] = 1e9;
    for (int i=90000;i>=0;i--){
        mn[i] = mn[i+1];
        if (dp2[(int)a.size()&1][i]) mn[i] = i;
    }
}

void NO(){
    printf("Impossible\n"); exit(0);
}

int main(){
    int S = 0;
    scanf("%d %d %d", &n, &m, &k);
    for (int i=1;i<=n;i++){
        scanf("%d", a+i);
        if (a[i]<k) NO();
        S += a[i];
    }

    vector<int> A, B;
    for (int i=1;i<=m;i++){
        scanf("%d", b+i);
        if (b[i]>=n) A.push_back(b[i]);
        else B.push_back(b[i]);
    }

    calc1(A);
    calc2(B);

    int ans = 1e9;
    for (int i=0;i<=(int)A.size();i++){
        for (int j=n*i;j<=300*i;j++) if (dp[(int)A.size()&1][i][j]){
            int x = max(0, max(n*(k-i), S-j));
            ans = min(ans, mn[x]+j - S);
        }
    }

    if (ans>90000) NO();
    printf("%d\n", ans);
    return 0;
}

Compilation message

kitchen.cpp: In function 'int main()':
kitchen.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d", a+i);
      |         ~~~~~^~~~~~~~~~~
kitchen.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d", b+i);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

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