oj.uz

Submission #567056

# Submission time Handle Problem Language Result Execution time Memory
567056 2022-05-23T07:43:46 Z MrDeboo Kitchen (BOI19_kitchen) C++17
52 / 100
 1000 ms 106444 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;
    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 80 ms 106324 KB Output is correct
2 Correct 83 ms 106324 KB Output is correct
3 Correct 83 ms 106328 KB Output is correct
4 Correct 80 ms 106324 KB Output is correct
5 Correct 81 ms 106316 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 87 ms 106268 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 106324 KB Output is correct
2 Correct 83 ms 106324 KB Output is correct
3 Correct 83 ms 106328 KB Output is correct
4 Correct 80 ms 106324 KB Output is correct
5 Correct 81 ms 106316 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 87 ms 106268 KB Output is correct
9 Correct 369 ms 106328 KB Output is correct
10 Correct 368 ms 106328 KB Output is correct
11 Correct 380 ms 106332 KB Output is correct
12 Correct 428 ms 106332 KB Output is correct
13 Correct 393 ms 106328 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 106316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 106324 KB Output is correct
2 Correct 821 ms 106444 KB Output is correct
3 Correct 837 ms 106332 KB Output is correct
4 Correct 859 ms 106328 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 80 ms 106324 KB Output is correct
2 Correct 83 ms 106324 KB Output is correct
3 Correct 83 ms 106328 KB Output is correct
4 Correct 80 ms 106324 KB Output is correct
5 Correct 81 ms 106316 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 87 ms 106268 KB Output is correct
9 Correct 369 ms 106328 KB Output is correct
10 Correct 368 ms 106328 KB Output is correct
11 Correct 380 ms 106332 KB Output is correct
12 Correct 428 ms 106332 KB Output is correct
13 Correct 393 ms 106328 KB Output is correct
14 Execution timed out 1098 ms 106316 KB Time limit exceeded
15 Halted 0 ms 0 KB -