oj.uz

Submission #906234

# Submission time Handle Problem Language Result Execution time Memory
906234 2024-01-13T20:09:10 Z n3rm1n Kitchen (BOI19_kitchen) C++17
30 / 100
 41 ms 108116 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)
    {
        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 107856 KB Output is correct
2 Correct 18 ms 107864 KB Output is correct
3 Correct 18 ms 108000 KB Output is correct
4 Correct 18 ms 107868 KB Output is correct
5 Correct 18 ms 107868 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 18 ms 107664 KB Output is correct

Subtask #2
0 / 22.0

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

Subtask #3
0 / 20.0

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