Submission #1124386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124386		whoknow	Kitchen (BOI19_kitchen)	C++20	100 / 100	15 ms	584 KiB

kitchen

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 305
#define MAXSUM 90005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n, m, K;
int a[MAXN], b[MAXN];
namespace sub1
{
int sumA, sumB;
int dp[MAXSUM];
void solve()
{
    for(int i = 1; i <= n; i++)
    {
        if(a[i] < K)
            return cout << "Impossible", void();
        sumA += a[i];
    }
    for(int i = 1; i <= m; i++)
        sumB += b[i];
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i <= m; i++)
        for(int j = sumB; j >= b[i]; j--)
            dp[j] = max(dp[j], dp[j - b[i]] + min(b[i], n));
    for(int i = sumA; i <= sumB; i++)
        if(dp[i] >= n * K)
            return cout << i - sumA, void();
    cout << "Impossible";
}
}
main()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> K;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++)
        cin >> b[i];
    if(K > m)
        return cout << "Impossible", 0;
    sub1::solve();
}
/**
2 4 3
5 5
1 4 5 1

**/

Compilation message (stderr)

kitchen.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main()
      | ^~~~
kitchen.cpp: In function 'int main()':
kitchen.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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