Submission #1306562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306562		veham	Kitchen (BOI19_kitchen)	C++20	100 / 100	19 ms	584 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

int solve(int N, int M, int K, vi &A, vi &B){
    int asum = accumulate(A.begin(),A.end(),0);
    int bsum = accumulate(B.begin(),B.end(),0);
    if(asum > bsum) return -1;
    if(*min_element(A.begin(),A.end()) < K) return -1;
    vi U(bsum+1,-1);
    U[0] = 0;
    for(int i = 0;i < M;i++){
        for(int j = bsum - B[i];j >= 0;j--) if(U[j] != -1) U[j+B[i]] = max(U[j+B[i]], U[j] + min(N,B[i]));
    }
    auto itr = find_if(U.begin() + asum, U.end(),[&](int x){return x >= N*K;});
    if(itr == U.end()) return -1;
    return  itr - U.begin() - asum;
}

int main(){
    int N,M,K;
    cin >> N >> M >> K;
    vi A(N), B(M);
    for(int i = 0;i < N;i++) cin >> A[i];
    for(int i = 0;i < M;i++) cin >> B[i];

    int ans = solve(N,M,K,A,B);
    if(ans == -1) cout << "Impossible";
    else cout << ans;
}

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