oj.uz

Submission #567276

# Submission time Handle Problem Language Result Execution time Memory
567276 2022-05-23T09:57:51 Z Rifal Kitchen (BOI19_kitchen) C++14
31 / 100
 1000 ms 7108 KB 
#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 32768
#define INF 100000000
//#define ll long long
//#define cin fin
//#define cout fout
using namespace std;
//ofstream fout("convention.out");
//ifstream fin("convention.in");
const int M = 9e4 + 5;
const int N = 300 + 5;
int n, m, k;
pair<bool,int> dp[M][N] = {};
void add(int x)
{
    for(int i = M-1; i >= x; i--)
    {
        for(int j = 1; j < N; j++)
        {
            if(dp[i-x][j-1].first)
            {
                dp[i][j].first = 1;
                if(x >= k)
                    dp[i][j].second += dp[i-x][j-1].second+1;
                else
                    dp[i][j].second = dp[i-x][j-1].second;

            }
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    int meal[n], chef[m];
    dp[0][0].first = 1;
    long long sum = 0;
    bool ok = true;
    for(int i = 0; i < n; i++)
    {
        cin >> meal[i];
        if(meal[i] < k)
            ok = false;
        sum += meal[i];
    }
    for(int i = 0; i < m; i++)
    {
        cin >> chef[i];
        add(chef[i]);
    }
    if(m < k || ok == false)
    {
        cout << "Impossible";
        return 0;
    }

    for(int i = sum; i < M; i++)
    {
        for(int j = k; j < N; j++)
        {
            if(dp[i][j].first == 1 && dp[i][j].second >= k)
            {
                cout << i-sum;
                return 0;
            }
        }
    }

    cout << "Impossible";
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 724 KB Output is correct
2 Correct 103 ms 704 KB Output is correct
3 Correct 124 ms 704 KB Output is correct
4 Correct 97 ms 804 KB Output is correct
5 Correct 87 ms 772 KB Output is correct
6 Correct 75 ms 624 KB Output is correct
7 Correct 100 ms 628 KB Output is correct
8 Correct 96 ms 712 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 724 KB Output is correct
2 Correct 103 ms 704 KB Output is correct
3 Correct 124 ms 704 KB Output is correct
4 Correct 97 ms 804 KB Output is correct
5 Correct 87 ms 772 KB Output is correct
6 Correct 75 ms 624 KB Output is correct
7 Correct 100 ms 628 KB Output is correct
8 Correct 96 ms 712 KB Output is correct
9 Correct 422 ms 6368 KB Output is correct
10 Correct 527 ms 2196 KB Output is correct
11 Correct 440 ms 992 KB Output is correct
12 Correct 481 ms 1112 KB Output is correct
13 Correct 402 ms 7108 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 724 KB Output is correct
2 Correct 103 ms 704 KB Output is correct
3 Correct 124 ms 704 KB Output is correct
4 Correct 97 ms 804 KB Output is correct
5 Correct 87 ms 772 KB Output is correct
6 Correct 75 ms 624 KB Output is correct
7 Correct 100 ms 628 KB Output is correct
8 Correct 96 ms 712 KB Output is correct
9 Correct 422 ms 6368 KB Output is correct
10 Correct 527 ms 2196 KB Output is correct
11 Correct 440 ms 992 KB Output is correct
12 Correct 481 ms 1112 KB Output is correct
13 Correct 402 ms 7108 KB Output is correct
14 Execution timed out 1085 ms 1948 KB Time limit exceeded
15 Halted 0 ms 0 KB -