oj.uz

Submission #493003

# Submission time Handle Problem Language Result Execution time Memory
493003 2021-12-10T02:15:05 Z Haruto810198 Kitchen (BOI19_kitchen) C++17
9 / 100
 90 ms 40900 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 = 4510;
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 2892 KB Output is correct
2 Correct 3 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2892 KB Output is correct
2 Correct 3 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 78 ms 20176 KB Output is correct
10 Correct 80 ms 20052 KB Output is correct
11 Correct 85 ms 20120 KB Output is correct
12 Correct 82 ms 20168 KB Output is correct
13 Runtime error 84 ms 38556 KB Execution killed with signal 11

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 38036 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 90 ms 40900 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 2892 KB Output is correct
2 Correct 3 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 78 ms 20176 KB Output is correct
10 Correct 80 ms 20052 KB Output is correct
11 Correct 85 ms 20120 KB Output is correct
12 Correct 82 ms 20168 KB Output is correct
13 Runtime error 84 ms 38556 KB Execution killed with signal 11