# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1005339 | rahidilbayramli | Kitchen (BOI19_kitchen) | C++17 | 19 ms | 1112 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll sz = 9e4+5;
ll dp[sz];
void solve()
{
ll n, m, k, sum = 0, sumb = 0, i, j;
cin >> n >> m >> k;
ll a[n+5], b[m+5];
for(i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
}
for(i = 1; i <= m; i++)
cin >> b[i];
sort(a+1, a+n+1);
sort(b+1, b+m+1);
if(m < k || a[1] < k)
cout << "Impossible\n";
else{
for(i = 1; i <= m; i++)
{
for(j = sz; j >= b[i]; j--)
{
if(j == b[i] || dp[j - b[i]])
dp[j] = max(dp[j], dp[j-b[i]] + min(b[i], n));
}
}
bool ok = false;
for(i = sum; i <= sz; i++)
{
if(dp[i] >= n * k && !ok)
{
cout << i - sum << "\n";
ok = true;
}
}
if(!ok)
cout << "Impossible\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll tests = 1;
//cin >> tests;
while(tests--)
{
solve();
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |