oj.uz

Submission #906235

# Submission time Handle Problem Language Result Execution time Memory
906235 2024-01-13T20:10:49 Z n3rm1n Kitchen (BOI19_kitchen) C++17
30 / 100
 42 ms 108120 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 305, MAXH = 90005;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
int a[MAXN], b[MAXN];
int diverse = 0, hours = 0;
int max_used = 0;
void read()
{
    cin >> n >> m >> k;
    int no = 0;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        hours += a[i];
        if(a[i] < k)no = 1;
    }
    diverse = k * n;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> b[i];
        max_used += b[i];
    }
    if(no == 1)
    {
        cout << "Impossible" << endl;
        exit(0);
    }
   // cout << hours << " " << diverse << " " << max_used << endl;
}
int dp[MAXN][MAXH/**the number of used hours*/];
void solve()
{
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= m; ++ i)
    {
        dp[i][0] = 0;
        for (int j = 0; j <= max_used; ++ j)
        {
            //if(dp[i][j] == 0)continue;
            if(dp[i][j] < dp[i-1][j])dp[i][j] = max(dp[i][j], dp[i-1][j]);
            int adding = min(b[i], n);
            if(j >= b[i])
            {
                int neww = dp[i-1][j - b[i]] + adding;
            //if(i == 1 && j == 130)cout << "* " << neww << endl;
            dp[i][j] = max(dp[i][j], neww);
            }
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    //cout << dp[m][130] << endl;
    for (int i = hours; i <= max_used; ++ i)
    {
       //cout << i << " " << dp[m][i] << endl;
        if(dp[m][i] >= diverse)
        {
            cout << i-hours << endl;
            return;
        }
    }
    cout << "Impossible" << endl;
}
int main()
{
    speed();

    read();
    solve();
    return 0;
}
/***
4--
4 2 1
12 43 61 11
98 130
3--
4 2 1
12 43 61 11
130 168

*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 107868 KB Output is correct
2 Correct 18 ms 107864 KB Output is correct
3 Correct 18 ms 107708 KB Output is correct
4 Correct 18 ms 107868 KB Output is correct
5 Correct 18 ms 107868 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 18 ms 107864 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 107868 KB Output is correct
2 Correct 18 ms 107864 KB Output is correct
3 Correct 18 ms 107708 KB Output is correct
4 Correct 18 ms 107868 KB Output is correct
5 Correct 18 ms 107868 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 18 ms 107864 KB Output is correct
9 Correct 20 ms 107868 KB Output is correct
10 Correct 18 ms 107868 KB Output is correct
11 Correct 17 ms 107868 KB Output is correct
12 Correct 18 ms 107868 KB Output is correct
13 Incorrect 18 ms 107664 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 108120 KB Output is correct
2 Correct 18 ms 107868 KB Output is correct
3 Correct 18 ms 107868 KB Output is correct
4 Correct 17 ms 107868 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 20 ms 107868 KB Output is correct
2 Correct 18 ms 107864 KB Output is correct
3 Correct 18 ms 107708 KB Output is correct
4 Correct 18 ms 107868 KB Output is correct
5 Correct 18 ms 107868 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 18 ms 107864 KB Output is correct
9 Correct 20 ms 107868 KB Output is correct
10 Correct 18 ms 107868 KB Output is correct
11 Correct 17 ms 107868 KB Output is correct
12 Correct 18 ms 107868 KB Output is correct
13 Incorrect 18 ms 107664 KB Output isn't correct
14 Halted 0 ms 0 KB -