제출 #1213113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213113		vivkostov	Catfish Farm (IOI22_fish)	C++20	52 / 100	806 ms	367420 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
    long long int a,b,c;
};
long long int mat[3005][3005],col[3005][3005],n,m;
long long int otg,dp[3005][3005],mdp[3005],rdp[3005][3005],sdp[3005][3005],ultdp[3005];
cell a[300005];
void make_dp()
{
    long long int ma1=0,ma2=0,use1=0,use2=0,l1=0,l2=0;
    for(int j=1;j<=n;j++)
    {
        ma1=0;
        ma2=0;
        use1=mdp[j-1];
        use2=mdp[j-2];
        l1=0;
        l2=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;
    }
}
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];
        mat[a[i].a][a[i].b]=a[i].c;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            col[i][j]=col[i-1][j]+mat[i][j];
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            //cout<<mat[i][j]<<" ";
        }
        //cout<<endl;
    }
    //cout<<endl;
    make_dp();
    return otg;
}

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