Submission #1227328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227328		PVM_pvm	Nile (IOI24_nile)	C++20	13 / 100	20 ms	4936 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n;
struct art
{
    long long w,a,b;
} ar[MAXN];
bool cmp(art &a, art &b)
{
    return a.w<b.w;
}
int rr[MAXN],lr[MAXN];
struct state
{
    long long namal;
    int lsl,rsl;
    int lm,rm;
};
bool operator<(state a, state b)
{
    return a.namal<b.namal;
}
bool operator>(state a, state b)
{
    return a.namal>b.namal;
}
bool sloz[MAXN];
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{

    int Q = (int)E.size();
    n=A.size();
    for (int q=0;q<n;q++) ar[q]={W[q],A[q],B[q]};
    //sort(ar,ar+n,cmp);
    vector<long long> R(Q);
    long long otg=0;
    long long otg2=0;
    for (int q=0;q<n;q++) otg+=B[q];
    otg2=otg;
    if (n%2==1)
    {
        long long bst=2000000000;
        for (int q=0;q<n;q++)
        {
            if (q%2!=0) continue;
            long long cur=A[q]-B[q];
            if (cur<bst) bst=cur;
        }
        otg2+=bst;
        bst=2000000000;
        for (int q=0;q<n;q++)
        {
            long long cur=A[q]-B[q];
            if (cur<bst) bst=cur;
        }
        otg+=bst;
    }
    for (int q=0;q<Q;q++)
    {
        if (E[q]>1) R[q]=otg;
        else R[q]=otg2;
    }
    /*
    for (int curZ=0;curZ<Q;curZ++)
    {
        int d=E[curZ];
        rr[n-1]=n-1;
        for (int q=n-2;q>=0;q--)
        {
            rr[q]=rr[q+1];
            while ((ar[rr[q]].w-ar[q].w)>d) rr[q]--;
        }
        lr[0]=0;
        for (int q=1;q<n;q++)
        {
            lr[q]=lr[q-1];
            while ((ar[q].w-ar[lr[q]].w)>d) lr[q]++;
        }
        //cout<<d<<"\n";
        //for (int q=0;q<n;q++) cout<<lr[q]<<" ";
        //cout<<"\n";
        //for (int q=0;q<n;q++) cout<<rr[q]<<" ";
        //cout<<"\n";
        long long otg=0;
        for (int q=0;q<n;q++) otg+=ar[q].a;
        for (int q=0;q<n;q++) sloz[q]=0;
        priority_queue<state> qu;
        for (int q=0;q<n;q++)
        {
            int bst=0,koi=-1;
            for (int w=lr[q];w<=rr[q];w++)
            {
                if (w==q) continue;
                if ((ar[w].a-ar[w].b)>bst)
                {
                    bst=ar[w].a-ar[w].b;
                    koi=w;
                }
            }
            cout<<q<<" "<<koi<<"aa\n";
            if (koi==-1) continue;
            if (koi<q)
            {
                qu.push({ar[q].a-ar[q].b+ar[koi].a-ar[koi].b,koi,q,-1,-1});
            }
            else
            {
                qu.push({ar[q].a-ar[q].b+ar[koi].a-ar[koi].b,q,koi,-1,-1});
            }
        }
        while (!qu.empty())
        {
            state tp=qu.top();
            qu.pop();
            if (sloz[ tp.lsl ] || sloz[ tp.rsl ]) continue;
            otg-=tp.namal;
            sloz[ tp.lsl ]=1;
            sloz[ tp.rsl ]=1;
            cout<<tp.namal<<" "<<tp.lsl<<" "<<tp.rsl<<"\n";
            int bstr=0,koir=-1;
            for (int w=tp.rsl+1;w<=rr[ tp.rsl ];w++)
            {
                if (sloz[w]) continue;
                if ((ar[w].a-ar[w].b)>bstr)
                {
                    bstr=ar[w].a-ar[w].b;
                    koir=w;
                }
            }
            int bstl=0,koil=-1;
            for (int w=tp.lsl-1;w>=lr[tp.lsl];w--)
            {
                if (sloz[w]) continue;
                if ((ar[w].a-ar[w].b)>bstl)
                {
                    bstl=ar[w].a-ar[w].b;
                    koil=w;
                }
            }
            if (koil==-1 || koir==-1) continue;
            qu.push({ar[koil].a-ar[koil].b+ar[koir].a-ar[koir].b,koil,koir,tp.lsl,tp.rsl});
        }
        cout<<otg<<"\n";
        R[curZ]=otg;
    }*/
    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 13 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18