Submission #905293

#	Time	Username	Problem	Language	Result	Execution time	Memory
905293		n3rm1n	Kitchen (BOI19_kitchen)	C++17	0 / 100	56 ms	68572 KiB

kitchen

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 305, MAXH = 90005;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
int a[MAXN], b[MAXN];
int diverse = 0, hours = 0;
int max_used = 0;
void read()
{
    cin >> n >> m >> k;
    int no = 0;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        hours += a[i];
        if(a[i] < k)no = 1;
    }
    diverse = k * n;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> b[i];
        max_used += b[i];
    }
    if(no == 1)
    {
        cout << "Impossible" << endl;
        exit(0);
    }
}
int dp[MAXN][MAXH/**the number of used hours*/];
void solve()
{
    for (int i = 1; i <= m; ++ i)
    {
        for (int j = b[i]; j <= max_used; ++ j)
        {
            //if(dp[i][j] == 0)continue;
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            int adding = min(b[i], n);
            dp[i][j] = max(dp[i][j], dp[i-1][j - b[i]] + adding);
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    for (int i = 0; i <= max_used; ++ i)
    {
        if(dp[m][i] >= diverse)
        {
            cout << i-hours << endl;
            return;
        }
    }
    cout << "Impossible" << endl;
}
int main()
{
    speed();

    read();
    solve();
    return 0;
}

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