boj10167.cpp

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
 
using namespace std;
#define MAXN 3100
#define ll long long
typedef struct Point{
    int x, y, w;
}Point;
typedef struct Node{
    ll SUM, LSUM, RSUM, MAXSUM;
    Node(){}
    Node(ll w){
        SUM = LSUM = RSUM = MAXSUM = w;
    }
}Node;
Node itr[4*MAXN];
Point point[MAXN];
int p = 1, xsize = 0;
 
void init(){
    for(int i = 1 ; i< (p << 1) ; i++){
        itr[i] = Node(0);
    }
}
 
void renew(int idx){
    int L = idx*2, R = idx*2+1;
    itr[idx].SUM = itr[L].SUM + itr[R].SUM;
    itr[idx].LSUM = max(itr[L].LSUM, itr[L].SUM + itr[R].LSUM);
    itr[idx].RSUM = max(itr[R].RSUM, itr[R].SUM + itr[L].RSUM);
    itr[idx].MAXSUM = max(itr[L].RSUM+itr[R].LSUM, max(itr[L].MAXSUM, max(itr[R].MAXSUM, itr[idx].SUM)));
}
 
void push(int idx, int w){
    itr[idx] = Node(itr[idx].SUM + w);
    for(int i = (idx >> 1); i >= 1; i>>=1)
        renew(i);
}
 
bool compare(const Point&i , const Point&j){
    return i.y < j.y;
}
 
int main(){
    int N;
    cin >> N;
     
    vector<int> x;
    map<int, int> xposition;
    for(int i = 0 ; i < N ; i++){
        scanf("%d%d%d", &point[i].x, &point[i].y, &point[i].w);
        x.push_back(point[i].x);
    }
    sort(point, point+N, compare);
     
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    xsize = (int)x.size();
    for(int i = 0 ; i < xsize ; i++)
        xposition[x[i]]= i;
    for(int i = 0 ; i < N ; i++)
        point[i].x = xposition[point[i].x];
     
    while(xsize > p ) p <<= 1;
     
    ll ans = 0;
    for(int i = 0 ; i <  N ;  i++){
        init();
        for(int j = i ; j < N ; j++){
            if(j <= N-2 && point[j].y == point[j+1].y){
                push(p+point[j].x, point[j].w);
                continue;
            }
            push(p+point[j].x, point[j].w);
            ans = max(ans, itr[1].MAXSUM);
        }
        for(int j = i ; j < N ; j++){
            if(j <= N-2 && point[j].y != point[j+1].y){
                i = j;
                break;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}