Submission #906234

#	Time	Username	Problem	Language	Result	Execution time	Memory
906234		n3rm1n	Kitchen (BOI19_kitchen)	C++17	30 / 100	41 ms	108116 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);
    }
   // cout << hours << " " << diverse << " " << max_used << endl;
}
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)
    {
        for (int j = 0; j <= max_used; ++ j)
        {
            //if(dp[i][j] == 0)continue;
            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])
            {
                int neww = dp[i-1][j - b[i]] + adding;
            //if(i == 1 && j == 130)cout << "* " << neww << endl;
            dp[i][j] = max(dp[i][j], neww);
            }
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    //cout << dp[m][130] << endl;
    for (int i = hours; i <= max_used; ++ i)
    {
       //cout << i << " " << dp[m][i] << endl;
        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
130 168

*/

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