Submission #767946

#	Time	Username	Problem	Language	Result	Execution time	Memory
767946		Khizri	Catfish Farm (IOI22_fish)	C++17	9 / 100	71 ms	10852 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;
int n,m,x[mxn],y[mxn],arr[mxn];
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]);
            }
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+val[i]);
        }
        return max(dp[n-1][1],dp[n-1][0]);
    }
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^

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