글 읽기 - 금광 질문 있습니다

leekh100000 8년 전 0

Gold 구조체로 입력받고 Segmant Tree에 집어넣어 y축 기준으로 최적해를 구하는 방식인데,

어디서는 틀렸다 하고 어디서는 시간이 터지더군요.. N^2lgN이라고 생각했는데 아닌가요?

#include<stdio.h>
#include<algorithm>
long long Res;
int Mp;
long long Fmax(long long a, long long b){
    if(a<b) return b;
    return a;
}
struct Segmant{
    long long max, lmax, rmax, sum;
}Tree[21000];
struct data{
    int x, y, w, Cy;
}Gold[3100];
bool cmpx(data i, data j){
    return i.x<j.x;
}
bool cmpy(data i, data j){
    return i.y<j.y;
}
void Setting(int p, int low, int high, int target, int W){
    if(Mp<p) Mp=p;
    if(low==high){
        Tree[p].max+=W;
        Tree[p].lmax+=W;
        Tree[p].rmax+=W;
        Tree[p].sum+=W;
        return;
    }
    if(target<=(low+high)/2) Setting(p*2, low, (low+high)/2, target, W);
    else Setting(p*2+1, (low+high)/2+1, high, target, W);
    Tree[p].lmax=Fmax(Tree[p*2].sum+Tree[p*2+1].lmax, Tree[p*2].lmax);
    Tree[p].rmax=Fmax(Tree[p*2].rmax+Tree[p*2+1].sum, Tree[p*2+1].rmax);
    Tree[p].sum=Tree[p*2].sum+Tree[p*2+1].sum;
    Tree[p].max=Fmax(Fmax(Tree[p*2].max, Tree[p*2+1].max), Fmax(Tree[p*2].rmax+Tree[p*2+1].lmax, Tree[p].sum));
}
int main(){
    int N, i, j, k, l, MaxCy;
    scanf("%d", &N);
    for(i=1; i<=N; i++) scanf("%d %d %d", &Gold[i].x, &Gold[i].y, &Gold[i].w);
    std::sort(Gold+1, Gold+N+1, cmpy);
    for(i=1; i<=N; i++){
        Gold[i].Cy=Gold[i-1].Cy;
        if(Gold[i].y!=Gold[i-1].y || i==1) Gold[i].Cy++;
    }
    MaxCy=Gold[N].Cy;
    std::sort(Gold+1, Gold+N+1, cmpx);
    for(i=1; i<=N; i++){
        for(j=i; j<=N; j++){
            Setting(1, 1, MaxCy, Gold[j].Cy, Gold[j].w);
            if(Res<Tree[1].max && (Gold[j].x!=Gold[j+1].x || j==N)) Res=Tree[1].max;
        }
        for(j=1; j<=Mp; j++) Tree[j].max=Tree[j].lmax=Tree[j].rmax=Tree[j].sum=0;
    }
    printf("%lld", Res);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

금광 질문 있습니다

leekh100000 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말