Submission #1225064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225064		guagua0407	Catfish Farm (IOI22_fish)	C++20	14 / 100	1102 ms	258016 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=300+5;
    const ll inf=(ll)1e18;
    ll dp[mxn][mxn][mxn];
}

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;
            }
        }
    }
    for(int i=0;i<mxn;i++){
        for(int j=0;j<mxn;j++){
            for(int k=0;k<mxn;k++){
                dp[i][j][k]=-inf;
            }
        }
    }
    dp[0][0][0]=0;
    ll ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<sz[i];j++){
            for(int k=j;k<sz[i];k++){
                //cout<<i<<' '<<j<<' '<<k<<' '<<ys[i][j]<<' '<<ys[i][k]<<' '<<dp[i][j][k]<<'\n';
                //if(i==n) continue;
                for(int l=0;l<sz[i+1];l++){
                    ll sum=dp[i][j][k];
                    int r;
                    if(ys[i+1][l]<ys[i][j]){
                        /*
                        for(auto v:pos[i+1]){
                            if(y[v]>ys[i+1][l] and y[v]<=ys[i][j]) sum+=w[v];
                        }
                        */
                        int L=l;
                        int R=nxt[i][j];
                        assert(L<=R);
                        sum+=pre[i+1][R]-pre[i+1][L];
                        r=R;
                    }
                    else{
                        /*
                        for(auto v:pos[i]){
                            if(y[v]>ys[i][k] and y[v]<=ys[i+1][l]) sum+=w[v];
                        }
                        */
                        if(ys[i][k]<ys[i+1][l]){
                            int L=k;
                            int R=prv[i+1][l];
                            assert(L<=R);
                            sum+=pre[i][R]-pre[i][L];
                        }
                        r=l;
                    }
                    dp[i+1][l][r]=max(dp[i+1][l][r],sum);
                    ans=max(ans,dp[i+1][l][r]);
                }
            }
        }
    }
    return ans;
}

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