Submission #1250996

#TimeUsernameProblemLanguageResultExecution timeMemory
1250996haiphong5g0Souvenirs (IOI25_souvenirs)C++20
4 / 100
1080 ms428 KiB
#include "souvenirs.h" #include <bits/stdc++.h> #define task "TEST" #define task2 "A" #define pl pair<ll, ll> #define pf push_front #define pb push_back #define pob pop_back #define pof pop_front #define mp make_pair #define fi first #define se second #define FOR(i, a, b, c) for (int i=a; i<=b; i+=c) #define FORE(i, a, b, c) for (int i=a; i>=b; i+=c) using namespace std; using ll = long long; using Knowledge = pair<vector<int>, ll>; using ull = unsigned long long; const int Mod = 998244353; const int maxn = 1e3; const ll Inf = 1e16; Knowledge res; ll P[maxn+1], num[maxn+1], n, A[maxn+1]; map <ll, Knowledge> Data; /*Knowledge transaction(ll val){ vector<int> a; a.clear(); ll sum = val; FOR(i, 0, n-1, 1) { if (sum >= A[i]) { a.pb(i); sum -= A[i]; } } return mp(a, sum); }*/ Knowledge Fix(Knowledge know) { FOR(i, 0, (ll)know.fi.size()-1, 1) { ll p = know.fi[i]; if (P[p] == 0) continue; know.fi.erase(know.fi.begin() + i); know.se -= P[p]; i--; } return know; } Knowledge Add(ll val) { //cerr << val << " "; res = transaction(val); for (auto p : res.fi) num[p]++; res.se = val - res.se; return res; } void Sub6(ll n) { priority_queue<ll, vector<ll>, greater<ll>> PQ; PQ.push(P[0] - 1); while (!PQ.empty()) { ll v = PQ.top(); PQ.pop(); if (!Data.count(v)) Data[v] = Add(v); Knowledge res = Fix(Data[v]); if (res.fi.size() == 1) { ll p = res.fi[0]; P[p] = res.se; if (P[p] != 0) continue; if (p + 1 < n and !P[p + 1]) PQ.push(P[p] + 1); } else if (res.fi.size() != 0) { PQ.push(v); PQ.push(res.se/res.fi.size()); } } FOR(i, 1, n-1, 1) FOR(j, num[i], i-1, 1) Add(P[i]); } void buy_souvenirs(int n, long long P0) { P[0] = P0; Sub6(n); } /*int main() { cin >> n; FOR(i, 0, n-1, 1) cin >> A[i]; buy_souvenirs(n, A[0]); FOR(i, 0, n-1, 1) cerr << num[i] << " "; }*/
#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...