oj.uz

답안 #394375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394375 2021-04-26T12:57:04 Z rocks03 Kitchen (BOI19_kitchen) C++14
100 / 100
 569 ms 233648 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define int ll
const int INF = 1e15;
const int MAXN = 300+10;
int N, M, K, a[MAXN], b[MAXN], memo[MAXN][MAXN * MAXN];

void Impossible(){
    cout << "Impossible"; exit(0);
}

int f(int i, int sum){
    if(i == M){
        if(sum == 0) return 0;
        else return INF;
    }
    int& ans = memo[i][sum];
    if(ans != 1e18){
        return ans;
    }
    ans = f(i + 1, sum);
    if(sum - b[i] >= 0){
        ans = min(ans, f(i + 1, sum - b[i]) - min(N, b[i]));
    }
    return ans;
}

void solve(){
    cin >> N >> M >> K;
    rep(i, 0, N) cin >> a[i];
    rep(i, 0, M) cin >> b[i];
    int s = 0;
    rep(i, 0, N){
        if(a[i] < K) Impossible();
        s += a[i];
    }
    int sb = 0;
    rep(i, 0, M){
        sb += b[i];
    }
    if(s > sb) Impossible();
    if(M < K) Impossible();
    rep(i, 0, MAXN){
        rep(j, 0, MAXN * MAXN){
            memo[i][j] = 1e18;
        }
    }
    for(int ans = 0; ans + s <= sb; ans++){
        if(N * K + f(0, ans + s) <= 0){
            cout << ans; return;
        }
    }
    Impossible();
}

main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message

kitchen.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main(){
      |      ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 233412 KB Output is correct
2 Correct 112 ms 233468 KB Output is correct
3 Correct 113 ms 233384 KB Output is correct
4 Correct 110 ms 233412 KB Output is correct
5 Correct 111 ms 233428 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 233412 KB Output is correct
2 Correct 112 ms 233468 KB Output is correct
3 Correct 113 ms 233384 KB Output is correct
4 Correct 110 ms 233412 KB Output is correct
5 Correct 111 ms 233428 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 116 ms 233448 KB Output is correct
10 Correct 114 ms 233392 KB Output is correct
11 Correct 111 ms 233424 KB Output is correct
12 Correct 115 ms 233480 KB Output is correct
13 Correct 115 ms 233496 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 233412 KB Output is correct
2 Correct 210 ms 233428 KB Output is correct
3 Correct 268 ms 233540 KB Output is correct
4 Correct 395 ms 233428 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 187 ms 233552 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 233452 KB Output is correct
2 Correct 122 ms 233476 KB Output is correct
3 Correct 115 ms 233404 KB Output is correct
4 Correct 113 ms 233468 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 233412 KB Output is correct
2 Correct 112 ms 233468 KB Output is correct
3 Correct 113 ms 233384 KB Output is correct
4 Correct 110 ms 233412 KB Output is correct
5 Correct 111 ms 233428 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 116 ms 233448 KB Output is correct
10 Correct 114 ms 233392 KB Output is correct
11 Correct 111 ms 233424 KB Output is correct
12 Correct 115 ms 233480 KB Output is correct
13 Correct 115 ms 233496 KB Output is correct
14 Correct 199 ms 233412 KB Output is correct
15 Correct 210 ms 233428 KB Output is correct
16 Correct 268 ms 233540 KB Output is correct
17 Correct 395 ms 233428 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 187 ms 233552 KB Output is correct
20 Correct 113 ms 233452 KB Output is correct
21 Correct 122 ms 233476 KB Output is correct
22 Correct 115 ms 233404 KB Output is correct
23 Correct 113 ms 233468 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 338 ms 233508 KB Output is correct
26 Correct 569 ms 233540 KB Output is correct
27 Correct 161 ms 233528 KB Output is correct
28 Correct 261 ms 233568 KB Output is correct
29 Correct 319 ms 233648 KB Output is correct
30 Correct 405 ms 233536 KB Output is correct