Submission #243085

#	Time	Username	Problem	Language	Result	Execution time	Memory
243085		dynam1c	Kitchen (BOI19_kitchen)	C++17	100 / 100	92 ms	896 KiB

kitchen

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define loopinc(i, a, b, inc) for(int i = a; i < (b); i += inc)
#define loop(i, a, b) for(int i = a; i < (b); i++)
#define rep(i, n) loop(i, 0, n)
#define rrep(i, n) for (int i = n-1; i >= 0; i--)
#define endl "\n"
#define all(c) (c).begin(),(c).end()
#define lloopinc(i, a, b, inc) for(ll i = a; i < (b); i += inc)
#define lloop(i, a, b) for(ll i = a; i < (b); i++)
#define lrep(i, n) lloop(i, 0, n)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tuple<int, int, int> tiii;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, k;
	cin >> n >> m >> k;
	vi meals(n);
	vi chefs(m);
	rep(i, n) cin >> meals[i];
	rep(i, m) cin >> chefs[i];

	rep(i, n) if (meals[i] < k) {
		cout << "Impossible\n";
		return 0;
	}

	vi arr(301*301, -1);
	arr[0] = 0;
	rep(i, m) rrep(j, arr.size()) if (arr[j] != -1) arr[j+chefs[i]] = max(arr[j+chefs[i]], arr[j] + min(chefs[i], n));

	int s = 0;
	rep(i, n) s += meals[i];
	loop(i, s, arr.size()) if (arr[i] >= n*k) {
		cout << i-s << endl;
		return 0;
	}
	cout << "Impossible\n";
}

Compilation message (stderr)

kitchen.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
kitchen.cpp: In function 'int main()':
kitchen.cpp:10:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define loop(i, a, b) for(int i = a; i < (b); i++)
                                        ^
kitchen.cpp:73:2: note: in expansion of macro 'loop'
  loop(i, s, arr.size()) if (arr[i] >= n*k) {
  ^~~~

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