글 읽기 - TLE가 뜨는데요...

Rche 6년 전 0

N^2 log N = 3000 * 3000 * 11 = 99000000 ~ 0.99 sec 으로 될거라고 생각하는데 어떤 연산 과정에서 시간이 많이 잡아먹히는지 모르겠습니다.

#include <cstdio>
#include <vector>
#include <map>
using namespace std;

const int LIMIT = 1e6 + 1;
map <int,int> chk;
int T[3001][3001];
int main()
{

    int N;
    scanf("%d",&N);
    vector <int> data(N+1,0);
    for(int i=1; i<=N; i++) {
        scanf("%d",&data[i]);
        chk[data[i]] = i;
    }
    int ans = 0;
    int i,j;
    for(i=N-2; i>=1; i--) {
        for(j=N-1; j>=i+1; j--) {
            if(data[j] - data[i] + data[j] >= LIMIT) continue;
            int temp = chk[2*data[j] - data[i]];
            if(temp != 0) {
                T[i][j] = max(3*data[j],data[i] + T[j][temp]);
            }
            ans = max(ans,T[i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}

djm03178 6년 전 1

map이나 set 등은 최악의 케이스를 대비하기 위한 복잡한 자료구조를 사용해서 평균적으로 좀 느립니다. logN 치고는 무거울 수 있습니다.

접근을 O(1)에 하는 방법을 생각해보세요.

Rche 6년 전 0

해결했습니다! 감사합니다.

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

문제

문제

출처

ICPC

TLE가 뜨는데요...

Rche 6년 전 0

djm03178 6년 전 1

Rche 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말