글 읽기 - 어디서 시간초과가 나는지 모르겠습니다.

pkc4913 4년 전 0

N = 100000이고 최대 계산횟수를 잡아봤자 90만회에서 멈추는데 0%에서 멈추다가 시간초과를 받습니다.

어디가 잘못된걸까요?

#include<bits/stdc++.h>
using namespace std;
int A[10001], prod[3], proa[3];
const int inf = 1e9;
int main() {
	int N; cin >> N;
	for(int i = 0; i < N; i++){
		scanf("%d", &A[i]);
	}
	if(N == 1){ printf("0"); return 0; }
	if(A[0] > A[N - 1]) reverse(A,A + N);
	proa[0] = A[0] - 1, proa[1] = A[0], proa[2] = A[0] + 1;
	int tmp = A[1] - A[0];
	prod[0] = tmp - 1 >= 0 ? tmp - 1 : 0, prod[1] = tmp, prod[2] = tmp + 1;
	int ans = inf;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			int val = 0;
			for(int k = 0; k < N; k++){
				int tmp2 = abs(proa[i] + k * prod[j] - A[k]);
				if(tmp2 > 1) {val = inf; break;}
				val += tmp2;
			}
			ans = min(ans,val);
		}
	}
	printf("%d",ans == inf ? -1 : ans);
}

sait2000 4년 전 0

A 크기가 틀렸습니다.

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

문제

문제

출처

ICPC

어디서 시간초과가 나는지 모르겠습니다.

pkc4913 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말