| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1251226 | bronze_coder | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(long long A, vector<int> P, vector<int> T){
int subtask = 3;
int n = P.size();
for(int i=0;i<n;i++){
if(T[i]>2){
subtask = 5;
}
}
if(n<=70){
subtask = 4;
}
vector<pair<int,int>> l1;
vector<pair<int,int>> l2;
vector<pair<int,int>> l3;
vector<pair<int,int>> l4;
for(int i=0;i<n;i++){
if(T[i]==1){
l1.push_back({P[i],i});
}
if(T[i]==2){
l2.push_back({P[i],i});
}
if(T[i]==3){
l3.push_back({P[i],i});
}
if(T[i]==4){
l4.push_back({P[i],i});
}
}
sort(l1.begin(),l1.end());
sort(l2.begin(),l2.end());
sort(l3.begin(),l3.end());
sort(l4.begin(),l4.end());
if(subtask==3){
vector<int> prefix = {0};
for(int i=0;i<l1.size();i++){
prefix.push_back(prefix[i]+l1[i].first);
}
long long A1 = A;
int ans = 0;
for(int i=0;i<=l2.size();i++){
if(i!=0){
A -= l2[i-1].first;
A *= 2;
A = min(A,1000000000000000);
}
int low = 0;
int high = prefix.size()-1;
while(low<high){
int mid = (low+high+1)/2;
if(prefix[mid]>A){
high = mid-1;
}
else{
low = mid;
}
}
ans = max(ans,i+low);
if(A<0){
break;
}
}
A = A1;
for(int i=0;i<=l2.size();i++){
if(i!=0){
A -= l2[i-1].first;
A *= 2;
A = min(A,1000000000000000);
}
int low = 0;
int high = prefix.size()-1;
while(low<high){
int mid = (low+high+1)/2;
if(prefix[mid]>A){
high = mid-1;
}
else{
low = mid;
}
}
if(ans==i+low){
vector<int> answer;
for(int j=0;j<i;j++){
answer.push_back(l2[j].second);
}
for(int j=0;j<low;j++){
answer.push_back(l1[j].second);
}
return answer;
}
}
}
if(subtask==4){
vector<pair<int,int>> l;
for(int i=0;i<n;i++){
if(T[i]!=1){
l.push_back({1LL*T[i]*P[i]*(6/(T[i]-1)),i});
}
}
sort(l.begin(),l.end());
for(int i=0;i<l1.size();i++){
l.push_back(l1[i]);
}
vector<int> ans;
for(int i=0;i<n;i++){
ans.push_back(l[i].second);
}
long long dp[n+1][n+1];
int f[n+1][n+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(i==0){
if(j==0){
dp[i][j] = A;
}
else{
dp[i][j] = -1;
}
}
else{
long long x;
if(j>=1){
x = (dp[i-1][j-1]-P[ans[i-1]])*T[ans[i-1]];
}
else{
x = -1;
}
if(x>dp[i-1][j]){
dp[i][j] = x;
f[i][j] = 1;
}
else{
dp[i][j] = dp[i-1][j];
f[i][j] = 0;
}
dp[i][j] = min(dp[i][j],1000000000000000);
}
}
}
for(int i=n;i>=0;i--){
vector<int> answer;
if(dp[n][i]>=0){
for(int j=n;j>0;j--){
if(f[j][i]){
answer.push_back(ans[j-1]);
i--;
}
}
vector<int> answer1;
for(int j=0;j<answer.size();j++){
answer1.push_back(answer[answer.size()-1-j]);
}
return answer1;
}
}
}
if(subtask==5){
vector<pair<int,int>> l;
for(int i=0;i<n;i++){
if(T[i]!=1){
l.push_back({1LL*T[i]*P[i]*(6/(T[i]-1)),i});
}
}
sort(l.begin(),l.end());
for(int i=0;i<l1.size();i++){
l.push_back(l1[i]);
}
vector<int> ans;
for(int i=0;i<n;i++){
ans.push_back(l[i].second);
}
return ans;
}
}