Submission #1210562

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

fish

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

int n,m;
vector<pair<int,int> > v[400001];
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[400001],r[400001];
long long p[400001];

long long sum(int x,int up)
{
    if(l[x]==-1)return 0;
    if(up<a[l[x]].y)return 0;

    int id1=l[x],id2=-1;
    int lf=l[x],rt=r[x];
    while(lf<=rt)
    {
        int md=(lf+rt)/2;
        if(a[md].y<=up)
        {
            id2=md;
            lf=md+1;
        }
        else rt=md-1;
    }

    long long ans=p[id2]-p[id1]+a[id1].w;
    /*for(int i=l[x];i<=r[x];i++)
        cout<<i<<" - "<<a[i].x<<" "<<a[i].y<<" "<<a[i].w<<endl;
    cout<<x<<" !! "<<dw<<" "<<up<<" "<<ans<<" "<<p[id2]<<" "<<p[id1]<<" "<<a[id1].w<<endl;*/
    return ans;
}

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;
        p[i]=a[i].w;
        if(i)p[i]+=p[i-1];
    }

    long long ans=0;

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

        if(x-1>=0)
        {
            long long prec1=sum(x-1,a[i].y-1);
            long long prec2=sum(x,a[i].y-1);
            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-sum(x-1,a[j].y-1));
                if(a[j].y>=a[i].y)dp[i][1]=max(dp[i][1],max(dp[j][0],dp[j][1])+sum(x,a[j].y-1)-prec2);
            }
        }

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