This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int nmax = 120 + 5;
int k = 0;
vector<ll> a;
ll x;
unordered_map<ll, ll, custom_hash> dp[nmax];
ll bkt(int p, int accum) {
if(p > k && accum < x) return 1;
if(dp[p].count(accum)) return dp[p][accum];
return dp[p][accum] = bkt(p + 1, (a[p] + accum) / 2) + (a[p] + accum >= x? bkt(p + 1, (a[p] + accum - x) / 2) : 0);
}
long long count_tastiness(long long XXX, std::vector<long long> AAA) {
x = XXX;
a = AAA;
k = sz(a);
for(int i = 0; i < nmax; i++) dp[i].clear();
while(sz(a) < nmax) a.emplace_back(0);
return bkt(0, 0);
}
#undef int
/**
Anul asta se da centroid.
-- Surse oficiale
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |