제출 #1213182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213182		vivkostov	메기 농장 (IOI22_fish)	C++20	12 / 100	185 ms	88076 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
    long long int a,b,c;
};
bool cmp(cell a1,cell a2)
{
    if(a1.b<a2.b)return true;
    if(a1.b>a2.b)return false;
    return a1.a<a2.a;
}
struct cord
{
    long long int i,st;
};
long long int n,m;
long long int otg,ultdp[100005],mdp[100005];
///long long int dp[3005][3005],rdp[3005][3005],sdp[3005][3005],col[3005][3005],mat[3005][3005];
vector<cord>dp[100005],rdp[100005],sdp[100005],col[100005],mat[100005];
cell a[300005];
/**
void make_dp()
{
    long long int ma1=0,ma2=0,use1=0,use2=0,l1=0;
    for(int j=1;j<=n;j++)
    {
        ma1=0;
        if(j>=2)ma2=0;
        use1=mdp[j-1];
        use2=mdp[j-2];
        l1=0;
        for(int i=1;i<=n;i++)
        {
            ma1+=mat[i][j-1];
            ma1=max(ma1,sdp[i][j-1]);
            if(j>=2)
            {
                ma2+=mat[i][j-1];
                ma2=max(ma2,rdp[i][j-2]);
            }
            if(!l1)use1-=mat[i][j];
            if(ma1>=use1)
            {
                use1=ma1;
                l1=1;
            }
            if(ma2>=use2)
            {
                use2=ma2;
            }
            if(j>=3)dp[i][j]=ultdp[j-3]+col[i][j-1]+col[i][j+1];
            else dp[i][j]=col[i][j-1]+col[i][j+1];
            dp[i][j]=max(dp[i][j],use1+col[i][j+1]);
            dp[i][j]=max(dp[i][j],use2+col[i][j+1]);
            sdp[i][j]=max(ma1,rdp[i][j-1]);
            sdp[i][j]=max(sdp[i][j],use2);
            sdp[i][j]=max(sdp[i][j],ultdp[j-3]+col[i][j-1]);
            rdp[i][j]=dp[i][j]-col[i][j+1];
            mdp[j]=max(mdp[j],dp[i][j]);
            otg=max(otg,dp[i][j]);
        }
        ultdp[j]=max(ultdp[j],mdp[j]);
    }
    //cout<<endl;
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            //cout<<dp[i][j]<<" ";
        }
        //cout<<endl;
    }
}
**/
void prime_dp()
{
    long long int ma1,ma2,use1,use2;
    int i,z1,z2,zm1,zm2,zm3,l;
    for(int j=1;j<=n;j++)
    {
        ma1=0;
        ma2=0;
        use1=mdp[j-1];
        use2=mdp[j-2];
        l=0;
        z1=0;
        z2=0;
        zm1=0;
        zm2=0;
        zm3=0;
        for(int z=0;z<dp[j].size();z++)
        {
            ///FIX zm and mat
            i=dp[j][z].i;
            zm1++;
            while(zm1<mat[j-1].size()&&mat[j-1][zm1].i<=i)
            {
                ma1+=mat[j-1][zm1].st;
                ma2+=mat[j-1][zm1].st;
                zm1++;
            }
            zm2++;
            while(zm2<mat[j].size()&&mat[j][zm2].i<=i)
            {
                if(!l)use1-=mat[j][zm2].st;
                zm2++;
            }
            zm3++;
            while(zm3<mat[j+1].size()&&mat[j+1][zm3].i<=i)
            {
                zm3++;
            }
            zm1=max(0,zm1-1);
            zm2=max(0,zm2-1);
            zm3=max(0,zm3-1);
            ///FIX ma and use
            z1++;
            while(z1<dp[j-1].size()&&dp[j-1][z1].i<=i)
            {
                ma1=max(ma1,sdp[j-1][z1].st);
                z1++;
            }
            z2++;
            while(z2<dp[j-2].size()&&dp[j-2][z2].i<=i)
            {
                ma2=max(ma2,rdp[j-2][z2].st);
                z2++;
            }
            z1--;
            z2--;
            if(ma1>=use1)
            {
                use1=ma1;
                l=1;
            }
            if(ma2>=use2)
            {
                use2=ma2;
            }

            ///FIX all dp
            if(j>=3)dp[j][z].st=ultdp[j-3]+col[j-1][zm1].st+col[j+1][zm3].st;
            else dp[j][z].st=col[j-1][zm1].st+col[j+1][zm3].st;
            dp[j][z].st=max(dp[j][z].st,use1+col[j+1][zm3].st);
            dp[j][z].st=max(dp[j][z].st,use2+col[j+1][zm3].st);
            sdp[j][z].st=max(ma1,rdp[j-1][z1].st);
            sdp[j][z].st=max(sdp[j][z].st,use2);
            if(j>=3)sdp[j][z].st=max(sdp[j][z].st,ultdp[j-3]+col[j-1][zm1].st);
            else sdp[j][z].st=max(sdp[j][z].st,col[j-1][zm1].st);
            rdp[j][z].st=dp[j][z].st-col[j+1][zm3].st;
            mdp[j]=max(mdp[j],dp[j][z].st);
            otg=max(otg,dp[j][z].st);
            //cout<<j<<" "<<i<<" "<<dp[j][z].st<<" "<<use1<<" "<<sdp[j][z].st<<endl;
        }
        ultdp[j]=max(ultdp[j-1],mdp[j]);
    }
}
void prec()
{
    cord c;
    c.i=0;
    c.st=0;
    for(int i=0;i<=n+1;i++)
    {
        dp[i].push_back(c);
        rdp[i].push_back(c);
        sdp[i].push_back(c);
        mat[i].push_back(c);
        col[i].push_back(c);
    }
    for(int i=1;i<=m;i++)
    {
        c.i=a[i].a;
        c.st=a[i].c;
        if(a[i].b!=1&&(dp[a[i].b-1].size()==0||dp[a[i].b-1].back().i<c.i))
        {
            dp[a[i].b-1].push_back(c);
            rdp[a[i].b-1].push_back(c);
            sdp[a[i].b-1].push_back(c);
        }
        dp[a[i].b+1].push_back(c);
        rdp[a[i].b+1].push_back(c);
        sdp[a[i].b+1].push_back(c);
        mat[a[i].b].push_back(c);
        if(col[a[i].b].size())c.st+=col[a[i].b].back().st;
        col[a[i].b].push_back(c);
    }
    /*cout<<endl;
    for(int j=1;j<=n;j++)
    {
        cout<<j<<" ";
        for(int z=0;z<col[j].size();z++)
        {
            cout<<col[j][z].st<<" ";
        }
        cout<<endl;
    }*/
}
long long int max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
    n=N;
    m=M;
    for(int i=1;i<=m;i++)
    {
        a[i].a=Y[i-1]+1;
        a[i].b=X[i-1]+1;
        a[i].c=W[i-1];
    }
    sort(a+1,a+m+1,cmp);
    prec();
    prime_dp();
    ///make_dp();
    return otg;
}

• Subtask 1: 3 / 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