Submission #1251229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251229		bronze_coder	Festival (IOI25_festival)	C++20	27 / 100	77 ms	8504 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> max_coupons(int A1, vector<int> P, vector<int> T){
    long long A = A1;
    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,1000000000000000LL);
            }
            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,1000000000000000LL);
            }
            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],1000000000000000LL);
                }
            }
        }

        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;
    }
}

Compilation message (stderr)

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:181:1: warning: control reaches end of non-void function [-Wreturn-type]
  181 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 27 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18