Submission #780879

#TimeUsernameProblemLanguageResultExecution timeMemory
780879EliasPacking Biscuits (IOI20_biscuits)C++17
0 / 100
106 ms25128 KiB
#ifndef _DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define int long long #ifndef _DEBUG #include "biscuits.h" #endif #ifdef _DEBUG long long count_tastiness(long long x, std::vector<long long> a); #endif struct hash_pair { template <class T1, class T2> size_t operator()(const pair<T1, T2> &p) const { auto hash1 = hash<T1>{}(p.first); auto hash2 = hash<T2>{}(p.second); if (hash1 != hash2) { return hash1 ^ hash2; } // If hash1 == hash2, their XOR is zero. return hash1; } }; int X; vector<int> A; unordered_map<pair<int, int>, int, hash_pair> mem; int dp(int i, int carry) { if (carry < 0) return 0; if (i >= 60) return 1; if (mem.count({i, carry})) return mem[{i, carry}]; int available_here = (i >= A.size() ? 0 : A[i]) + carry / 2; return mem[{i, carry}] = dp(i + 1, available_here) + dp(i + 1, available_here - X); } long long count_tastiness(long long x, std::vector<long long> a) { X = x; A = a; return dp(0, 0); } #ifdef _DEBUG signed main() { int q; assert(scanf("%lld", &q) == 1); vector<int> k(q); vector<long long> x(q); vector<vector<long long>> a(q); vector<long long> results(q); for (int t = 0; t < q; t++) { assert(scanf("%lld%lld", &k[t], &x[t]) == 2); a[t] = vector<long long>(k[t]); for (int i = 0; i < k[t]; i++) { assert(scanf("%lld", &a[t][i]) == 1); } } fclose(stdin); for (int t = 0; t < q; t++) { results[t] = count_tastiness(x[t], a[t]); } for (int t = 0; t < q; t++) { printf("%lld\n", results[t]); } fclose(stdout); return 0; } #endif

Compilation message (stderr)

biscuits.cpp: In function 'long long int dp(long long int, long long int)':
biscuits.cpp:57:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  int available_here = (i >= A.size() ? 0 : A[i]) + carry / 2;
      |                        ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...