Submission #825106

#	Time	Username	Problem	Language	Result	Execution time	Memory
825106		alvingogo	Catfish Farm (IOI22_fish)	C++17	100 / 100	467 ms	98672 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

const long long inf=1e16;
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    set<int> tw;
    for(int i=0;i<m;i++){
        if(y[i]==0){
            tw.insert(x[i]);
        }
    }
    vector<vector<pair<int,long long> > > v(n);
    for(int i=0;i<n;i++){
        v[i].push_back({-2,0});
        if(tw.find(i)!=tw.end()){
            continue;
        }
        x.push_back(i);
        y.push_back(0);
        w.push_back(0);
    }
    m=x.size();
    vector<vector<int> > lis(n);
    vector<int> s(n),vs(n);
    for(int i=0;i<m;i++){
        v[x[i]].push_back({y[i],w[i]});
        lis[x[i]].push_back(y[i]-1);
        lis[x[i]].push_back(y[i]);
        if(x[i]-1>=0){
            lis[x[i]-1].push_back(y[i]);
        }
        if(x[i]+1<n){
            lis[x[i]+1].push_back(y[i]);
        }
    }
    auto org=lis;
    for(int i=0;i<n;i++){
        sort(v[i].begin(),v[i].end());
        vs[i]=v[i].size();
        for(int j=1;j<vs[i];j++){
            v[i][j].sc+=v[i][j-1].sc;
        }
        v[i].push_back({1e9,v[i][vs[i]-1].sc});
        sort(lis[i].begin(),lis[i].end());
        lis[i].erase(unique(lis[i].begin(),lis[i].end()),lis[i].end());
        s[i]=lis[i].size();
    }
    auto get=[&](int i,int a){
        return lower_bound(lis[i].begin(),lis[i].end(),a)-lis[i].begin();
    };
    auto get2=[&](int i,int a){
        return upper_bound(v[i].begin(),v[i].end(),pair<int,long long>(a,inf))-v[i].begin()-1;
    };
    auto get3=[&](int i,int a){
        return upper_bound(v[i].begin(),v[i].end(),pair<int,long long>(a,-1))-v[i].begin();
    };
    vector<vector<long long> > dp[3];
    dp[0].resize(n);
    dp[1].resize(n);
    dp[2].resize(n);
    // 0: i-1 >= i, 1: i-1 < i, 2: i = 0, j = the chosen blocks in col i-1  
    for(int i=0;i<n;i++){
        dp[0][i].resize(s[i]);
        dp[1][i].resize(s[i]);
        if(i){
            dp[2][i].resize(s[i-1]);
        }
        else{
            dp[2][i].resize(1);
        }
    }
    for(int i=0;i<s[0];i++){
        dp[1][0][i]=-inf;
    }
    for(int i=1;i<n;i++){
        //dp[0][i][j] = max(dp[0][i-1][j]+cnt[i]);
        // 0 -> 0
        // 1 -> 0
        int l=0;
        int r=s[i-1]-1;
        long long mx=-inf;
        
        for(int j=s[i]-1;j>0;j--){
            while(r>=0 && lis[i-1][r]>=lis[i][j]){
                mx=max(mx,max(dp[0][i-1][r],dp[1][i-1][r])+v[i][get2(i,lis[i-1][r])].sc);
                r--;
            }
            dp[0][i][j]=max(dp[0][i][j],mx-v[i][get2(i,lis[i][j])].sc);
        }
        
        // 1 -> 1
        l=0;
        mx=-inf;
        for(int j=1;j<s[i];j++){
            while(l<s[i-1] && lis[i-1][l]<lis[i][j]){
                mx=max(mx,dp[1][i-1][l]-v[i-1][get2(i-1,lis[i-1][l])].sc);
                l++;
            }
            dp[1][i][j]=max(dp[1][i][j],mx+v[i-1][get2(i-1,lis[i][j])].sc);
        }
        
        // 2 -> 1
        if(i-2>=0){
            l=0;
            mx=-inf;
            for(int j=1;j<s[i];j++){
                while(l<s[i-2] && lis[i-2][l]<lis[i][j]){
                    int z=get2(i-1,lis[i-2][l]);
                    mx=max(mx,dp[2][i-1][l]-v[i-1][z].sc);
                    l++;
                }
                int z=get2(i-1,lis[i][j]);
                dp[1][i][j]=max(dp[1][i][j],mx+v[i-1][z].sc);
            }
            r=s[i-2]-1;
            mx=-inf;
            for(int j=s[i]-1;j>0;j--){
                while(r>=0 && lis[i-2][r]>=lis[i][j]){
                    mx=max(mx,dp[2][i-1][r]);
                    r--;
                }
                dp[1][i][j]=max(dp[1][i][j],mx);
            }
        }
        
        else{
            for(int j=1;j<s[i];j++){
                dp[1][i][j]=max(dp[1][i][j],dp[0][i-1][0]+v[i-1][get2(i-1,lis[i][j])].sc);
            }
        }
        // 0 -> 2
        // 1 -> 2
        for(int j=0;j<s[i-1];j++){
            dp[2][i][j]=max(dp[0][i-1][j],dp[1][i-1][j])+v[i][get2(i,lis[i-1][j])].sc;
        }
        // 2 -> 2
        if(i>=2){
            for(int j=0;j<s[i-2];j++){
                dp[2][i][0]=max(dp[2][i][0],dp[2][i-1][j]);
            }
        }
        else{
            dp[2][i][0]=max(dp[2][i][0],0ll);
        }
        
    }
    /*
    for(int i=0;i<3;i++){
        for(int j=0;j<n;j++){
            for(auto h:dp[i][j]){
                cout << h << " ";
            }
            cout << '\n';
        }
        cout << '\n';
    }
    */
    long long ans=0;
    for(int i=0;i<2;i++){
        for(int j=0;j<s[n-1];j++){
            ans=max(ans,dp[i][n-1][j]);
        }
    }
    for(int i=0;i<s[n-2];i++){
        ans=max(ans,dp[2][n-1][i]);
    }
    return ans;
}

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:52:10: warning: variable 'get' set but not used [-Wunused-but-set-variable]
   52 |     auto get=[&](int i,int a){
      |          ^~~
fish.cpp:58:10: warning: variable 'get3' set but not used [-Wunused-but-set-variable]
   58 |     auto get3=[&](int i,int a){
      |          ^~~~

• 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: 14 / 14
• Subtask 8: 16 / 16