oj.uz

Submission #1100837

# Submission time Handle Problem Language Result Execution time Memory
1100837 2024-10-14T19:32:45 Z sofiefu Kitchen (BOI19_kitchen) C++14
100 / 100
 27 ms 2040 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vo vector
#define pb push_back
#define se second
#define fi first
#define all(v) v.begin(), v.end()
typedef vector<int> vi;
typedef pair<int, int> pii;

#define rep(i, a, b) for(int i=(a); i<b; i++)
#define pr1(x) cerr << #x << '=' << x << ' ';
//for google contests
#define umap unordered_map
#define uset unordered_set
#define repd(i, a, b) for(int i=(b-1); i >= a; i--)
void _pr(signed x) {cerr << x;}
void _pr(long long x) {cerr << x;}
void _pr(size_t x) {cerr << x;}
void _pr(double x) {cerr << x;}
void _pr(char x) {cerr << '\'' << x << '\'';}
void _pr(const char* x) {cerr << x;}
void _pr(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void _pr(const pair<T, V> &x);
template<typename T, typename V> void _pr(const pair<T, V> &x) {cerr << "\e[95m" << "[ "; _pr(x.first); cerr << ", "; _pr(x.second); cerr << "\e[95m" << ']';}
template<typename T> void _pr(const T &x) {int F=0; cerr << '{'; for(auto &i: x) cerr << (F++ ? ", " : ""), _pr(i); cerr << "\e[91m" << '}';}
template <typename T, typename... V> void _pr(T t, V... v) {_pr(t); if(sizeof...(v)) cerr << ", "; _pr(v...);}
#define pr(x...) cerr << "\e[91m" << __func__ << ':' << __LINE__ << " [" << #x << "] = ["; _pr(x); cerr << "\e[91m" << ']' << "\033[0m"  << endl;
mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){return uniform_int_distribution<int>(l, r)(mt_rng);}

//go for outline with ;, then details
int const inf = LLONG_MAX, mxn = 300;
int n, m, k, meal[mxn], mxhours[mxn], sum, ans = inf;

void fulsol(){
    int mxval = 90310; vo<pii> dp(mxval); dp[0] = {1, 0};
    rep(chef, 0, m){
        repd(i, 0, mxval){
            if(dp[i].fi){
                int nw = mxhours[chef]+i, uniqhours = dp[i].se+min(n, mxhours[chef]);
                if(nw < mxval){
                    dp[nw].fi = 1;
                    dp[nw].se = max(dp[nw].se, uniqhours);
                }
            }
        }
    }

    rep(i, sum, mxval) 
        if(dp[i].fi && dp[i].se>=k*n){
            ans = i-sum; break;
        }
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>k;
    rep(i, 0, n) {
        cin>>meal[i]; sum+=meal[i];
    }
    rep(i, 0, m) cin>>mxhours[i]; 
    rep(i, 0, n){
        if(meal[i] < k){
            cout << "Impossible"; exit(0);
        }
    }

    fulsol();
    if(ans == inf) cout << "Impossible";
    else cout << ans;
}

/*
subtask 1: case-analysis for m,k in {1, 2}
subtask 2: subset bruteforce, use bitmask. see that we can also get prev subtask if we create a function 
f(vi chefs, sumchefhours) that returns wasted time
subtask 3: subset sum and find biggest r=subsetsum such that r<=sumhours. time complexity: maxval*ppl = (maxA*n)*m <= 3e7 
subtask 4: dp[sum] = {a1, a2, ... , an} where a1 is how many chefs working on person 1. time: mxsum * chefs * dishes = 40^4
subtask 5: dp[sum] = {x, y};
x = if it is reachable
y = maximum sum of hours we can get such that no person gets the same chef twice = sum of min(n, mxhours[i])} for all chefs i included
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1872 KB Output is correct
2 Correct 2 ms 1872 KB Output is correct
3 Correct 2 ms 1872 KB Output is correct
4 Correct 2 ms 1688 KB Output is correct
5 Correct 2 ms 1872 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 1860 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1872 KB Output is correct
2 Correct 2 ms 1872 KB Output is correct
3 Correct 2 ms 1872 KB Output is correct
4 Correct 2 ms 1688 KB Output is correct
5 Correct 2 ms 1872 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 1860 KB Output is correct
9 Correct 3 ms 1872 KB Output is correct
10 Correct 2 ms 1872 KB Output is correct
11 Correct 2 ms 1872 KB Output is correct
12 Correct 3 ms 2040 KB Output is correct
13 Correct 2 ms 1872 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1872 KB Output is correct
2 Correct 17 ms 1872 KB Output is correct
3 Correct 25 ms 1872 KB Output is correct
4 Correct 27 ms 1872 KB Output is correct
5 Correct 25 ms 1872 KB Output is correct
6 Correct 16 ms 1884 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1872 KB Output is correct
2 Correct 4 ms 1872 KB Output is correct
3 Correct 4 ms 1872 KB Output is correct
4 Correct 4 ms 1872 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1872 KB Output is correct
2 Correct 2 ms 1872 KB Output is correct
3 Correct 2 ms 1872 KB Output is correct
4 Correct 2 ms 1688 KB Output is correct
5 Correct 2 ms 1872 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 1860 KB Output is correct
9 Correct 3 ms 1872 KB Output is correct
10 Correct 2 ms 1872 KB Output is correct
11 Correct 2 ms 1872 KB Output is correct
12 Correct 3 ms 2040 KB Output is correct
13 Correct 2 ms 1872 KB Output is correct
14 Correct 26 ms 1872 KB Output is correct
15 Correct 17 ms 1872 KB Output is correct
16 Correct 25 ms 1872 KB Output is correct
17 Correct 27 ms 1872 KB Output is correct
18 Correct 25 ms 1872 KB Output is correct
19 Correct 16 ms 1884 KB Output is correct
20 Correct 8 ms 1872 KB Output is correct
21 Correct 4 ms 1872 KB Output is correct
22 Correct 4 ms 1872 KB Output is correct
23 Correct 4 ms 1872 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 15 ms 1872 KB Output is correct
26 Correct 18 ms 1872 KB Output is correct
27 Correct 13 ms 1884 KB Output is correct
28 Correct 20 ms 1872 KB Output is correct
29 Correct 21 ms 2040 KB Output is correct
30 Correct 27 ms 2040 KB Output is correct