Submission #1210584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210584		simona1230	Catfish Farm (IOI22_fish)	C++20	61 / 100	1096 ms	83604 KiB

fish

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

int n,m;
long long dp[400001][2];
struct catfish
{
    int x,y,w;
    catfish() {}
    catfish(int _x,int _y,int _w)
    {
        x=_x;
        y=_y;
        w=_w;
    }

    bool operator<(const catfish&c)const
    {
        if(x==c.x)return y<c.y;
        return x<c.x;
    }
};

catfish a[400001];
int l[100001],r[100001];
long long maxx0[100001],maxx1[100001];

vector<long long> same[100001],nxt[100001],prv[100001],m1[100001],m2[100001],m3[100001];
vector<int> id1[100001],id2[100001];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W)
{
    n=N;
    m=M;
    for(int i=0; i<n; i++)
    {
        X.push_back(i);
        Y.push_back(n);
        W.push_back(0);
        l[i]=-1;
        r[i]=-2;
    }

    for(int i=0; i<X.size(); i++)
        a[i]= {X[i],Y[i],W[i]};

    sort(a,a+X.size());
    for(int i=0; i<X.size(); i++)
    {
        if(i==0||a[i].x!=a[i-1].x)l[a[i].x]=i;
        if(i==X.size()-1||a[i].x!=a[i+1].x)r[a[i].x]=i;
    }

    long long ans=0;

    for(int i=0;i<n;i++)
    {
        same[i].push_back({0});
        for(int j=l[i]+1;j<=r[i];j++)
            same[i].push_back(same[i][same[i].size()-1]+a[j-1].w);

        if(i!=n-1)
        {
            int k=l[i+1]-1;
            long long curr=0;
            for(int j=l[i];j<=r[i];j++)
            {
                while(k<r[i+1]&&a[k+1].y<a[j].y)
                {
                    k++;
                    curr+=a[k].w;
                }

                nxt[i].push_back(curr);
            }
        }

        if(i!=0)
        {
            int k=l[i-1]-1;
            long long curr=0;
            for(int j=l[i];j<=r[i];j++)
            {
                while(k<r[i-1]&&a[k+1].y<a[j].y)
                {
                    k++;
                    curr+=a[k].w;
                }
                id1[i].push_back(k-l[i-1]);
                prv[i].push_back(curr);
            }
        }

        if(i-2>=0)
        {
            int k=l[i-2]-1;
            for(int j=l[i];j<=r[i];j++)
            {
                while(k<r[i-2]&&a[k+1].y<a[j].y)
                {
                    k++;
                }
                id2[i].push_back(k-l[i-2]);
            }
        }
    }

    for(int i=0; i<X.size(); i++)
    {
        int x=a[i].x;

        if(x-1>=0)
        {
            long long prec1=prv[x][i-l[x]];
            long long prec2=same[x][i-l[x]];
            for(int j=l[x-1]; j<=r[x-1]; j++)
            {
                if(a[j].y<a[i].y)dp[i][0]=max(dp[i][0],dp[j][0]+prec1-same[x-1][j-l[x-1]]);
                if(a[j].y>=a[i].y)dp[i][1]=max(dp[i][1],max(dp[j][0],dp[j][1])+nxt[x-1][j-l[x-1]]-prec2);
            }
        }


        if(x-2>=0)
        {
            long long prec3=prv[x][i-l[x]];
            int h=id2[x][i-l[x]];
            //cout<<h<<" "<<m3[x-2].size()<<" "<<m2[x-2].size()<<endl;
            if(h>=0)dp[i][0]=max(dp[i][0],m3[x-2][h]+prec3);
            dp[i][0]=max(dp[i][0],m2[x-2][h+1]);
        }
        ans=max(ans,max(dp[i][0],dp[i][1]));
        //cout<<a[i].x<<"---- "<<a[i].y<<" "<<a[i].w<<endl;
        //cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
        if(x!=n-1)ans=max(ans,max(dp[i][0],dp[i][1])+nxt[x][i-l[x]]);

        if(i==r[x])
        {
            for(int j=l[x];j<=r[x];j++)
            {
                m1[x].push_back(dp[j][0]-same[x][j-l[x]]);
                if(j!=l[x])m1[x][j-l[x]]=max(m1[x][j-l[x]],m1[x][j-l[x]-1]);

                m3[x].push_back(max(dp[j][0],dp[j][1]));
                if(j!=l[x])m3[x][j-l[x]]=max(m3[x][j-l[x]],m3[x][j-l[x]-1]);

                m2[x].push_back(0);
            }

            if(x!=n-1)
            for(int j=r[x];j>=l[x];j--)
            {
                m2[x][j-l[x]]=max(dp[j][0],dp[j][1])+nxt[x][j-l[x]];
                if(j!=r[x])m2[x][j-l[x]]=max(m2[x][j-l[x]],m2[x][j-l[x]+1]);
            }

        }
    }

    return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16