Submission #1099707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099707		vjudge1	Kitchen (BOI19_kitchen)	C++17	100 / 100	57 ms	2144 KiB

kitchen

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const lli maxN =3e2 + 5;
lli f[maxN * maxN],g[maxN * maxN];
lli a[maxN],b[maxN],n,sum,m,k;
void input()
{
    cin >> n >> m >> k;
    sum = 0;
    for (lli i = 1;i <= n;++i)
    {
        cin >> a[i];
        sum += a[i];
    }
    for (lli i = 1;i <= m;++i) cin >> b[i];
    for (lli j = 1;j < maxN * maxN;++j) g[j] = -1e18;
    g[0] = 0;
}
void solve()
{
    for (lli i = 1;i <= n;++i) if (a[i] < k) {cout << "Impossible";return;}
    for (lli i = 1;i <= m;++i)
    {
        for (lli j = 0;j < maxN * maxN;++j)
        {
            f[j] = -1e18;
            if (j - b[i] >= 0 && g[j - b[i]] != -1e18) f[j] = g[j - b[i]] + min(b[i],n);
            f[j] = max(g[j],f[j]);
            //if (j == 10 && i == 4) cout << g[j] << " " << f[j] << "\n";
        }
        for (lli j = 0;j < maxN * maxN;++j)
        {
            g[j] = f[j];
        }
        //if (i == 1) cout << f[3] << "\n";
    }
    lli ans = 1e18;
    for (lli j = 1;j < maxN * maxN;++j)
    {
        if (j - sum >= 0 && f[j] >= n * k) ans = min(ans,j - sum);
    }
    if (ans == 1e18) cout << "Impossible";
    else cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("G.inp","r",stdin);
//    freopen("G.out","w",stdout);
    input();
    solve();
}
/*
4 4 1
1 2 3 4
2 3 4 2
*/

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28