Submission #627400

#	Time	Username	Problem	Language	Result	Execution time	Memory
627400		perchuts	Catfish Farm (IOI22_fish)	C++17	0 / 100	64 ms	28156 KiB

fish

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "fish.h"
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

struct fish{
    ll ans, pr, left, right;
    int coord;
    fish(int coord,ll val) : ans(0), pr(val), left(0), right(0), coord(coord){}
};

vector<fish>v[maxn];

vector<ll>dp1[maxn], dp2[maxn], dp3[maxn];

bool comp(fish a,fish b){
    return a.coord<b.coord;
}

ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int> W) {

    for(int i=0;i<M;++i){
        v[Y[i]+1].pb(fish(X[i]+1,W[i]));
    }    

    for(int i=0;i<=N;++i){
        v[i].pb(fish(0,0));
        sort(all(v[i]), comp);
        for(int j=1;j<sz(v[i]);++j)v[i][j].pr += v[i][j-1].pr;
    }

    auto processa = [&](int x,bool type){
        int cur = 0, idx = (type?x+1:x-1);
        for(int i=1;i<sz(v[x]);++i){
            while(cur<sz(v[idx])-1&&v[idx][cur+1].coord<=v[x][i].coord)++cur;
            ll y = v[idx][cur].pr;
            if(type)v[x][i].right = y;
            else v[x][i].left = y;
        }
    };

    for(int i=1;i<=N;++i){
        if(i!=1)processa(i,0);
        if(i!=N)processa(i,1);
    }


    for(int i=0;i<=N;++i){
        int cur = 0, cur2 = 0;
        for(auto& x:v[i]){
            //2 casos:
            //a minha coordenada é k
            //1: a linha à minha esquerda é menor do que eu:
            //max(dp[i-1][j]-qnt[i][j]-qnt[i-1][j])+qnt[i-1][k]+qnt[i+1][k]
            //2:a linha à minha esquerda é maior do que eu:
            //max(dp[i-1][j]) - qnt[i][k] - qnt[i-1][k] + qnt[i+1][k]
            //corner case: o cara do meu lado é igual a zero

            if(i<=1){
                x.ans = x.right;
            }else{
                if(i>=3)x.ans = dp2[i-3][0];//duas colunas anteriores sao 0

                while(cur<sz(v[i-1])-1&&
                v[i-1][cur+1].coord<=x.coord)++cur;

                while(cur2<sz(v[i-2])-1&&
                v[i-2][cur2+1].coord<=x.coord)++cur2;

                //coluna anterior é igual a zero
                ckmax(x.ans,max(dp3[i-2][cur2]+x.left+x.right,
                (cur2==sz(dp2[i-2])-1?0:dp2[i-2][cur+1]+x.right)));

                ckmax(x.ans,dp1[i-1][cur] + x.pr + x.right);

                if(cur!=sz(dp1[i-1])-1){
                    ckmax(x.ans, dp2[i-1][cur+1]-x.pr+x.right);
                }
            }
        }

        dp1[i].resize(sz(v[i]));
        dp2[i].resize(sz(v[i]));
        dp3[i].resize(sz(v[i]));

        for(int j=1;j<sz(v[i]);++j){
            dp1[i][j] = max(dp1[i][j-1],v[i][j].ans-v[i][j].pr
            -v[i][j].right);
            dp3[i][j] = max(dp3[i][j-1], v[i][j].ans - v[i][j].right);
        }

        for(int j=sz(v[i])-1;j>=0;--j){
            dp2[i][j] = v[i][j].ans;
            if(j!=sz(v[i])-1)ckmax(dp2[i][j], dp2[i][j+1]);
        }

    }

    return dp2[N][0];
}


// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));

//   std::vector<int> X(M), Y(M), W(M);
//   for (int i = 0; i < M; ++i) {
//     assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
//   }

//   long long result = max_weights(N, M, X, Y, W);
//   printf("%lld\n", result);
//   return 0;
// }

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