oj.uz

Submission #567062

# Submission time Handle Problem Language Result Execution time Memory
567062 2022-05-23T07:44:58 Z MrDeboo Kitchen (BOI19_kitchen) C++17
72 / 100
 1000 ms 106340 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
int dp[301][90001];
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    if(k==1){
        int a[n];
        int b[m];
        for(auto &i:a)cin>>i;
        for(auto &i:b)cin>>i;
        if(m<k){cout<<"Impossible";return 0;}
        for(int i=0;i<n;i++){
            if(a[i]<k){cout<<"Impossible";return 0;}
        }
        bool dp[m+1][300*m+1];
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(int i=0;i<m;i++){
            for(int j=300*m-b[i];j>=0;j--){
                if(dp[0][j])dp[0][j+b[i]]=1;
            }
        }
        int sm=0;
        int ans=INT_MAX;
        for(auto &i:a)sm+=i;
        for(int i=0;i<=m;i++){
            for(int w=sm;w<=300*m;w++){
                if(dp[i][w]){
                    ans=min(ans,w-sm);
                    break;
                }
            }
        }
        if(ans==INT_MAX)cout<<"Impossible";
        else cout<<ans;
    }else{
        int a[n];
        int b[m];
        for(auto &i:a)cin>>i;
        for(auto &i:b)cin>>i;
        if(m<k){cout<<"Impossible";return 0;}
        for(int i=0;i<n;i++){
            if(a[i]<k){cout<<"Impossible";return 0;}
        }
        memset(dp,-1,sizeof dp);
        dp[0][0]=0;
        for(int i=0;i<m;i++){
            for(int w=299;w>=0;w--){
                for(int j=90000-b[i];j>=0;j--){
                    if(dp[w][j]!=-1)dp[w+1][j+b[i]]=max(dp[w+1][j+b[i]],dp[w][j]+min(b[i],n));
                }
            }
        }
        int sm=0;
        int ans=INT_MAX;
        for(auto &i:a)sm+=i;
        for(int i=k;i<=m;i++){
            for(int w=sm;w<=90000;w++){
                if(dp[i][w]>=n*k){
                    ans=min(ans,w-sm);
                }
            }
        }
        if(ans==INT_MAX)cout<<"Impossible";
        else cout<<ans;
    }
}

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 1 ms 212 KB Output is correct
4 Correct 88 ms 106252 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 1 ms 212 KB Output is correct
4 Correct 88 ms 106252 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 359 ms 106328 KB Output is correct
10 Correct 340 ms 106328 KB Output is correct
11 Correct 356 ms 106240 KB Output is correct
12 Correct 392 ms 106340 KB Output is correct
13 Correct 374 ms 106332 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20308 KB Output is correct
2 Correct 23 ms 15392 KB Output is correct
3 Correct 43 ms 26816 KB Output is correct
4 Correct 40 ms 26836 KB Output is correct
5 Correct 34 ms 24984 KB Output is correct
6 Correct 19 ms 13068 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 106328 KB Output is correct
2 Correct 979 ms 106328 KB Output is correct
3 Correct 855 ms 106328 KB Output is correct
4 Correct 885 ms 106324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

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 1 ms 212 KB Output is correct
4 Correct 88 ms 106252 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 359 ms 106328 KB Output is correct
10 Correct 340 ms 106328 KB Output is correct
11 Correct 356 ms 106240 KB Output is correct
12 Correct 392 ms 106340 KB Output is correct
13 Correct 374 ms 106332 KB Output is correct
14 Correct 31 ms 20308 KB Output is correct
15 Correct 23 ms 15392 KB Output is correct
16 Correct 43 ms 26816 KB Output is correct
17 Correct 40 ms 26836 KB Output is correct
18 Correct 34 ms 24984 KB Output is correct
19 Correct 19 ms 13068 KB Output is correct
20 Correct 901 ms 106328 KB Output is correct
21 Correct 979 ms 106328 KB Output is correct
22 Correct 855 ms 106328 KB Output is correct
23 Correct 885 ms 106324 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Execution timed out 1088 ms 106308 KB Time limit exceeded
26 Halted 0 ms 0 KB -