제출 #627965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
627965		perchuts	메기 농장 (IOI22_fish)	C++17	0 / 100	142 ms	69320 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 ans1, ans2, pr, left, right;
    int coord;
    fish(int coord,ll val) : ans1(0), ans2(0), pr(val), left(0), right(0), coord(coord){}
};

vector<fish>tmp[maxn], v[maxn];
 
vector<ll>dp1[maxn], dp2[maxn], dp3[maxn];//1: subindo, 2: descendo

//ideia: toda ponte termina em um bagre. todo conjunto conexo de pontes forma uma piramide
//(nao possui nenhum minimo local). Logo, pra cada conjunto vou subir e depois descer, sempre nessa ordem.
//nao necessariamente vou subir antes de descer ou descer depois de subir. As transições sao bem diretas mas chatas.
//dp1[i][j] -> considero o melhor valor no prefixo, tirando o right e o pr de cada um (SUBINDO)
//dp2[i][j] -> considero o melhor valor no sufixo (DESCENDO + SUBINDO)
//dp3[i][j] -> considero o melhor valor no prefixo, tirando o right de cada um (DESCENDO + SUBINDO)

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){
        tmp[Y[i]+1].pb(fish(X[i]+1,W[i]));
    }    
 
    for(int i=0;i<=N;++i){
        tmp[i].pb(fish(0,0));
        for(int j=1;j<sz(tmp[i]);++j)tmp[i][j].pr += tmp[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(tmp[x]);++i){
            while(cur<sz(tmp[idx])-1&&tmp[idx][cur+1].coord<=tmp[x][i].coord)++cur;
            ll y = (tmp[idx][cur].coord<=tmp[x][i].coord?tmp[idx][cur].pr:0);
            if(type)tmp[x][i].right = y;
            else tmp[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=1;i<=N;++i){
        for(auto x:tmp[i]){
            v[i+1].pb(x), v[i-1].pb(x);
        }
    }

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

    ll resp = 0;

    for(int i=0;i<=N;++i){
        int cur = 0, cur2 = 0;
        if(i){
            for(int j=0;j<sz(v[i]);++j){
                auto& x = v[i][j]; 
                //dp só guarda resultados onde eu coloco uma ponte
                //o caso onde não tem ponte na esquerda é tratado separadamente
                while(cur<sz(v[i-1])-1&&v[i-1][cur+1].coord<=x.coord)++cur;
                if(i>1)while(cur2<sz(v[i-2])-1&&v[i-2][cur2+1].coord<=x.coord)++cur2;
                //subindo
                //ans1(i,j) = max(dp1[i-1][k]-pr[i][k]-pr[i-1][k]) + pr[i-1][j] + pr[i+1][j], k<=j
                x.ans1 = dp1[i-1][cur] + x.left + x.right;
                //descendo
                //ans2(i,j) = max(dp2[i-1][k]) - pr[i][j] + pr[i+1][j], k>=j
                if(cur!=sz(v[i-1])-1)x.ans2 = dp2[i-1][cur+1] - x.pr + x.right;
                ll y = 0;
                //i-1 é zero
                if(i>=2)y = max(dp3[i-2][cur2]+x.left+x.right, (cur2!=sz(v[i-2])-1?dp2[i-2][cur2+1]+x.right:0)); 
                //i-1 e i-2 são zero
                if(i>=3)ckmax(y, dp2[i-3][0] + x.left + x.right);
                ckmax(x.ans1,y), ckmax(x.ans2,y);
            }
        }else v[0][0].ans1 = v[0][0].ans2 = 0;
        
        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){
            auto x = v[i][j];
            dp1[i][j] = max(dp1[i][j-1], x.ans1 - x.pr - x.right);
            dp3[i][j] = max({dp3[i][j-1], x.ans1 - x.right, x.ans2});
            ckmax(resp, max(x.ans1, x.ans2));
        }

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


    return resp;
}
  
// 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