Submission #1206115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206115		pinbu	Kitchen (BOI19_kitchen)	C++20	100 / 100	10 ms	668 KiB

kitchen

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

const int N = 100005;

int n, m, k;
int dp[N];
 
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
    cin >> n >> m >> k;
    int suma = 0;
    for (int i = 1, ai; i <= n; i++) {
        cin >> ai;
        if (ai < k) {
        	cout << "Impossible";
        	return 0;
        }
        suma += ai;
    }
    
    int sumb = 0;
    for (int j = 1; j <= 90000; j++) {
    	dp[j] = -2e9;
    }
    dp[0] = 0;
    for (int i = 1, bi; i <= m; i++) {
        cin >> bi;
        sumb += bi;
        for (int j = sumb; j >= bi; j--) {
        	dp[j] = max(dp[j], dp[j - bi] + min(bi, n)); // check ediorial!
        }
    }
 
    for (int i = suma; i <= sumb; i++) {
        if (dp[i] < n * k) {
        	continue;
        }
        cout << i - suma;
        return 0;
    }
    cout << "Impossible";
    
    return 0;
}

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