oj.uz

Submission #771553

# Submission time Handle Problem Language Result Execution time Memory
771553 2023-07-03T06:19:47 Z Wael Kitchen (BOI19_kitchen) C++14
52 / 100
 1000 ms 242048 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long 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 = 1e18 , y , w , sum , a[M] , b[M] , mx = 9e4 , dp[4][Mx];
bool Dp[2][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 , 0ll);
                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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 212492 KB Output is correct
2 Correct 67 ms 212524 KB Output is correct
3 Correct 68 ms 212536 KB Output is correct
4 Correct 67 ms 212736 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 66 ms 212556 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 212492 KB Output is correct
2 Correct 67 ms 212524 KB Output is correct
3 Correct 68 ms 212536 KB Output is correct
4 Correct 67 ms 212736 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 66 ms 212556 KB Output is correct
9 Correct 78 ms 214216 KB Output is correct
10 Correct 76 ms 213988 KB Output is correct
11 Correct 76 ms 213940 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 4 ms 1748 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1872 KB Output is correct
2 Correct 29 ms 1900 KB Output is correct
3 Correct 122 ms 242048 KB Output is correct
4 Execution timed out 1073 ms 156816 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 214616 KB Output is correct
2 Correct 80 ms 214324 KB Output is correct
3 Correct 74 ms 214524 KB Output is correct
4 Correct 73 ms 214732 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 212492 KB Output is correct
2 Correct 67 ms 212524 KB Output is correct
3 Correct 68 ms 212536 KB Output is correct
4 Correct 67 ms 212736 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 66 ms 212556 KB Output is correct
9 Correct 78 ms 214216 KB Output is correct
10 Correct 76 ms 213988 KB Output is correct
11 Correct 76 ms 213940 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 4 ms 1748 KB Output is correct
14 Correct 30 ms 1872 KB Output is correct
15 Correct 29 ms 1900 KB Output is correct
16 Correct 122 ms 242048 KB Output is correct
17 Execution timed out 1073 ms 156816 KB Time limit exceeded
18 Halted 0 ms 0 KB -