Submission #768071

#	Time	Username	Problem	Language	Result	Execution time	Memory
768071		Khizri	Catfish Farm (IOI22_fish)	C++17	18 / 100	73 ms	14320 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=3e5+5;
ll n,m,x[mxn],y[mxn],arr[mxn],val[305][305],pre[305][305],dp[305][305][2];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n=N;
    m=M;
    bool t1=true,t2=true,t3=true;
    ll sum=0;
    for(int i=0;i<m;i++){
        x[i]=X[i];
        y[i]=Y[i];
        arr[i]=W[i];
        sum+=arr[i];
        if(x[i]%2) t1=false;
        if(x[i]>1) t2=false;
        if(y[i]!=0) t3=false;
    }
    if(t1){
        return sum;
    }
    if(t2){
        vector<int>a(n+5),b(n+5);
        ll k=0;
        for(int i=0;i<m;i++){
            if(x[i]==0){
                a[y[i]]=arr[i];
            }
            else{
                b[y[i]]=arr[i];
                k+=arr[i];
            }
        }
        if(n==2){
            return max(a[0]+a[1],b[0]+b[1]);
        }
        ll ans=k;
        for(int i=0;i<n;i++){
            k-=b[i];
            k+=a[i];
            ans=max(ans,k);
        }
        return ans;
    }
    if(t3){
        vector<vector<ll>>dp(n+5,vector<ll>(3));
        vector<ll>val(n+5);
        for(int i=0;i<m;i++){
            val[x[i]]=arr[i];
        }
        for(int i=1;i<n;i++){
            dp[i][1]=dp[i-1][1];
            if(i>1){
                dp[i][1]=max(dp[i-1][1],max(dp[i-2][1],dp[i-2][0])+val[i-1]);
            }
            else{
                dp[i][1]=val[i-1];
            }
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+val[i]);
        }
        return max(dp[n-1][1],dp[n-1][0]);
    }
    for(int i=0;i<m;i++){
        val[x[i]+1][y[i]+1]=arr[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            pre[j][i]=pre[j-1][i]+val[i][j];
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<j;k++){
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][k][1]+pre[j][i-1]-pre[k][i-1]);
            }
            for(int k=0;k<=n&&i>1;k++){
                if(i==2){
                    dp[i][j][1]=pre[j][i-1];
                    dp[i][j][0]=pre[j][i-1];
                }
                else{
                    dp[i][j][1]=max(dp[i][j][1],max(dp[i-2][k][1],dp[i-2][k][0])+pre[max(k,j)][i-1]);
                    dp[i][j][0]=max(dp[i][j][0],max(dp[i-2][k][1],dp[i-2][k][0])+pre[max(k,j)][i-1]);
                }
            }
            for(int k=j;k<=n;k++){
                dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][k][0],dp[i-1][k][1])+pre[k][i]-pre[j][i]);
            }
        }
    }
    for(int i=0;i<=n;i++){
        ans=max(ans,dp[n][i][0]);
        ans=max(ans,dp[n][i][1]);
    }
    return ans;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

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