oj.uz

Submission #493005

# Submission time Handle Problem Language Result Execution time Memory
493005 2021-12-10T02:16:11 Z Haruto810198 Kitchen (BOI19_kitchen) C++17
31 / 100
 117 ms 46432 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 4810;
const int C = 300;

int n, m, lim; // meals, chefs, required chefs
int meal[MAX], chef[MAX], meal_sum;
bool dp[MAX][MAX]; // dp(chefs)[sum(min(n, chef[j]))][sum(chef[j])]
int res;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>lim;
	FOR(i, 1, n, 1){
		cin>>meal[i];
		meal_sum += meal[i];
	}
	FOR(i, 1, m, 1){
		cin>>chef[i];
	}

	// meal[i] >= lim
	FOR(i, 1, n, 1){
		if(meal[i] < lim){
			cout<<"Impossible"<<'\n';
			return 0;
		}
	}

	// dp
	dp[0][0] = 1;

	FOR(i, 1, m, 1){
		for(int j = i*C; j >= 0; j--){
			int jj = j + min(n, chef[i]);
			for(int k = i*C; k >= 0; k--){
				int kk = k + chef[i];
				dp[jj][kk] |= dp[j][k];
			}
		}
		/*	
		FOR(j, 0, 10, 1){
			cerr<<"dp["<<j<<"] = ";
			FOR(k, 0, 10, 1){
				cerr<<dp[j][k]<<" ";
			}
			cerr<<endl;
		}
		cerr<<endl;
		*/
	}
	
	res = INF;
	FOR(j, n*lim, m*C, 1){
		FOR(k, meal_sum, m*C, 1){
			if(dp[j][k]) res = min(res, k - meal_sum);
		}
	}

	if(res == INF) cout<<"Impossible"<<'\n';
	else cout<<res<<'\n';
	
	return 0;

}

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 2 ms 3020 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 2 ms 3020 KB Output is correct
9 Correct 90 ms 21480 KB Output is correct
10 Correct 87 ms 21484 KB Output is correct
11 Correct 83 ms 21500 KB Output is correct
12 Correct 81 ms 21444 KB Output is correct
13 Correct 71 ms 21636 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 43380 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 46432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3020 KB Output is correct
5 Correct 2 ms 3020 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 2 ms 3020 KB Output is correct
9 Correct 90 ms 21480 KB Output is correct
10 Correct 87 ms 21484 KB Output is correct
11 Correct 83 ms 21500 KB Output is correct
12 Correct 81 ms 21444 KB Output is correct
13 Correct 71 ms 21636 KB Output is correct
14 Runtime error 99 ms 43380 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -