Submission #1256389

#TimeUsernameProblemLanguageResultExecution timeMemory
1256389ro9669Festival (IOI25_festival)C++20
24 / 100
58 ms9912 KiB
#include "festival.h" #include <bits/stdc++.h> #define sz(a) int(a.size()) #define all(a) a.begin(),a.end() #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int , int> ii; int w; vector<int> p , t; namespace sub1{ const int maxN = int(2e5)+7; const ll inf = ll(1e18); bool check(){ int n = sz(p); for (int i = 0 ; i < n ; i++){ if (t[i] > 2) return false; } return true; } vector<ii> g[2]; ll cost(ll cur , int i){ ll tmp = cur - 1ll * p[i]; if (tmp <= inf / t[i]) return 1ll * tmp * t[i]; else return inf; } ll S[maxN]; int calc(ll x){ int l = 0 , r = sz(g[0]) , ans = 0; while (l <= r){ int mid = (l + r) / 2; if (x >= S[mid]){ ans = mid; l = mid + 1; } else{ r = mid - 1; } } return ans; } vector<int> solve(){ int n = sz(p); for (int i = 0 ; i < n ; i++){ g[t[i] - 1].push_back({p[i] , i}); } sort(all(g[0])); sort(all(g[1])); S[0] = 0; for (int i = 0 ; i < sz(g[0]) ; i++){ S[i + 1] = S[i] + 1ll * g[0][i].fi; } pair<ll , int> res = {calc(w) , 0}; ll cur = w; for (int i = 0 ; i < sz(g[1]) ; i++){ if (cur > g[1][i].fi){ cur = cost(cur , g[1][i].se); if (res.fi < i + 1 + calc(cur)){ res = {i + 1 + calc(cur) , i + 1}; } } } vector<int> ans; for (int i = 0 ; i < res.se ; i++) ans.push_back(g[1][i].se); for (int i = 0 ; i < res.fi - res.se ; i++) ans.push_back(g[0][i].se); return ans; } } vector<int> max_coupons(int W , vector<int> P , vector<int> T){ w = W; p = P; t = T; if (sub1::check()) return sub1::solve(); return {}; } // int main(){ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("templete.inp" , "r" , stdin); // freopen("templete.out" , "w" , stdout); // int n , W; cin >> n >> W; // vector<int> P(n) , T(n); // for (int &x : P) cin >> x; // for (int &x : T) cin >> x; // vector<int> ans = max_coupons(W , P , T); // cout << sz(ans) << "\n"; // return 0; // }
#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...