Submission #1270669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270669		akim9905	Kitchen (BOI19_kitchen)	C++20	100 / 100	62 ms	108360 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)(a.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 303;

int N,M,K,A[MAX],B[MAX];
int dp[MAX][MAX*MAX];

int main() {
    fio();

    cin>>N>>M>>K;

    int suma=0, sumb=0;
    for (int i=1; i<=N; i++) cin>>A[i], suma+=A[i];
    for (int i=1; i<=M; i++) cin>>B[i], sumb+=B[i];

    for (int i=1; i<=N; i++) {
        if (A[i]<K) {
            cout<<"Impossible\n";
            return 0;
        }
    }

    fill_n(&dp[0][0], MAX*MAX, -INF);
    
    dp[0][0]=0;
    for (int i=1; i<=M; i++) {
        for (int x=0; x<MAX*MAX; x++) {
            dp[i][x]=dp[i-1][x];
            if (x-B[i]>=0) dp[i][x]=max(dp[i][x], dp[i-1][x-B[i]]+min(N,B[i]));
        }
    }
    
    for (int i=suma; i<=sumb; i++) {
        if (dp[M][i]>=N*K) {
            cout<<i-suma<<'\n';
            return 0;
        }
    }

    cout<<"Impossible\n";
    return 0;
}

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