oj.uz

Submission #905291

# Submission time Handle Problem Language Result Execution time Memory
905291 2024-01-12T22:32:49 Z n3rm1n Kitchen (BOI19_kitchen) C++17
0 / 100
 54 ms 69028 KB 
#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 = 0; 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+b[i]] = max(dp[i][j+b[i]], dp[i-1][j] + 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 69028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -