oj.uz

Submission #1099600

# Submission time Handle Problem Language Result Execution time Memory
1099600 2024-10-11T19:58:03 Z andrei_iorgulescu Kitchen (BOI19_kitchen) C++14
0 / 100
 69 ms 129368 KB 
#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 <= s; 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 106328 KB Output is correct
2 Correct 40 ms 106328 KB Output is correct
3 Correct 43 ms 106320 KB Output is correct
4 Correct 43 ms 106316 KB Output is correct
5 Incorrect 44 ms 106580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 106328 KB Output is correct
2 Correct 40 ms 106328 KB Output is correct
3 Correct 43 ms 106320 KB Output is correct
4 Correct 43 ms 106316 KB Output is correct
5 Incorrect 44 ms 106580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 129368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 106836 KB Output is correct
2 Correct 49 ms 108116 KB Output is correct
3 Correct 50 ms 109900 KB Output is correct
4 Incorrect 52 ms 109908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 106328 KB Output is correct
2 Correct 40 ms 106328 KB Output is correct
3 Correct 43 ms 106320 KB Output is correct
4 Correct 43 ms 106316 KB Output is correct
5 Incorrect 44 ms 106580 KB Output isn't correct
6 Halted 0 ms 0 KB -