Submission #620803

#	Time	Username	Problem	Language	Result	Execution time	Memory
620803		wiwiho	Packing Biscuits (IOI20_biscuits)	C++14	12 / 100	1143 ms	1061424 KiB

biscuits

#include "biscuits.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

const int K = 60;
long long count_tastiness(ll x, vector<ll> a){
    
    a.resize(K);
    vector<ll> ex(K);
    for(int i = 0; i < K; i++){
        ex[i] += a[i];
        if(i + 1 < K) ex[i + 1] += ex[i] / 2;
    }

    vector<ll> dp(K * x + 1);
    for(int i = 0; i <= K * x; i++){
        if(ex[K - 1] - i >= x) dp[i] = 2;
        else dp[i] = 1;
    }

    for(int i = K - 2; i >= 0; i--){
        vector<ll> dp2(K * x + 1);
        for(int j = 0; j <= K * x; j++){
            ll r = ex[i] - j;

            ll tmp = r / 2 + a[i + 1];
            tmp = ex[i + 1] - tmp;
            if(0 <= tmp && tmp <= K * x) dp2[j] += dp[tmp];

            if(r >= x){
                tmp = (r - x) / 2 + a[i + 1];
                tmp = ex[i + 1] - tmp;
                if(0 <= tmp && tmp <= K * x) dp2[j] += dp[tmp];
            }
        }
        dp.swap(dp2);
    }

    return dp[0];
}

• Subtask 1: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23