제출 #906237

#제출 시각아이디문제언어결과실행 시간메모리
906237n3rm1nKitchen (BOI19_kitchen)C++17
100 / 100
68 ms108120 KiB
#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


*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...