Submission #1270668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270668		akim9905	Kitchen (BOI19_kitchen)	C++20	21 / 100	59 ms	94020 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 go(int i, int x) {
//     if (i==0) return (x==0?0:-INF);

//     int &ret=dp[i][x];
//     if (ret!=-1) return ret;

//     ret=go(i-1,B[i]);
//     if (x-B[i]>=0) ret=max(ret, go(i-1,x-B[i])+min(N,B[i]));

//     return ret;
// }

int main() {
    fio();
    // memset(dp,-1,sizeof dp);

    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;
        }
    }

    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: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 20
• Subtask 4: 21 / 21
• Subtask 5: 0 / 28