oj.uz

답안 #771540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771540 2023-07-03T06:14:28 Z Wael Kitchen (BOI19_kitchen) C++14
21 / 100
 1000 ms 220236 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
//#define int long long
#define F first
#define S second
#define endl '\n'
#define INT INT_MAX
int const M = 301 , Mx = 1e5 , N = 4e6 + 2 , lg = 30 , mod = 1e9 + 7;
int dx[] = {0 , 0 , -1 , 1 , 1 , 1 , -1 , -1};
int dy[] = {1 , -1 , 0 , 0 , 1 , -1 , 1 , -1};
int T , n , m , k , x , ans = 1e9 , y , w , sum , a[M] , b[M] , mx = 9e4 , dp[4][Mx];
int Dp[4][Mx][M];
int closer[Mx][M] , sum1;

main() {
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);

    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i] , sum += a[i];
    for(int i = 1 ; i <= m ; ++i) cin >> b[i] , sum1 += b[i];

    for(int i = 1 ; i <= n ; ++i) {
        if(a[i] < k) {
            cout << "Impossible" << endl;
            return 0;
        }
    }

    sort(b + 1 , b + m + 1);
    int Index = lower_bound(b + 1 , b + m + 1 , n) - b; --Index;

    dp[0][0] = 1;
    for(int i = 1 ; i <= Index ; ++i) {
        int I = (i % 2);
        dp[I][0] = 1;
        for(int j = 1 ; j <= mx ; ++j) {
            dp[I][j] = dp[!I][j];
            if(j >= b[i]) dp[I][j] = max(dp[I][j] , dp[!I][j - b[i]]);
        }
    }

    Dp[Index % 2][0][0] = 1;
    for(int i = Index + 1 ; i <= m ; ++i) {
        int I = (i % 2);
        Dp[I][0][0] = 1;
        for(int j = 1 ; j <= sum1 ; ++j) {
            for(int cnt = 1 ; cnt <= m - Index ; ++cnt) {
                Dp[I][j][cnt] = Dp[!I][j][cnt];
                if(j >= b[i]) Dp[I][j][cnt] = max(Dp[I][j][cnt] , Dp[!I][j - b[i]][cnt - 1]);
            }
        }
    }

    int I = m % 2;
    for(int cnt = 1 ; cnt <= m - Index ; ++cnt) {
        for(int j = mx ; j >= 1 ; --j) {
            closer[j][cnt] = closer[j + 1][cnt];
            if(Dp[I][j][cnt]) closer[j][cnt] = j;
        }
    }

    for(int Left = 0 ; Left <= mx ; ++Left) {
        if(dp[Index % 2][Left]) {
            if(Left >= sum) ans = min(ans , Left - sum);
            else {
                int ReqCnt = k - (Left / n);
                ReqCnt = max(ReqCnt , 0);
                int ReqJ = sum - Left;
                for(int CurCnt = ReqCnt ; CurCnt <= m - Index ; ++CurCnt)
                    if(closer[ReqJ][CurCnt]) ans = min(ans , (Left + closer[ReqJ][CurCnt]) - sum);
            }
        }
    }

    if(ans == 1e18) cout << "Impossible" << endl;
    else cout << ans << endl;

    return 0;
}

Compilation message

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

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 107236 KB Output is correct
2 Correct 53 ms 107056 KB Output is correct
3 Correct 52 ms 107336 KB Output is correct
4 Correct 53 ms 107736 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 57 ms 107032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 107236 KB Output is correct
2 Correct 53 ms 107056 KB Output is correct
3 Correct 52 ms 107336 KB Output is correct
4 Correct 53 ms 107736 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 57 ms 107032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 1032 KB Output is correct
2 Correct 28 ms 1144 KB Output is correct
3 Correct 156 ms 220236 KB Output is correct
4 Execution timed out 1094 ms 195244 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 110292 KB Output is correct
2 Correct 69 ms 109244 KB Output is correct
3 Correct 62 ms 110096 KB Output is correct
4 Correct 53 ms 110696 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 107236 KB Output is correct
2 Correct 53 ms 107056 KB Output is correct
3 Correct 52 ms 107336 KB Output is correct
4 Correct 53 ms 107736 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 57 ms 107032 KB Output isn't correct
9 Halted 0 ms 0 KB -