Submission #1253682

#TimeUsernameProblemLanguageResultExecution timeMemory
1253682zipdang04Festival (IOI25_festival)C++20
5 / 100
39 ms6080 KiB
#include "festival.h" #include <bits/stdc++.h> using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; */ typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template <class T> using PQMax = priority_queue<T>; template <class T> using PQMin = priority_queue<T, vector<T>, greater<T>>; template <class T1, class T2> void maximize(T1 &a, T2 b){ if (b > a) a = b; } template <class T1, class T2> void minimize(T1 &a, T2 b){ if (b < a) a = b; } template <class T> void read(T &number) { bool negative = false; register int c; number = 0; c = getchar(); while (c != '-' && !isalnum(c)) c = getchar(); if (c=='-'){ negative = true; c = getchar(); } for (; (c>47 && c<58); c=getchar()) number = number *10 + c - 48; if (negative) number *= -1; } template <class T, class ...Ts> void read(T &a, Ts& ... args){ read(a); read(args...); } /* struct Node { int node, len; Node() {node = len = 0;} Node(int node, int len) {this -> node = node, this -> len = len;} }; typedef vector<Node> vg; */ #define fi first #define se second #define FOR(type, i, a, b) for(type i = (a); i <= (b); i++) #define REV(type, i, b, a) for(type i = (b); i >= (a); i--) #define testBit(n, bit) (((n) >> (bit)) & 1) #define flipBit(n, bit) ((n) ^ (1ll << (bit))) #define cntBit(n) __builtin_popcount(n) #define cntBitll(n) __builtin_popcountll(n) #define log2(n) (31 - __builtin_clz(n)) #define log2ll(n) (63 - __builtin_clzll(n)) #define CURRENT_TIMESTAMP chrono::steady_clock::now().time_since_epoch().count() #define randomize mt19937_64 mt(CURRENT_TIMESTAMP) #define MAX 1000001 #define MOD 1000000007 #define oo 1'000'000'000'000'000'000ll struct Coupon { int idx; ll p, t; Coupon() {idx = p = t = 0;} Coupon(int idx, ll p, int t): idx(idx), p(p), t(t) {} }; ll A; int n; int P[MAX], T[MAX]; namespace Subtask123 { vector<int> prices[3]; vector<int> solve() { FOR(int, i, 1, n) prices[T[i]].push_back(i); FOR(int, type, 1, 2) sort(prices[type].begin(), prices[type].end(), [](int i, int j){ return P[i] < P[j]; }); vector<int> answer; int ptr[3] = {}; while (ptr[1] < prices[1].size() and ptr[2] < prices[2].size()) { ll newA1 = A - P[prices[1][ptr[1]]], newA2 = (A - P[prices[2][ptr[2]]]) * 2; // cerr << prices[1][ptr[1]] << ' ' << prices[2][ptr[2]] << ' ' << newA1 << ' ' << newA2 << '\n'; if (newA1 < 0 and newA2 < 0) break; if (newA2 >= newA1) A = newA2, answer.push_back(prices[2][ptr[2]++]); else A = newA1, answer.push_back(prices[1][ptr[1]++]); minimize(A, oo); } FOR(int, type, 1, 2) while (A > 0 and ptr[type] < prices[type].size()) { int i = prices[type][ptr[type]++]; if (A < P[i]) break; answer.push_back(i); A = (A - P[i]) * type; minimize(A, oo); } for (int &value: answer) value -= 1; return answer; } } namespace Subtask4 { int f[71][71][71][71]; int cnt[4]; vector<Coupon> prices; } std::vector<int> max_coupons(int _A, std::vector<int> _P, std::vector<int> _T) { A = _A; n = _P.size(); FOR(int, i, 1, n) P[i] = _P[i-1], T[i] = _T[i-1]; // FOR(int, i, 1, n) cerr << P[i] << " \n"[i == n]; // FOR(int, i, 1, n) cerr << T[i] << " \n"[i == n]; return Subtask123::solve(); }

Compilation message (stderr)

festival.cpp: In function 'void read(T&)':
festival.cpp:30:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   30 |     register int c;
      |                  ^
#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...