Submission #1099630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099630		andrei_iorgulescu	Kitchen (BOI19_kitchen)	C++14	100 / 100	87 ms	132172 KiB

kitchen

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m, m1, m2, k;
int a[305], b[305];
int b1[305], b2[305];
int s;
 
bool pot1[305][90005];
int f2[305][90005];
 
void dps()
{
    pot1[0][0] = true;
    for (int i = 1; i <= m1; i++)
    {
        for (int j = 0; j <= 90000; j++)
        {
            pot1[i][j] = pot1[i - 1][j];
            if (j - b1[i] >= 0)
                pot1[i][j] |= pot1[i - 1][j - b1[i]];
        }
    }
    for (int i = 0; i <= 300; i++)
        for (int j = 0; j <= 90000; j++)
            f2[i][j] = -1;
    f2[0][0] = 0;
    for (int i = 1; i <= m2; i++)
    {
        for (int j = 0; j <= 90000; j++)
        {
            f2[i][j] = f2[i - 1][j];
            if (j - b2[i] >= 0)
                if (f2[i - 1][j - b2[i]] != -1)
                    f2[i][j] = max(f2[i][j], 1 + f2[i - 1][j - b2[i]]);
        }
    }
}
 
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], s += a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    for (int i = 1; i <= m; i++)
    {
        if (b[i] <= n)
            b1[++m1] = b[i];
        else
            b2[++m2] = b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] < k)
        {
            cout << "Impossible";
            return 0;
        }
    }
    int sss1 = 0, sss2 = 0;
    for (int i = 1; i <= m; i++)
        sss1 += b[i], sss2 += min(b[i], n);
    if (sss1 < s or sss2 < n * k)
    {
        cout << "Impossible";
        return 0;
    }
    int ans = 1e9;
    dps();
    set<int> www;
    int uu = 1e9;
    for (int s1 = 0; s1 <= 90000; s1++)
    {
        if (!pot1[m1][s1])
            continue;
        int new_uu;
        if (s1 >= n * k)
            new_uu = 0;
        else
            new_uu = (n * k - s1) / n + min(1, (n * k - s1) % n);
        if (new_uu < uu)
        {
            for (int i = 0; i <= 90000; i++)
            {
                if (f2[m2][i] != -1 and f2[m2][i] >= new_uu and f2[m2][i] < uu)
                    www.insert(i);
            }
        }
        uu = new_uu;
        if (www.lower_bound(s - s1) == www.end())
            continue;
        int vll = *www.lower_bound(s - s1);
        ans = min(ans, s1 + vll - s);
    }
    cout << ans;
    return 0;
}
 
/**
imi fac pot1 si f2, apoi for prin i de la 0 la V^2 din pot1, imi mentin setul de i cu f2[i] >= cur si vad acolo un lower_bound
**/

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