Submission #679890

#TimeUsernameProblemLanguageResultExecution timeMemory
679890peijarIce Hockey World Championship (CEOI15_bobek)C++17
100 / 100
189 ms16736 KiB
#include <bits/stdc++.h> #define int long long using namespace std; namespace std { template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) { out << "["; for (int i = 0; i < (int)vec.size(); ++i) { out << vec[i]; if (i + 1 < (int)vec.size()) out << ", "; } return out << "]"; } } // namespace std void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int N, budget; cin >> N >> budget; vector<int> L, R; for (int i = 0; i < N; ++i) { int x; cin >> x; if (i % 2) R.push_back(x); else L.push_back(x); } int szL = L.size(), szR = R.size(); vector<int> valL(1 << szL), valR(1 << szR); for (int msk = 0; msk < (1 << szL); ++msk) { for (int i = 0; i < szL; ++i) if ((1 << i) & msk) { valL[msk] = valL[msk ^ (1 << i)] + L[i]; break; } } sort(valL.begin(), valL.end()); for (int msk = 0; msk < (1 << szR); ++msk) { for (int i = 0; i < szR; ++i) if ((1 << i) & msk) { valR[msk] = valR[msk ^ (1 << i)] + R[i]; break; } } dbg(L, R); sort(valR.rbegin(), valR.rend()); dbg(valL); dbg(valR); int curL = 0; int sol = 0; for (int x : valR) { if (x > budget) continue; while (curL < (int)valL.size() and valL[curL] + x <= budget) ++curL; dbg(x, curL); sol += curL; } cout << sol << endl; }
#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...
#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...