Submission #1225393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225393		guagua0407	Catfish Farm (IOI22_fish)	C++20	100 / 100	263 ms	79392 KiB

fish

#pragma GCC optimize("O3")
#include "fish.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int mxn=1e5+5;
    const ll inf=(ll)1e18;
    vector<vector<ll>> dpl,dpr;
}

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
    auto st=clock();
    vector<int> x=X;
    vector<int> y=Y;
    vector<int> w=W;
    for(int i=0;i<m;i++){
        x[i]++;
        y[i]++;
        //cout<<x[i]<<' '<<y[i]<<' '<<w[i]<<'\n';
    }
    vector<vector<int>> pos(n+1);
    for(int i=0;i<m;i++){
        pos[x[i]].push_back(i);
    }
    vector<vector<int>> ys(n+1);
    vector<vector<ll>> pre(n+1);
    vector<vector<int>> prv(n+1);
    vector<vector<int>> nxt(n+1);
    vector<int> sz(n+1);
    for(int i=0;i<=n;i++){
        ys[i].push_back(0);
        for(auto v:pos[i]){
            //ys[i].push_back(y[v]-1);
            ys[i].push_back(y[v]);
        }
        if(i>0){
            for(auto v:pos[i-1]){
                ys[i].push_back(y[v]);
                //ys[i].push_back(y[v]-1);
            }
        }
        if(i<n){
            for(auto v:pos[i+1]){
                ys[i].push_back(y[v]);
                //ys[i].push_back(y[v]-1);
            }
        }
        sort(all(ys[i]));
        ys[i].resize(unique(all(ys[i]))-ys[i].begin());
        sz[i]=(int)ys[i].size();
        pre[i]=vector<ll>(sz[i]);
        for(auto v:pos[i]){
            int j=lower_bound(all(ys[i]),y[v])-ys[i].begin();
            pre[i][j]+=w[v];
        }
        for(int j=1;j<sz[i];j++){
            pre[i][j]+=pre[i][j-1];
        }
    }
    for(int i=0;i<=n;i++){
        if(i>0){
            prv[i]=vector<int>(sz[i]);
            for(int j=0;j<sz[i];j++){
                prv[i][j]=upper_bound(all(ys[i-1]),ys[i][j])-ys[i-1].begin()-1;
            }
        }
        if(i<n){
            nxt[i]=vector<int>(sz[i]);
            for(int j=0;j<sz[i];j++){
                nxt[i][j]=upper_bound(all(ys[i+1]),ys[i][j])-ys[i+1].begin()-1;
            }
        }
    }
    dpl.resize(n+1);
    dpr.resize(n+1);
    for(int i=0;i<=n;i++){
        dpl[i]=vector<ll>(sz[i],-inf);
        dpr[i]=vector<ll>(sz[i],-inf);
    }
    dpr[0][0]=0;
    ll ans=0;
    for(int i=0;i<n;i++){
        {
            int r=sz[i]-1;
            ll mx=-inf;
            for(int l=sz[i+1]-1;l>=0;l--){
                while(r>=0 and ys[i][r]>=ys[i+1][l]){
                    mx=max(mx,dpr[i][r]);
                    r--;
                }
                dpl[i+1][l]=max(dpl[i+1][l],mx);
                dpr[i+1][l]=max(dpr[i+1][l],mx);
            }
        }
        {
            int r=0;
            ll mx=-inf;
            for(int l=0;l<sz[i+1];l++){
                while(r<sz[i] and ys[i][r]<=ys[i+1][l]){
                    mx=max(mx,dpr[i][r]-pre[i][r]);
                    r++;
                }
                dpl[i+1][l]=max(dpl[i+1][l],mx+pre[i][prv[i+1][l]]);
                dpr[i+1][l]=max(dpr[i+1][l],mx+pre[i][prv[i+1][l]]);
            }
        }
        //continue;
        {
            int l=sz[i]-1;
            ll mx=-inf;
            for(int r=sz[i+1]-1;r>=0;r--){
                while(l>=0 and ys[i][l]>=ys[i+1][r]){
                    dpr[i+1][nxt[i][l]]=max(dpr[i+1][nxt[i][l]],dpl[i][l]+pre[i+1][nxt[i][l]]);
                    mx=max(mx,dpl[i][l]+pre[i+1][nxt[i][l]]);
                    l--;
                }
                dpl[i+1][r]=max(dpl[i+1][r],mx-pre[i+1][r]);
            }
        }
        //continue;
        {
            int l=0;
            ll mx=-inf;
            for(int r=0;r<sz[i+1];r++){
                while(l<sz[i] and ys[i][l]<=ys[i+1][r]){
                    //cout<<i<<' '<<l<<' '<<dpl[i][l]<<'\n';
                    mx=max(mx,dpl[i][l]);
                    l++;
                }
                dpr[i+1][r]=max(dpr[i+1][r],mx);
                dpl[i+1][r]=max(dpl[i+1][r],mx);
            }
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<sz[i];j++){
            //cout<<i<<' '<<j<<' '<<dpl[i][j]<<' '<<dpr[i][j]<<'\n';
            ans=max({ans,dpl[i][j],dpr[i][j]});
        }
    }
    return ans;
}

• 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