Submission #1256385

#TimeUsernameProblemLanguageResultExecution timeMemory
1256385ro9669Festival (IOI25_festival)C++20
0 / 100
41 ms7096 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; } 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])); ll cur = w; int i = 0 , j = 0; vector<int> ans; while (i < sz(g[0]) && j < sz(g[1])){ ll X = cost(cur , g[0][i].se); ll Y = cost(cur , g[1][j].se); if (X < 0 && Y < 0) break; if (X > Y){ cur = X; ans.push_back(g[0][i].se); i++; } else{ cur = Y; ans.push_back(g[1][j].se); j++; } } 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...