oj.uz

Submission #701017

# Submission time Handle Problem Language Result Execution time Memory
701017 2023-02-19T18:13:26 Z ghostwriter Kitchen (BOI19_kitchen) C++17
100 / 100
 87 ms 106268 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ers erase
#define bg begin
#define ed end
#define ft front
#define bk back
#define mtp make_tuple
#define sz(x) (int)(x).size()
#define all(x) (x).bg(), (x).ed()
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
const int oo = 1e9 + 5;
const int N = 305;
const int M = 305;
const int NxN = 300 * 300 + 5;
int n, m, k, a[N], b[N], total = 0;
bool check() {
    FOR(i, 1, n)
        if (a[i] < k)
            return 0;
    int sum = 0, sum1 = 0;
    FOR(i, 1, m) {
        sum += min(b[i], n);
        sum1 += b[i];
    }
    return sum >= n * k && sum1 >= total;
}
namespace subtask12 {
    void solve() {
        int rs = oo;
        FOR(j, 0, (1 << m) - 1) {
            int sum = 0, sum1 = 0;
            FRN(i, m) {
                if (!(j & (1 << i))) continue;
                sum += min(b[i + 1], n);
                sum1 += b[i + 1];
            }
//            cerr << "DB>> " << j << " : " << sum << ' ' << sum1 << '\n';
            if (sum >= n * k && sum1 >= total) rs = min(rs, sum1 - total);
        }
        cout << rs << '\n';
    }
}
namespace subtask3 {
    int d[N][NxN];
    void solve() {
        d[0][0] = 1;
        FOR(i, 1, m)
        FOR(j, 0, m * 300) {
            d[i][j] = d[i - 1][j];
            if (j >= b[i]) d[i][j] = d[i][j] || d[i - 1][j - b[i]];
        }
        FOR(i, total, m * 300)
            if (d[m][i]) {
                cout << i - total << '\n';
                return;
            }
    }
}
namespace subtask45 {
    int d[N][NxN], d1[N][NxN], f[N];
    vi b1, b2;
    void solve() {
        FOR(i, 1, m)
            if (b[i] < n) b1.pb(b[i]);
            else b2.pb(b[i]);
        reverse(all(b1));
        b1.pb(0);
        reverse(all(b1));
        reverse(all(b2));
        b2.pb(0);
        reverse(all(b2));
        d[0][0] = 1;
        FOR(i, 1, sz(b1) - 1)
        FOR(j, 0, m * 300) {
            d[i][j] = d[i - 1][j];
            if (j >= b1[i]) d[i][j] = d[i][j] || d[i - 1][j - b1[i]];
        }
        FOR(i, 1, m * 300) d1[0][i] = -oo;
        FOR(i, 1, sz(b2) - 1)
        FOR(j, 0, m * 300) {
            d1[i][j] = d1[i - 1][j];
            if (j >= b2[i]) d1[i][j] = max(d1[i][j], d1[i - 1][j - b2[i]] + 1);
        }
        memset(f, -1, sizeof f);
        int rs = oo, pt = m * 300;
        FOR(fs, 0, m * 300) {
            if (!d[sz(b1) - 1][fs]) continue;
//            cerr << "DB>> " << fs << '\n';
            if (fs >= total) rs = min(rs, fs - total);
            else {
                int need = total - fs, need1 = 0;
                WHILE(pt >= need) {
                    if (d1[sz(b2) - 1][pt] >= 0) f[d1[sz(b2) - 1][pt]] = pt;
                    --pt;
                }
                if (fs < n * k) need1 = (n * k - fs + n - 1) / n;
                int rs1 = oo;
                FOR(j, need1, m) {
                    if (f[j] == -1) continue;
                    rs1 = min(rs1, f[j]);
                }
//                cerr << "DB>> " << fs << ' ' << rs1 << '\n';
                rs = min(rs, fs + rs1 - total);
            }
        }
        cout << rs << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin >> n >> m >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, m) cin >> b[i];
    FOR(i, 1, n) total += a[i];
    if (!check()) {
        cout << "Impossible\n";
        return 0;
    }
    if (m <= 15) {
        subtask12::solve();
        return 0;
    }
    if (k == 1) {
        subtask3::solve();
        return 0;
    }
    subtask45::solve();
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 3 ms 212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 81376 KB Output is correct
2 Correct 54 ms 61244 KB Output is correct
3 Correct 67 ms 106020 KB Output is correct
4 Correct 68 ms 105920 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 36 ms 51916 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 4 ms 2388 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 71 ms 81376 KB Output is correct
15 Correct 54 ms 61244 KB Output is correct
16 Correct 67 ms 106020 KB Output is correct
17 Correct 68 ms 105920 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 36 ms 51916 KB Output is correct
20 Correct 2 ms 2388 KB Output is correct
21 Correct 2 ms 2388 KB Output is correct
22 Correct 4 ms 2388 KB Output is correct
23 Correct 2 ms 2388 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 42 ms 53180 KB Output is correct
26 Correct 54 ms 70920 KB Output is correct
27 Correct 25 ms 31180 KB Output is correct
28 Correct 57 ms 71436 KB Output is correct
29 Correct 56 ms 75020 KB Output is correct
30 Correct 87 ms 106268 KB Output is correct