Submission #1216397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216397		ASGA_RedSea	Catfish Farm (IOI22_fish)	C++20	70 / 100	954 ms	2162688 KiB

fish

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;





ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
    int n=1,m=1;

    for(int i=0;i<M;i++){n=max(n,X[i]+5);m=max(m,Y[i]+5);}

    n=min(n,N);m=min(m,N);

    if(n*m>1e7){
        int spt=1;
        for(int&i:X)spt&=(i%2==0);
        if(spt)return accumulate(W.begin(),W.end(),0LL);


    }

    vector<vector<ll>>w(n,vector<ll>(m,0));
    for(int i=0;i<M;i++){
        w[X[i]][Y[i]]=W[i];
    }

    vector<vector<ll>>d(n,vector<ll>(m+1,0));
    vector<ll>mx(n,0);

    vector<ll>d1(m+1,0),d2(m+1,0);
    for(int i=1;i<n;i++){
        vector<ll>p(m+1,0);
        ll s=accumulate(w[i].begin(),w[i].end(),0LL);
        for(int j=m-1;j>=0;j--){
            p[j]=max(p[j+1],d[i-1][j+1]+s);
            s-=w[i][j];
        }

        s=0;
        for(int j=m-1;j>=0;j--){
            s+=w[i-1][j];
            d1[j]+=s;
        }
        for(int j=1;j<=m;j++)d1[j]=max(d1[j],d1[j-1]);

        s=0;
        ll ss=accumulate(w[i-1].begin(),w[i-1].end(),0LL);
        ll sss=0;
        for(int j=0;j<=m;j++){
            ll&r=d[i][j];

            r=d1[j]-ss;
            if(i>1)r=max(r,mx[i-2]+sss);

            d2[j]=r;

            r=max(p[j]-s,r);
            if(j<m){s+=w[i][j];ss-=w[i-1][j];sss+=w[i-1][j];}
            r=max(r,mx[i-1]);
            mx[i]=max(mx[i],r);

        }
        d1=d2;
    }

    return *max_element(d.back().begin(),d.back().end());
}

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