oj.uz

Submission #906236

# Submission time Handle Problem Language Result Execution time Memory
906236 2024-01-13T20:29:04 Z n3rm1n Kitchen (BOI19_kitchen) C++17
30 / 100
 44 ms 107880 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()
{
    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])
            {
                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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 107864 KB Output is correct
2 Correct 19 ms 107864 KB Output is correct
3 Correct 19 ms 107868 KB Output is correct
4 Correct 18 ms 107868 KB Output is correct
5 Correct 18 ms 107768 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 19 ms 107864 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 107864 KB Output is correct
2 Correct 19 ms 107864 KB Output is correct
3 Correct 19 ms 107868 KB Output is correct
4 Correct 18 ms 107868 KB Output is correct
5 Correct 18 ms 107768 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 19 ms 107864 KB Output is correct
9 Correct 18 ms 107868 KB Output is correct
10 Correct 19 ms 107752 KB Output is correct
11 Correct 18 ms 107868 KB Output is correct
12 Correct 18 ms 107868 KB Output is correct
13 Incorrect 18 ms 107868 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 107760 KB Output is correct
2 Correct 18 ms 107868 KB Output is correct
3 Correct 19 ms 107868 KB Output is correct
4 Correct 19 ms 107852 KB Output is correct
5 Correct 1 ms 600 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 107864 KB Output is correct
2 Correct 19 ms 107864 KB Output is correct
3 Correct 19 ms 107868 KB Output is correct
4 Correct 18 ms 107868 KB Output is correct
5 Correct 18 ms 107768 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 19 ms 107864 KB Output is correct
9 Correct 18 ms 107868 KB Output is correct
10 Correct 19 ms 107752 KB Output is correct
11 Correct 18 ms 107868 KB Output is correct
12 Correct 18 ms 107868 KB Output is correct
13 Incorrect 18 ms 107868 KB Output isn't correct
14 Halted 0 ms 0 KB -