Submission #584347

#	Time	Username	Problem	Language	Result	Execution time	Memory
584347		talant117408	Kitchen (BOI19_kitchen)	C++17	100 / 100	65 ms	110500 KiB

kitchen

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

vector <bitset <100001>> dp(301);

void impossible() {
    cout << "Impossible" << endl;
    exit(0);
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector <int> a(n), b(m+1);
    for (auto &to : a) cin >> to;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    int dishes = 0, chefs = 0;
    for (auto to : a) dishes += to;
    if (*min_element(all(a)) < k) impossible();
    
    vector <vector <int>> dp(m+1, vector <int> (90000 + 1, -2e9));
    dp[0][0] = 0;
    
    for (int i = 1; i <= m; i++) {
        chefs += b[i];
        for (int j = chefs; j >= 0; j--) {
            if (j >= b[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - b[i]] + min(n, b[i]));
            else dp[i][j] = dp[i - 1][j];
        }
    }
    for (int j = dishes; j <= chefs; j++) {
        if (dp[m][j] >= n * k) {
            cout << j - dishes;
            return;
        }
    }
    
    impossible();
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

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