oj.uz

Submission #1108248

# Submission time Handle Problem Language Result Execution time Memory
1108248 2024-11-03T13:34:33 Z flyingkite Kitchen (BOI19_kitchen) C++17
100 / 100
 49 ms 220184 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 305;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n,m,k,sA = 0, sB = 0, sMn = 0;
ll a[N], b[N], dp[N][N * N];
void to_thic_cau(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n;i++){
        cin >> a[i];
        sA += a[i];
    }
    for(int i = 1; i <= m;i++){
        cin >> b[i];
        sB += b[i]; sMn += min(b[i], n);
    }
    for(int i = 1; i <= n;i++) if(a[i] < k){cout << "Impossible" << '\n'; return;}
    if(sB < sA){
        cout << "Impossible" << '\n';
        return;
    }
    if(sMn < n * k){
        cout << "Impossible" << '\n';
        return;
    }
    for(int i = 0; i <= n;i++){
        for(int j = 0; j <= sB;j++) dp[i][j] = -inf;
    }
    dp[0][0] = 0;
    for(int i = 1; i <= m;i++){
        for(int j = 0; j <= sB;j++){
            dp[i][j] = dp[i-1][j];
            if(j >= b[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + min(n, b[i]));
        }
    }
    for(int j = sA; j <= sB;j++){
        if(dp[m][j] >= n * k){
            cout << j - sA << '\n';
            return;
        }
    }
    cout << "Impossible" << '\n';
}    
 
signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 2 ms 12624 KB Output is correct
5 Correct 20 ms 219984 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 2 ms 12624 KB Output is correct
5 Correct 20 ms 219984 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 3 ms 12860 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 3 ms 22864 KB Output is correct
13 Correct 21 ms 220152 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 217940 KB Output is correct
2 Correct 35 ms 217972 KB Output is correct
3 Correct 42 ms 219984 KB Output is correct
4 Correct 49 ms 220176 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 33 ms 217972 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31056 KB Output is correct
2 Correct 3 ms 31056 KB Output is correct
3 Correct 3 ms 31056 KB Output is correct
4 Correct 3 ms 31056 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 2 ms 12624 KB Output is correct
5 Correct 20 ms 219984 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 3 ms 12860 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 3 ms 22864 KB Output is correct
13 Correct 21 ms 220152 KB Output is correct
14 Correct 44 ms 217940 KB Output is correct
15 Correct 35 ms 217972 KB Output is correct
16 Correct 42 ms 219984 KB Output is correct
17 Correct 49 ms 220176 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 33 ms 217972 KB Output is correct
20 Correct 3 ms 31056 KB Output is correct
21 Correct 3 ms 31056 KB Output is correct
22 Correct 3 ms 31056 KB Output is correct
23 Correct 3 ms 31056 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 28 ms 154440 KB Output is correct
26 Correct 32 ms 179024 KB Output is correct
27 Correct 16 ms 117588 KB Output is correct
28 Correct 32 ms 179024 KB Output is correct
29 Correct 36 ms 183204 KB Output is correct
30 Correct 47 ms 220184 KB Output is correct