Submission #1210573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210573		simona1230	Catfish Farm (IOI22_fish)	C++20	61 / 100	1096 ms	45400 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];

vector<long long> same[100001],nxt[100001],prv[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;
                }

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

    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]];
            for(int j=l[x-2]; j<=r[x-2]; j++)
            {
                long long help=0;
                if(a[i].y>a[j].y)help=prec3;
                else help=nxt[x-2][j-l[x-2]];
                dp[i][0]=max(dp[i][0],max(dp[j][0],dp[j][1])+help);
            }
        }
        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]]);
    }

    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