oj.uz

Submission #733926

# Submission time Handle Problem Language Result Execution time Memory
733926 2023-05-01T12:05:10 Z Vanilla Kitchen (BOI19_kitchen) C++17
51 / 100
 224 ms 3668 KB 
#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct custom_hash {static uint64_t splitmix64(uint64_t x) {x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
// string __fname = ""; ifstream in (__fname + ".in"); ofstream out (__fname + ".out"); 
// #define cin in 
// #define cout out
#define int64 long long
#define uint64 unsigned long long
#define x first
#define y second
#define pb push_back
#define pii pair <int, int> 
#define pii64 pair <int64, int64>
#define db(x) cout << "> " << #x << ": " << (x) << "\n"
#define qr queries()
#define yn(x) if (x) {ctn("Yes");}else {ctn("No");}
void solve(int);
void queries(){int n;cin >> n;for (int i = 1; i <= n; i++) solve(i);}
template<class T>T ceildiv(T a, T b) {return a / b + !!(a % b);}
template<class T>T gcd (T a, T b){return (b ? gcd(b, a % b): a);}
template<class T>T lcm (T a, T b){return a * b / gcd(a, b);}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
const int ddx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double pi = 3.14159265359;
const double eps = 1e-6;
const int64 hash_inv = 940594066;
const int64 hash_p = 101;
const int64 mod = 1e9 + 7;
const int maxn = 301;
const int maxs = maxn * maxn + 1;
bitset <maxs> dp [maxn];
int a[maxn];
int b[maxn];
int n,m,k;

void solve(int id){
    
    return;
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed; cout << setprecision(10); 
    cin >> n >> m >> k;
    int sa = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        sa+=a[i];
    }
    for (int i = 0; i < m; i++){
        cin >> b[i];
    }
    for (int i = 0; i < n; i++){
        if (a[i] < k) {
            cout << "Impossible";
            return 0;
        }
    }
    dp[0][0] = 1;
    for (int val: b) {
        if (val >= n) {
            for (int i = m - 1; i >= 0; i--) dp[i + 1] |= dp[i] << val;
        }
        else {
            for (int i = maxs - val - 1; i >= 0; i--){
                int r1 = min(i / n, m);
                int r2 = min((i + val) / n, m);
                if (dp[r1][i]) dp[r2][i + val] = 1;
            }
        }
    }
    for (int i = sa; i < maxs; i++){
        for (int j = k; j <= m; j++){
            if (dp[j][i]) {
                cout << i - sa;
                return 0;
            }
        }
    }
    cout << "Impossible\n";
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 364 KB Output is correct
2 Correct 206 ms 352 KB Output is correct
3 Correct 190 ms 340 KB Output is correct
4 Correct 192 ms 360 KB Output is correct
5 Correct 166 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 179 ms 352 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 364 KB Output is correct
2 Correct 206 ms 352 KB Output is correct
3 Correct 190 ms 340 KB Output is correct
4 Correct 192 ms 360 KB Output is correct
5 Correct 166 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 179 ms 352 KB Output is correct
9 Correct 199 ms 508 KB Output is correct
10 Correct 177 ms 496 KB Output is correct
11 Correct 178 ms 492 KB Output is correct
12 Correct 195 ms 344 KB Output is correct
13 Correct 157 ms 372 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 1152 KB Output is correct
2 Correct 186 ms 996 KB Output is correct
3 Correct 197 ms 3644 KB Output is correct
4 Correct 224 ms 3668 KB Output is correct
5 Correct 215 ms 3540 KB Output is correct
6 Correct 177 ms 892 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 788 KB Output is correct
2 Incorrect 167 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 364 KB Output is correct
2 Correct 206 ms 352 KB Output is correct
3 Correct 190 ms 340 KB Output is correct
4 Correct 192 ms 360 KB Output is correct
5 Correct 166 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 179 ms 352 KB Output is correct
9 Correct 199 ms 508 KB Output is correct
10 Correct 177 ms 496 KB Output is correct
11 Correct 178 ms 492 KB Output is correct
12 Correct 195 ms 344 KB Output is correct
13 Correct 157 ms 372 KB Output is correct
14 Correct 178 ms 1152 KB Output is correct
15 Correct 186 ms 996 KB Output is correct
16 Correct 197 ms 3644 KB Output is correct
17 Correct 224 ms 3668 KB Output is correct
18 Correct 215 ms 3540 KB Output is correct
19 Correct 177 ms 892 KB Output is correct
20 Correct 167 ms 788 KB Output is correct
21 Incorrect 167 ms 724 KB Output isn't correct
22 Halted 0 ms 0 KB -