Submission #701017

#	Time	Username	Problem	Language	Result	Execution time	Memory
701017		ghostwriter	Kitchen (BOI19_kitchen)	C++17	100 / 100	87 ms	106268 KiB

kitchen

#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 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28