Submission #124860

#	Time	Username	Problem	Language	Result	Execution time	Memory
124860		khsoo01	Kitchen (BOI19_kitchen)	C++11	100 / 100	30 ms	1528 KiB

kitchen

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

const int N = 305, inf = 1e9;

int n, mt, m[2], k, s, a[2][N], dt[2][N*N], mn[N*N], ans = inf;

void boom () {
	puts("Impossible");
	exit(0);
}

int main()
{
	scanf("%d%d%d",&n,&mt,&k);
	for(int i=1;i<=n;i++) {
		int T;
		scanf("%d",&T);
		if(T < k) boom();
		s += T;
	}
	for(int i=1;i<=mt;i++) {
		int T;
		scanf("%d",&T);
		int I = (T >= n);
		a[I][++m[I]] = T;
	}
	for(int x=0;x<2;x++) {
		fill(dt[x] + 1, dt[x] + N*N, -inf);
		for(int i=1;i<=m[x];i++) {
			for(int j=N*N-1;j>=a[x][i];j--) {
				dt[x][j] = max(dt[x][j], dt[x][j-a[x][i]] + 1);
			}
		}
	}
	for(int i=N*N,j=N*N;i--;) {
		if(dt[0][i] >= 0) j = i;
		mn[i] = j;
	}
	for(int i=0;i<N*N;i++) {
		if(dt[1][i] < 0) continue;
		int X = max({0, s - i, (k - dt[1][i]) * n});
		if(mn[X] == N*N) continue;
		ans = min(ans, i + mn[X]);
	}
	if(ans == inf) boom();
	printf("%d\n", ans - s);
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&mt,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
kitchen.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~
kitchen.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~

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