Submission #620690

#	Time	Username	Problem	Language	Result	Execution time	Memory
620690		wiwiho	Packing Biscuits (IOI20_biscuits)	C++14	21 / 100	1086 ms	63272 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 << ')';
}

vector<ll> a;
const int K = 60;
map<pll, ll> tmp;
ll x;

ll f(ll now, ll v){
    if(now == K - 1){
        if(v >= x) return 2;
        else return 1;
    }
    if(tmp.find(mp(now, v)) != tmp.end()) return tmp[mp(now, v)];
    
    ll ans = f(now + 1, a[now + 1] + v / 2);
    if(v >= x){
        ans += f(now + 1, a[now + 1] + (v - x) / 2);
    }
    
    tmp[mp(now, v)] = ans;
    return ans;
}

long long count_tastiness(long long _x, vector<long long> _a){
    
    _a.resize(K);
    a = _a;
    x = _x;
    tmp.clear();

	return f(0, a[0]);
}

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