Submission #1365411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365411		activedeltorre	Festival (IOI25_festival)	C++20	0 / 100	1096 ms	9784 KiB

festival

#include "festival.h"
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ura
{
    long long first,second,index;
};
ura vec[200005];
bool cmp(ura a,ura b)
{
    if(a.first==0 || b.first==0)
    {
        return a.first<b.first;
    }
    long long val1=1ll*a.first*a.second*b.second+b.first*b.second;
    long long val2=1ll*b.first*b.second*a.second+a.first*a.second;
    return val1<val2;
}
vector<ura>tip[5];
long long inf=1e16;
bool check(vector<ura>a,int A)
{
    long long val=A;
    for(int i=0;i<a.size();i++)
    {
       if(val>=a[i].first)
       {
           val=val-a[i].first;
           val=val*a[i].second;
           val=min(val,inf);
       }
       else
       {
           return 0;
       }
    }
    return 1;
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
    int n=P.size();
    for(int i=0; i<n; i++)
    {
        //vec[i].first=P[i];
        //vec[i].second=T[i];
        //vec[i].index=i;
        ura nod;
        nod.index=i;
        nod.second=T[i];
        nod.first=P[i];
        tip[T[i]-1].push_back({nod});
    }
    for(int i=0;i<4;i++)
    {
        sort(tip[i].begin(),tip[i].end(),cmp);
    }
    vector<ura>best;
    for(int d1=0; d1<=tip[0].size(); d1++)
    {
        for(int d2=0; d2<=tip[1].size(); d2++)
        {
            for(int d3=0; d3<=tip[2].size(); d3++)
            {
                for(int d4=0; d4<=tip[3].size(); d4++)
                {
                    if(d1+d2+d3+d4>best.size())
                    {
                        vector<ura>vec;
                        for(int i=0; i<d1; i++)
                        {
                            vec.push_back(tip[0][i]);
                        }
                        for(int i=0; i<d2; i++)
                        {
                            vec.push_back(tip[1][i]);
                        }
                        for(int i=0; i<d3; i++)
                        {
                            vec.push_back(tip[2][i]);
                        }
                        for(int i=0; i<d4; i++)
                        {
                            vec.push_back(tip[3][i]);
                        }
                        sort(vec.begin(),vec.end(),cmp);
                        if(check(vec,A)==1)
                        {
                            best=vec;
                        }
                    }
                }
            }
        }
    }
    vector<int>rasp;
    for(int i=0; i<best.size(); i++)
    {
        rasp.push_back(best[i].index);
    }
    return rasp;
}

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