oj.uz

Submission #771547

# Submission time Handle Problem Language Result Execution time Memory
771547 2023-07-03T06:16:56 Z Wael Kitchen (BOI19_kitchen) C++14
52 / 100
 159 ms 262144 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];
int 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 97 ms 214092 KB Output is correct
2 Correct 90 ms 213844 KB Output is correct
3 Correct 92 ms 214456 KB Output is correct
4 Correct 92 ms 215164 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 95 ms 213816 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 214092 KB Output is correct
2 Correct 90 ms 213844 KB Output is correct
3 Correct 92 ms 214456 KB Output is correct
4 Correct 92 ms 215164 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 95 ms 213816 KB Output is correct
9 Correct 108 ms 227352 KB Output is correct
10 Correct 108 ms 226052 KB Output is correct
11 Correct 96 ms 215212 KB Output is correct
12 Correct 3 ms 1748 KB Output is correct
13 Correct 3 ms 1748 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1884 KB Output is correct
2 Correct 32 ms 1936 KB Output is correct
3 Runtime error 159 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 220404 KB Output is correct
2 Correct 109 ms 218288 KB Output is correct
3 Correct 98 ms 219856 KB Output is correct
4 Correct 98 ms 221200 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 97 ms 214092 KB Output is correct
2 Correct 90 ms 213844 KB Output is correct
3 Correct 92 ms 214456 KB Output is correct
4 Correct 92 ms 215164 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 95 ms 213816 KB Output is correct
9 Correct 108 ms 227352 KB Output is correct
10 Correct 108 ms 226052 KB Output is correct
11 Correct 96 ms 215212 KB Output is correct
12 Correct 3 ms 1748 KB Output is correct
13 Correct 3 ms 1748 KB Output is correct
14 Correct 30 ms 1884 KB Output is correct
15 Correct 32 ms 1936 KB Output is correct
16 Runtime error 159 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -