oj.uz

답안 #394366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394366 2021-04-26T12:53:23 Z rocks03 Kitchen (BOI19_kitchen) C++14
20 / 100
 396 ms 233720 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";
}

int f(int i, int sum){
    if(i == M){
        if(sum == 0) return 0;
        else return INF;
    }
    int& ans = memo[i][sum];
    if(ans != INF){
        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];
    }
    rep(i, 0, MAXN){
        rep(j, 0, MAXN * MAXN){
            memo[i][j] = INF;
        }
    }
    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:68:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      |      ^

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 233412 KB Output is correct
2 Correct 125 ms 233492 KB Output is correct
3 Correct 121 ms 233452 KB Output is correct
4 Correct 122 ms 233412 KB Output is correct
5 Correct 125 ms 233484 KB Output is correct
6 Incorrect 123 ms 233524 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 233412 KB Output is correct
2 Correct 125 ms 233492 KB Output is correct
3 Correct 121 ms 233452 KB Output is correct
4 Correct 122 ms 233412 KB Output is correct
5 Correct 125 ms 233484 KB Output is correct
6 Incorrect 123 ms 233524 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 233496 KB Output is correct
2 Correct 194 ms 233508 KB Output is correct
3 Correct 260 ms 233556 KB Output is correct
4 Correct 396 ms 233720 KB Output is correct
5 Correct 122 ms 233524 KB Output is correct
6 Correct 210 ms 233508 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 233500 KB Output is correct
2 Correct 123 ms 233476 KB Output is correct
3 Correct 125 ms 233484 KB Output is correct
4 Correct 121 ms 233412 KB Output is correct
5 Incorrect 126 ms 233416 KB Output isn't correct

Subtask #5
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 233412 KB Output is correct
2 Correct 125 ms 233492 KB Output is correct
3 Correct 121 ms 233452 KB Output is correct
4 Correct 122 ms 233412 KB Output is correct
5 Correct 125 ms 233484 KB Output is correct
6 Incorrect 123 ms 233524 KB Output isn't correct
7 Halted 0 ms 0 KB -