oj.uz

Submission #642656

# Submission time Handle Problem Language Result Execution time Memory
642656 2022-09-20T10:16:39 Z aebov Kitchen (BOI19_kitchen) C++17
0 / 100
 18 ms 980 KB 
#include<iostream>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cstring>
#define ll long long
#define pb push_back
using namespace std;

ll inf = (ll)1e18 + 18;
const int N = 302;
ll int n, m, k , sum , sum2;
ll int a[N], b[N];
ll ans = inf;
ll dp[N*N + N + N + 2];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n; i ++){
		cin >> a[i], sum += a[i];
		if( a[i] < k){
			cout << "Impossible\n";
			return 0;
		}
	}
	for(int i = 1 ; i <= m; i ++) cin >> b[i], sum2 += b[i];
	if( sum2 < sum){
		cout << "Impossible\n";
		return 0;
	}
	sort(b + 1 , b + m + 1);
	memset(dp,-1,sizeof(dp));
	dp[0] = 0 ;
	for(int i = m ; i ; i--) {
        for(int j = N*N - b[i]  ; j >= 0; j--) {
            if(dp[j] != -1)dp[j + b[i]] = max(dp[j + b[i]] , dp[j] + min(n, b[i]));
        }
    }
	for(int i = sum; i <= N*N; i++){
		if(dp[i] >= n*k) cout << i-sum << "\n";
		return 0;
	}
	cout << "Impossible\n";
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

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