글 읽기 - 시간초과

sminhyuck 4년 전 0

시간복잡도가 O(N+Q) 인 것 같은데 시간초과가 발생하네요

어디서 더 줄여야할지 잘 모르겠습니다.

#include <iostream>
using namespace std;
int COW[200001];
int CHANGE[200001];
int SUM[200001];
int N, Q;
long answer;

void init() {
	answer = 0;
	cin >> N >> Q;
	for (int i = 1; i <= N; i++)
		cin >> COW[i];
	for (int i = 1; i <= Q; i++)
		cin >> CHANGE[i];

	for (int i = 1; i <= N; i++) {
		int j = i;
		int sum = COW[i];
		for (int k = 0; k < 3; k++) {
			j++;
			if (j > N) j = j - N;
			sum = sum * COW[j];
		}
		SUM[i] = sum;
		answer += SUM[i];
	}
	
}

void TRICK();

int main() {
	init();
	TRICK();
}

void TRICK() {
	for (int i = 1; i <= Q; i++) {
		int index = CHANGE[i]; // 바뀔 소의 인덱스
		
		for (int j = 0; j < 4; j++) {
			answer -= SUM[index];
			SUM[index] = -SUM[index];
			answer += SUM[index];
			index--;
			if (index < 1) index = N;
		}
		
		cout << answer << endl;
	}
}

djm03178 4년 전 1

https://www.acmicpc.net/proble...

sminhyuck 4년 전 0

감사합니다! cin이 느리단걸 생각도 안하고있었네요 ㅎㅎ

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

문제

문제

출처

ICPC

시간초과

sminhyuck 4년 전 0

djm03178 4년 전 1

sminhyuck 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말