글 읽기 - 계속 시간초과가 되는데 어떻게 고쳐야하죠?

jhjh307 7년 전 0

계속 시간초과하는데 어떻게 고치면 될까요?

#include <stdio.h>
#define len 200000
int main(void)
{
    int i,N,a,b,tot=0,a1[len],b1[len],n;
    scanf("%d",&N);
    for(i=0; i<N; i++)
    {
        scanf("%d %d",&a,&b);
        a1[i]=a;
        b1[i]=b;
    }
    for(i=0; i<N; i++)
    {
        for(n=i; n<N; n++)
        {
            if(a1[i]!=a1[n+1] && b1[i]>b1[n+1])
                tot+=b1[n+1];
            else
                tot+=0;
        }
        for(n=i; n>0; n--)
        {
            if(a1[i]!=a1[n-1] && b1[i]>b1[n-1])
                tot+=b1[n-1];
            else
                tot+=0;
        }
        printf("%d\n",tot);
        tot=0;
    }
    return 0;
}

exqt 7년 전 1

실행 시간이 N^2에 비례하므로 N이 20만일 경우 시간초과가 발생합니다

저는 미리 정렬해서 이진탐색을 이용해 풀었어요

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

문제

문제

출처

ICPC

계속 시간초과가 되는데 어떻게 고쳐야하죠?

jhjh307 7년 전 0

exqt 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말