Submission #906237

#	Time	Username	Problem	Language	Result	Execution time	Memory
906237		n3rm1n	Kitchen (BOI19_kitchen)	C++17	100 / 100	68 ms	108120 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()
{
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= m; ++ i)
    {
        dp[i][0] = 0;
        for (int j = 0; j <= max_used; ++ j)
        {
            if(dp[i][j] < dp[i-1][j])dp[i][j] = max(dp[i][j], dp[i-1][j]);
            int adding = min(b[i], n);
            if(j >= b[i])
            {
                if(dp[i-1][j-b[i]] == -1)continue;
                int neww = dp[i-1][j - b[i]] + adding;
                dp[i][j] = max(dp[i][j], neww);
            }
        }
    }
    for (int i = hours; i <= max_used; ++ i)
    {
        if(dp[m][i] >= diverse)
        {
            cout << i-hours << endl;
            return;
        }
    }
    cout << "Impossible" << endl;
}
int main()
{
    speed();

    read();
    solve();
    return 0;
}
/***
4--
4 2 1
12 43 61 11
98 130
3--
4 2 1
12 43 61 11
30 15 5
6 6 5 7 6 7 7 7 7 6 7 6 7 6 6 6 5 6 6 7 7 6 5 7 7 5 5 5 5 7
12 6 11 8 8 11 9 6 18 20 21 18 19 20 10


*/

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