Submission #1099624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099624		andrei_iorgulescu	Kitchen (BOI19_kitchen)	C++14	52 / 100	1048 ms	129248 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];
bool pot2[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]];
        }
    }
    pot2[0][0] = true;
    for (int i = 1; i <= m2; i++)
    {
        for (int j = 0; j <= 90000; j++)
        {
            pot2[i][j] = pot2[i - 1][j];
            if (j - b2[i] >= 0)
                pot2[i][j] |= pot2[i - 1][j - b2[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;
    www.insert(0);
    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 = 1; 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);*/
        for (int i = max(0, s - s1); i <= 90000; i++)
            if (i + s1 >= s and f2[m2][i] != -1 and s1 + n * f2[m2][i] >= n * k)
            {
                ans = min(ans, i + s1 - s);
                break;
            }
    }
    if (ans >= (int)1e8)
        cout << "Impossible";
    else
        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
**/

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:86:9: warning: unused variable 'uu' [-Wunused-variable]
   86 |     int uu = 1e9;
      |         ^~

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