Submission #900391

#	Time	Username	Problem	Language	Result	Execution time	Memory
900391		n3rm1n	Kitchen (BOI19_kitchen)	C++17	29 / 100	1050 ms	684 KiB

kitchen

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 305;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
int a[MAXN], b[MAXN];
int total = 0;
void read()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        total += a[i];
    }
    for (int i = 1; i <= m; ++ i)
        cin >> b[i];

    for (int i = 1; i <= n; ++ i)
    {
        if(a[i] < k)
        {
            cout << "Impossible" << endl;
            exit(0);
        }
    }

}
int taken[MAXN];
int p[MAXN], notused[MAXN];
int solve()
{
    memset(taken, 0, sizeof(taken));
    int left = total, sumup = 0;
    int ok = 0;

    for (int i = 1; i <= m; ++ i)
    {
        if(p[i])
        {
            notused[i] = b[i];
            for (int j = 1; j <= n; ++ j)
            {
                if(taken[j] < k && notused[i] > 0)
                {
                    taken[j] ++;
                    if(taken[j] == k)ok ++;
                    notused[i] --;
                    left --;
                }
            }
            sumup += notused[i];
        }
    }
    if(sumup < left || ok < n)return 1e9;
    else
    {

        return sumup - left;
    }
}
int ans = 1e9;
void gen(int pos)
{
    if(pos > m)
    {
        ans = min(ans, solve());
        return;
    }
    p[pos] = 0;
    gen(pos+1);
    p[pos] = 1;
    gen(pos+1);
}
int dp[MAXN * MAXN + MAXN * MAXN];
void solve_k1()
{
    dp[0] = 1;
    for (int i = 1; i <= m; ++ i)
    {
        for (int j = total; j >= 0; -- j)
            if(dp[j])dp[j+b[i]] = 1;
    }
    for (int i = total; i <= 2*total; ++ i)
    {
        if(dp[i])
        {
            cout << i - total << endl;
            exit(0);
        }
    }
    cout << "Impossible" << endl;
}
int main()
{
    speed();
    read();
    if(k == 1)
    {
        solve_k1();
        return 0;
    }
    gen(1);
    if(ans == 1e9)cout << "Impossible" << endl;
    else cout << ans << endl;
    return 0;
}
/**
297 208 1
168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168
252 252 252 252 252 272 252 252 252 252 252 6 252 252 250 252 252 252 252 2 252 252 252 252 252 252 252 5 252 252 252 252 252 252 254 252 252 252 252 252 252 252 252 252 252 249 252 252 252 252 252 252 252 252 252 252 154 252 252 252 252 252 252 252 252 252 252 252 252 251 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 1 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 2 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 4 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 1 252 252 252 252 252 3 1 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 253 252 252 252 252 252

*/

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