oj.uz

Submission #1099608

# Submission time Handle Problem Language Result Execution time Memory
1099608 2024-10-11T20:16:45 Z andrei_iorgulescu Kitchen (BOI19_kitchen) C++14
20 / 100
 73 ms 132692 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] <= 300)///!!!!
            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 = s; s1 <= 90000; s1++)///!!!!
    {
        if (!pot1[m1][s1])
            continue;
        else
            ans = min(ans, s1 - s);
        /*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(s - s1, 0); i <= 90000; i++)
            if (f2[m2][i] != -1 and s1 + f2[m2][i] * n >= 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:75:9: warning: unused variable 'uu' [-Wunused-variable]
   75 |     int uu = 1e9;
      |         ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106580 KB Output is correct
2 Correct 43 ms 106564 KB Output is correct
3 Correct 44 ms 106580 KB Output is correct
4 Incorrect 43 ms 106576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106580 KB Output is correct
2 Correct 43 ms 106564 KB Output is correct
3 Correct 44 ms 106580 KB Output is correct
4 Incorrect 43 ms 106576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 129364 KB Output is correct
2 Correct 64 ms 126188 KB Output is correct
3 Correct 70 ms 132692 KB Output is correct
4 Correct 73 ms 132656 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 58 ms 124600 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106580 KB Output is correct
2 Correct 43 ms 106564 KB Output is correct
3 Correct 44 ms 106580 KB Output is correct
4 Incorrect 43 ms 106576 KB Output isn't correct
5 Halted 0 ms 0 KB -