oj.uz

Submission #1083531

# Submission time Handle Problem Language Result Execution time Memory
1083531 2024-09-03T12:14:52 Z browntoad Kitchen (BOI19_kitchen) C++14
100 / 100
 68 ms 109908 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for (int i = (n); i >= 1; i--)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define f first
#define s second
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 305;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

ll mpw(ll a, ll p, ll m = mod){
    ll ret = 1;
    while(p > 0){
        if (p & 1){
            ret *= a;
            ret %= m;
        }
        p >>= 1;
        a *= a;
        a %= m;
    }
    return ret;
}
ll inv(ll a){
    return mpw(a, mod-2);
}

int n, m, k;

int dp[maxn][maxn*maxn];
signed main(){
    IOS();
    cin>>n>>m>>k;

    int tot = 0;
    REP(i, n){
        int tt; cin>>tt;
        tot += tt;
        if (tt < k){
            cout<<"Impossible"<<endl;
            return 0;
        }
    }

    REP1(j, maxn*maxn-1){
        dp[0][j] = -mod; // -inf hehe
    }

    REP1(i, m){
        int b; cin>>b;
        REP(j, maxn*maxn){
            dp[i][j] = dp[i-1][j];
            if (j >= b) dp[i][j] = max(dp[i][j], dp[i-1][j-b] + min(b, n));
        }
    }

    int ret = -1;
    FOR(i, tot, maxn*maxn){
        if (dp[m][i] >= n*k){
            ret = i;
            break;
        }
    }

    if (ret == -1) cout<<"Impossible"<<endl;
    else {
        cout<<ret-tot<<endl;
    }
}
/*
5 4 1
3 4 5 2 1
3 3 7 6
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1528 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1528 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 4 ms 6236 KB Output is correct
10 Correct 3 ms 6236 KB Output is correct
11 Correct 3 ms 6132 KB Output is correct
12 Correct 4 ms 6236 KB Output is correct
13 Correct 4 ms 6236 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 95692 KB Output is correct
2 Correct 48 ms 83024 KB Output is correct
3 Correct 68 ms 109804 KB Output is correct
4 Correct 65 ms 109904 KB Output is correct
5 Correct 62 ms 106320 KB Output is correct
6 Correct 49 ms 76372 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15192 KB Output is correct
2 Correct 9 ms 15192 KB Output is correct
3 Correct 10 ms 15196 KB Output is correct
4 Correct 9 ms 15260 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1528 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 4 ms 6236 KB Output is correct
10 Correct 3 ms 6236 KB Output is correct
11 Correct 3 ms 6132 KB Output is correct
12 Correct 4 ms 6236 KB Output is correct
13 Correct 4 ms 6236 KB Output is correct
14 Correct 61 ms 95692 KB Output is correct
15 Correct 48 ms 83024 KB Output is correct
16 Correct 68 ms 109804 KB Output is correct
17 Correct 65 ms 109904 KB Output is correct
18 Correct 62 ms 106320 KB Output is correct
19 Correct 49 ms 76372 KB Output is correct
20 Correct 14 ms 15192 KB Output is correct
21 Correct 9 ms 15192 KB Output is correct
22 Correct 10 ms 15196 KB Output is correct
23 Correct 9 ms 15260 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 46 ms 77096 KB Output is correct
26 Correct 53 ms 89040 KB Output is correct
27 Correct 38 ms 58904 KB Output is correct
28 Correct 57 ms 89516 KB Output is correct
29 Correct 53 ms 91728 KB Output is correct
30 Correct 64 ms 109908 KB Output is correct