oj.uz

Submission #264942

# Submission time Handle Problem Language Result Execution time Memory
264942 2020-08-14T11:29:00 Z Hehehe Kitchen (BOI19_kitchen) C++14
100 / 100
 112 ms 114296 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
//#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 3e2 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, m, k, a[N], b[N], dp[N][N*N], s;


void solve(){

    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s += a[i];
    }

    for(int i = 1; i <= m; i++){
        cin >> b[i];
    }
    
    for(int i = 1; i <= n; i++){
        if(a[i] < k){
            cout << "Impossible" << '\n';
            return;
        }
    }

    for(int i = 1; i < N*N; i++)dp[0][i] = -inf;

    for(int i = 1; i <= m; i++){
        for(int j = 0; j < N*N; j++){
            dp[i][j] = dp[i - 1][j];
            if(b[i] <= j){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + min(n, b[i]));
            }
        }
    }

    for(int i = s; i < N*N; i++){
        if(dp[m][i] >= k*n){
            cout << i - s << '\n';
            return;
        }
    }


    cout << "Impossible" << '\n';
}



int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1408 KB Output is correct
2 Correct 2 ms 1408 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1408 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 2 ms 1408 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1408 KB Output is correct
2 Correct 2 ms 1408 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1408 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 2 ms 1408 KB Output is correct
9 Correct 7 ms 6400 KB Output is correct
10 Correct 6 ms 6400 KB Output is correct
11 Correct 9 ms 6400 KB Output is correct
12 Correct 6 ms 6400 KB Output is correct
13 Correct 7 ms 6400 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 99448 KB Output is correct
2 Correct 71 ms 86264 KB Output is correct
3 Correct 97 ms 114296 KB Output is correct
4 Correct 96 ms 114296 KB Output is correct
5 Correct 93 ms 110456 KB Output is correct
6 Correct 67 ms 79480 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15872 KB Output is correct
2 Correct 13 ms 15872 KB Output is correct
3 Correct 13 ms 15872 KB Output is correct
4 Correct 14 ms 15872 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1408 KB Output is correct
2 Correct 2 ms 1408 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1408 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 2 ms 1408 KB Output is correct
9 Correct 7 ms 6400 KB Output is correct
10 Correct 6 ms 6400 KB Output is correct
11 Correct 9 ms 6400 KB Output is correct
12 Correct 6 ms 6400 KB Output is correct
13 Correct 7 ms 6400 KB Output is correct
14 Correct 95 ms 99448 KB Output is correct
15 Correct 71 ms 86264 KB Output is correct
16 Correct 97 ms 114296 KB Output is correct
17 Correct 96 ms 114296 KB Output is correct
18 Correct 93 ms 110456 KB Output is correct
19 Correct 67 ms 79480 KB Output is correct
20 Correct 13 ms 15872 KB Output is correct
21 Correct 13 ms 15872 KB Output is correct
22 Correct 13 ms 15872 KB Output is correct
23 Correct 14 ms 15872 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 85 ms 80144 KB Output is correct
26 Correct 108 ms 92776 KB Output is correct
27 Correct 56 ms 61332 KB Output is correct
28 Correct 100 ms 93168 KB Output is correct
29 Correct 112 ms 95352 KB Output is correct
30 Correct 101 ms 114296 KB Output is correct