oj.uz

Submission #758817

# Submission time Handle Problem Language Result Execution time Memory
758817 2023-06-15T10:50:34 Z Hanksburger Kitchen (BOI19_kitchen) C++17
100 / 100
 72 ms 106316 KB 
#include <bits/stdc++.h>
using namespace std;
int dp[305][90005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k, sum=0;
    cin >> n >> m >> k;
    for (int i=1; i<=n; i++)
    {
        int x;
        cin >> x;
        if (x<k)
        {
            cout << "Impossible";
            return 0;
        }
        sum+=x;
    }
    for (int i=1; i<=90000; i++)
        dp[0][i]=-1e9;
    for (int i=1; i<=m; i++)
    {
        int x;
        cin >> x;
        for (int j=0; j<=90000; j++)
            dp[i][j]=max(dp[i-1][j], j>=x?(dp[i-1][j-x]+min(x, n)):(int)(-1e9));
    }
    for (int i=sum; i<=90000; i++)
    {
        if (dp[m][i]>=n*k)
        {
            cout << i-sum;
            return 0;
        }
    }
    cout << "Impossible";
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 5 ms 5844 KB Output is correct
10 Correct 4 ms 5844 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 4 ms 5844 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 92588 KB Output is correct
2 Correct 50 ms 80168 KB Output is correct
3 Correct 72 ms 106304 KB Output is correct
4 Correct 67 ms 106316 KB Output is correct
5 Correct 66 ms 102720 KB Output is correct
6 Correct 48 ms 73908 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 10 ms 14676 KB Output is correct
3 Correct 10 ms 14768 KB Output is correct
4 Correct 11 ms 14676 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 5 ms 5844 KB Output is correct
10 Correct 4 ms 5844 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 4 ms 5844 KB Output is correct
14 Correct 57 ms 92588 KB Output is correct
15 Correct 50 ms 80168 KB Output is correct
16 Correct 72 ms 106304 KB Output is correct
17 Correct 67 ms 106316 KB Output is correct
18 Correct 66 ms 102720 KB Output is correct
19 Correct 48 ms 73908 KB Output is correct
20 Correct 9 ms 14676 KB Output is correct
21 Correct 10 ms 14676 KB Output is correct
22 Correct 10 ms 14768 KB Output is correct
23 Correct 11 ms 14676 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 58 ms 74528 KB Output is correct
26 Correct 64 ms 86240 KB Output is correct
27 Correct 43 ms 56900 KB Output is correct
28 Correct 55 ms 86532 KB Output is correct
29 Correct 56 ms 88716 KB Output is correct
30 Correct 66 ms 106240 KB Output is correct