oj.uz

Submission #900391

# Submission time Handle Problem Language Result Execution time Memory
900391 2024-01-08T08:23:01 Z n3rm1n Kitchen (BOI19_kitchen) C++17
29 / 100
 1000 ms 684 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 305;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
int a[MAXN], b[MAXN];
int total = 0;
void read()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        total += a[i];
    }
    for (int i = 1; i <= m; ++ i)
        cin >> b[i];

    for (int i = 1; i <= n; ++ i)
    {
        if(a[i] < k)
        {
            cout << "Impossible" << endl;
            exit(0);
        }
    }

}
int taken[MAXN];
int p[MAXN], notused[MAXN];
int solve()
{
    memset(taken, 0, sizeof(taken));
    int left = total, sumup = 0;
    int ok = 0;

    for (int i = 1; i <= m; ++ i)
    {
        if(p[i])
        {
            notused[i] = b[i];
            for (int j = 1; j <= n; ++ j)
            {
                if(taken[j] < k && notused[i] > 0)
                {
                    taken[j] ++;
                    if(taken[j] == k)ok ++;
                    notused[i] --;
                    left --;
                }
            }
            sumup += notused[i];
        }
    }
    if(sumup < left || ok < n)return 1e9;
    else
    {

        return sumup - left;
    }
}
int ans = 1e9;
void gen(int pos)
{
    if(pos > m)
    {
        ans = min(ans, solve());
        return;
    }
    p[pos] = 0;
    gen(pos+1);
    p[pos] = 1;
    gen(pos+1);
}
int dp[MAXN * MAXN + MAXN * MAXN];
void solve_k1()
{
    dp[0] = 1;
    for (int i = 1; i <= m; ++ i)
    {
        for (int j = total; j >= 0; -- j)
            if(dp[j])dp[j+b[i]] = 1;
    }
    for (int i = total; i <= 2*total; ++ i)
    {
        if(dp[i])
        {
            cout << i - total << endl;
            exit(0);
        }
    }
    cout << "Impossible" << endl;
}
int main()
{
    speed();
    read();
    if(k == 1)
    {
        solve_k1();
        return 0;
    }
    gen(1);
    if(ans == 1e9)cout << "Impossible" << endl;
    else cout << ans << endl;
    return 0;
}
/**
297 208 1
168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168 168
252 252 252 252 252 272 252 252 252 252 252 6 252 252 250 252 252 252 252 2 252 252 252 252 252 252 252 5 252 252 252 252 252 252 254 252 252 252 252 252 252 252 252 252 252 249 252 252 252 252 252 252 252 252 252 252 154 252 252 252 252 252 252 252 252 252 252 252 252 251 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 1 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 2 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 4 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 1 252 252 252 252 252 3 1 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 253 252 252 252 252 252

*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 7 ms 348 KB Output is correct
12 Correct 12 ms 348 KB Output is correct
13 Incorrect 94 ms 444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 8 ms 600 KB Output is correct
3 Correct 9 ms 604 KB Output is correct
4 Correct 15 ms 616 KB Output is correct
5 Correct 18 ms 684 KB Output is correct
6 Correct 13 ms 604 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 7 ms 348 KB Output is correct
12 Correct 12 ms 348 KB Output is correct
13 Incorrect 94 ms 444 KB Output isn't correct
14 Halted 0 ms 0 KB -