Submission #1210533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210533		simona1230	Catfish Farm (IOI22_fish)	C++20	9 / 100	1096 ms	21168 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 dw,int up)
{
    if(l[x]==-1)return 0;
    if(up<a[l[x]].y)return 0;
    if(a[r[x]].y<dw)return 0;
    if(dw>up)return 0;

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

    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;
    }

    if(id1>id2)return 0;
    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<<" "<<id1<<" "<<id2<<" "<<p[id1]<<" "<<p[id2]<<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]=W[i];
        if(i)p[i]+=p[i-1];
    }

    long long ans=0;

    for(int i=0;i<X.size();i++)
    {
        //cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].w<<endl;
        int x=a[i].x;
        if(x-1>=0)
        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]+sum(x-1,a[j].y,a[i].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[i].y,a[j].y-1));
        }

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

    return ans;
}

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