oj.uz

Submission #771548

# Submission time Handle Problem Language Result Execution time Memory
771548 2023-07-03T06:17:25 Z Wael Kitchen (BOI19_kitchen) C++14
52 / 100
 145 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 100 ms 214264 KB Output is correct
2 Correct 87 ms 213796 KB Output is correct
3 Correct 87 ms 214388 KB Output is correct
4 Correct 89 ms 215152 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 91 ms 213860 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 214264 KB Output is correct
2 Correct 87 ms 213796 KB Output is correct
3 Correct 87 ms 214388 KB Output is correct
4 Correct 89 ms 215152 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 91 ms 213860 KB Output is correct
9 Correct 105 ms 227244 KB Output is correct
10 Correct 105 ms 226008 KB Output is correct
11 Correct 97 ms 215276 KB Output is correct
12 Correct 3 ms 1748 KB Output is correct
13 Correct 2 ms 1748 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1916 KB Output is correct
2 Correct 29 ms 1872 KB Output is correct
3 Runtime error 145 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 125 ms 220400 KB Output is correct
2 Correct 108 ms 218248 KB Output is correct
3 Correct 99 ms 219856 KB Output is correct
4 Correct 98 ms 221192 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 214264 KB Output is correct
2 Correct 87 ms 213796 KB Output is correct
3 Correct 87 ms 214388 KB Output is correct
4 Correct 89 ms 215152 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 91 ms 213860 KB Output is correct
9 Correct 105 ms 227244 KB Output is correct
10 Correct 105 ms 226008 KB Output is correct
11 Correct 97 ms 215276 KB Output is correct
12 Correct 3 ms 1748 KB Output is correct
13 Correct 2 ms 1748 KB Output is correct
14 Correct 30 ms 1916 KB Output is correct
15 Correct 29 ms 1872 KB Output is correct
16 Runtime error 145 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -