제출 #786831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
786831		andrei_boaca	메기 농장 (IOI22_fish)	C++17	35 / 100	1088 ms	17864 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
ll n,m;
struct date
{
    ll poz,val;
};
vector<date> myy[100005];
ll dp[3][3005][3005],v[3005][3005];
bool comp(date a, date b)
{
    return a.poz<b.poz;
}
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<m;i++)
    {
        ll x=X[i];
        ll y=Y[i];
        ll w=W[i];
        myy[x+1].push_back({y+1,w});
        v[x+1][y+1]=w;
    }
    for(int i=1;i<=n;i++)
    {
        myy[i].push_back({0,0});
        myy[i].push_back({n+1,0});
        sort(myy[i].begin(),myy[i].end(),comp);
    }
    ll ans=0;
    for(int i=2;i<=n;i++)
    {
        // neutru
        ll suma=0;
        for(ll p=0;p<=n;p++)
        {
            suma+=v[i][p];
            for(ll p1=p;p1<=n;p1++)
                dp[0][i][p]=max(dp[0][i][p],suma+max(dp[1][i-1][p1],dp[2][i-1][p1]));
            if(p==0)
            {
                for(int p1=0;p1<=p;p1++)
                    dp[0][i][p]=max(dp[0][i][p],dp[0][i-1][p1]);
            }
            ans=max(ans,dp[0][i][p]);
        }

        // cresc
        for(ll p=0;p<=n;p++)
        {
            ll s1=0;
            for(ll j=0;j<=p;j++)
                s1+=v[i-1][j];
            ll s2=0;
            for(ll j=0;j<=p;j++)
            {
                s2+=v[i-1][j];
                dp[1][i][p]=max(dp[1][i][p],max(0LL,s1-s2)+max(dp[0][i-1][j],dp[1][i-1][j]));
            }
            ans=max(ans,dp[1][i][p]);
        }

        // desc
        for(ll p=0;p<=n;p++)
        {
            ll s2=0;
            for(ll j=0;j<=p;j++)
                s2+=v[i][j];
            ll s1=0;
            for(ll j=0;j<=n;j++)
            {
                s1+=v[i][j];
                dp[2][i][p]=max(dp[2][i][p],max(0LL,s1-s2+max(dp[1][i-1][j],dp[2][i-1][j])));
            }
            ans=max(ans,dp[2][i][p]);
        }
    }
    return ans;
}

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