oj.uz

Submission #1099624

# Submission time Handle Problem Language Result Execution time Memory
1099624 2024-10-11T20:33:08 Z andrei_iorgulescu Kitchen (BOI19_kitchen) C++14
52 / 100
 1000 ms 129248 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];
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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 106576 KB Output is correct
2 Correct 46 ms 106572 KB Output is correct
3 Correct 44 ms 106576 KB Output is correct
4 Correct 45 ms 106580 KB Output is correct
5 Correct 42 ms 106580 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 106576 KB Output is correct
2 Correct 46 ms 106572 KB Output is correct
3 Correct 44 ms 106576 KB Output is correct
4 Correct 45 ms 106580 KB Output is correct
5 Correct 42 ms 106580 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 51 ms 107720 KB Output is correct
10 Correct 51 ms 107588 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 55 ms 107644 KB Output is correct
13 Correct 144 ms 107804 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 129248 KB Output is correct
2 Execution timed out 1048 ms 126292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 109904 KB Output is correct
2 Correct 59 ms 109908 KB Output is correct
3 Correct 89 ms 109756 KB Output is correct
4 Correct 109 ms 110004 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 106576 KB Output is correct
2 Correct 46 ms 106572 KB Output is correct
3 Correct 44 ms 106576 KB Output is correct
4 Correct 45 ms 106580 KB Output is correct
5 Correct 42 ms 106580 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 51 ms 107720 KB Output is correct
10 Correct 51 ms 107588 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 55 ms 107644 KB Output is correct
13 Correct 144 ms 107804 KB Output is correct
14 Correct 886 ms 129248 KB Output is correct
15 Execution timed out 1048 ms 126292 KB Time limit exceeded
16 Halted 0 ms 0 KB -