oj.uz

Submission #345047

# Submission time Handle Problem Language Result Execution time Memory
345047 2021-01-07T00:26:31 Z ant101 Kitchen (BOI19_kitchen) C++14
100 / 100
 177 ms 206644 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
#define mp make_pair
#define f first
#define s second

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 3e2+5;
const ll INF = 1e18;
const ld PI = 4*atan((ld)1);
const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};


namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        // cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
        if (sz(s)) {
            setIn(s+".in");
            setOut(s+".out");
        } // for USACO
    }
}

using namespace io;

namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
    
    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class Arg, class... Args> void re(Arg& first, Args&... rest) {
        re(first); re(rest...);
    }
    
    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}

namespace output {
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T, size_t SZ> void pr(const array<T,SZ>& x);
    template<class T> void pr(const vector<T>& x);
    template<class T> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
    
    template<class T> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
        pr(first); pr(rest...);
    }
    
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{",x.f,", ",x.s,"}");
    }
    template<class T> void prContain(const T& x) {
        pr("{");
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool>
        pr("}");
    }
    template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    template<class T> void pr(const vector<T>& x) { prContain(x); }
    template<class T> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
    
    void ps() { pr("\n"); }
    template<class Arg> void ps(const Arg& first) {
        pr(first); ps(); // no space at end of line
    }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
        pr(first," "); ps(rest...); // print w/ spaces
    }
}

using namespace output;

using namespace input;

ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}

ll N, M, K;
ll mealtimes[MX];
ll dp[MX][MX*MX];
ll chefs[MX];

int main() {
//    ps(sizeof(dp)+sizeof(mealtimes)+sizeof(chefs));
    setIO();
    re(N, M, K);
    ll tmh = 0;
    F0R (i, N) {
        re(mealtimes[i]);
        if (mealtimes[i] < K) { // if we cannot even have K chefs on a certain dish then its legit impossible lmao
            ps("Impossible");
            return 0;
        }
        tmh+=mealtimes[i];
    }
    F0R (i, M) {
        re(chefs[i]);
    }
    // so lets see are we doing forward or backwards dp
    // our state is f(current index of the chefs array, sum of all the hours of the chefs that we have chosen)
    // value will be the value of max(sum(min(chefs[j], N))) over all used chefs j.
    // the idea is that in order to have K chefs on each dish, we need sum(min(chefs[j], N)) >= N*K
    // reason is because each chef can contribute to a maximum of N total dishes or less. We want the total contribution to be N*K, so each dish out of N can have K chefs on it
    // that reminds me i forgot about an edgecase :rhulkmoment:
    // if we let the minimum sum of all hours such that above condition is satisfied S, then the answer is S-tmh
    // so the answer will be the minimum value of (total of all mealtimes)-sum of all the hours of the chefs that we have chosen
    // this variant of dp is looking like knapsack
    // we will do forwards knapsack, in which case we must 1 index???
    // no i guess not
    // what are our initial conditions
    // I think leaving everything to 0 will suffice
    // nvm it doesnt
    F0R (i, M+1) {
        F0R (j, N*300+1) {
            dp[i][j] = -1e13;
        }
    }
    dp[0][0] = 0; // initial condition is that we start out with 0 total contribution
    F0R (i, M) {
        F0R (j, N*300+1) {
            if (dp[i][j] == -1e13) { // if its impossible then we dont care
                continue;
            }
//            ps(i, j, dp[i][j]);
            dp[i+1][j+chefs[i]] = max(dp[i+1][j+chefs[i]], dp[i][j]+min(chefs[i], N)); // first we try to include it in the subset of chefs
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]); // or we dont include it
        }
    }
    FOR (i, tmh, N*300+1) {
        if (dp[M][i] >= N*K) {
            ps(i-tmh);
            return 0;
        }
    }
    ps("Impossible");
    return 0;
}

Compilation message

kitchen.cpp: In function 'void io::setIn(std::string)':
kitchen.cpp:67:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
kitchen.cpp: In function 'void io::setOut(std::string)':
kitchen.cpp:68:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 1004 KB Output is correct
12 Correct 1 ms 1516 KB Output is correct
13 Correct 8 ms 11628 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 184172 KB Output is correct
2 Correct 121 ms 159596 KB Output is correct
3 Correct 168 ms 206644 KB Output is correct
4 Correct 177 ms 200172 KB Output is correct
5 Correct 177 ms 206572 KB Output is correct
6 Correct 117 ms 146924 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3180 KB Output is correct
2 Correct 3 ms 2924 KB Output is correct
3 Correct 3 ms 3948 KB Output is correct
4 Correct 4 ms 4460 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 1004 KB Output is correct
12 Correct 1 ms 1516 KB Output is correct
13 Correct 8 ms 11628 KB Output is correct
14 Correct 141 ms 184172 KB Output is correct
15 Correct 121 ms 159596 KB Output is correct
16 Correct 168 ms 206644 KB Output is correct
17 Correct 177 ms 200172 KB Output is correct
18 Correct 177 ms 206572 KB Output is correct
19 Correct 117 ms 146924 KB Output is correct
20 Correct 3 ms 3180 KB Output is correct
21 Correct 3 ms 2924 KB Output is correct
22 Correct 3 ms 3948 KB Output is correct
23 Correct 4 ms 4460 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 76 ms 99564 KB Output is correct
26 Correct 91 ms 114924 KB Output is correct
27 Correct 49 ms 57836 KB Output is correct
28 Correct 107 ms 122348 KB Output is correct
29 Correct 111 ms 119424 KB Output is correct
30 Correct 176 ms 199532 KB Output is correct