Submission #921357

#	Time	Username	Problem	Language	Result	Execution time	Memory
921357		penguin133	Kitchen (BOI19_kitchen)	C++17	0 / 100	30 ms	220940 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int memo[305][305][605], A[305], B[305], dp2[305][305], n, m, k, mx, mn = 1e9, ans = 1e18, sm;

int dp(int x, int y, int cur){
	if(!y){
		return (cur >= mx ? cur * n - sm : 1e18);
	}
	if(x == m + 1)return 1e18;
	if(memo[x][y][cur] != -1)return memo[x][y][cur];
	if(cur >= mx){
		return memo[x][y][cur] = (dp2[x][y] + cur) * n - sm;
	}
	return memo[x][y][cur] = min(dp(x + 1, y, cur), dp(x + 1, y - 1, cur + B[x]));
}

void solve(){
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++)cin >> A[i], mx = max(mx, A[i]), sm += A[i], mn = min(mn, A[i]);
	if(mn < k){
		cout << "Impossible\n";
		return;
	}
	for(int i = 1; i <= m; i++)cin >> B[i];
	dp2[m+1][0] = 0;
	for(int i = 1; i <= m; i++)dp2[m+1][i] = 1e18;
	for(int i = m; i >= 1; i--){
		for(int j = 0; j <= m; j++){
			dp2[i][j] = min(dp2[i+1][j], (j ? dp2[i+1][j-1] + B[i] : (int)1e18));
		} 
	}
	memset(memo, -1, sizeof(memo));
	int res = dp(1, k, 0);
	if(res > 1e9)cout << "Impossible\n";
	else cout << res << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

kitchen.cpp:14:86: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | int memo[305][305][605], A[305], B[305], dp2[305][305], n, m, k, mx, mn = 1e9, ans = 1e18, sm;
      |                                                                                      ^~~~
kitchen.cpp: In function 'int dp(int, int, int)':
kitchen.cpp:20:23: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 |  if(x == m + 1)return 1e18;
      |                       ^~~~
kitchen.cpp: In function 'void solve()':
kitchen.cpp:37:43: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   37 |  for(int i = 1; i <= m; i++)dp2[m+1][i] = 1e18;
      |                                           ^~~~
kitchen.cpp: At global scope:
kitchen.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      | ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28