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

(追記) (追記ここまで)

금광 질문 있습니다

10167번 - 금광

leekh100000 10년 전 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;
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

금광 질문 있습니다

leekh100000 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말