글 읽기 - 1067번 질문(시간 초과)

insu_nym 7년 전 0

간단해보이는데 오랫동안 헤매고 있네요 ㅠㅠ

n = 60000일 때 대체 어떻게 2초 안에 결과를 낼 수 있나요?

힌트라도 부탁드립니다.

/*input
4
1 2 3 4
6 7 8 5
*/
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int arr1[60000];
int arr2[60000];
int mult[100][100];
int n;
long long int maxVal;


long long int getCalcResult(int offset) {
	long long int ret = 0;

	for (int i = 0; i < n; i++) {
		ret += mult[arr1[(i + offset) % n]][arr2[i]];
	}

	return ret;
}

int main(){
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr1[i]);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr2[i]);
	}

	for (int i = 1; i < 100; i++) {
		for (int j = i; j < 100; j++) {
			int temp = i * j;
			mult[i][j] = temp;
			mult[j][i] = temp;
		}
	}

	maxVal = 0;
	for(int i = 0; i < n; i++){
		maxVal = max(maxVal, getCalcResult(i));
	}

	cout<<maxVal;
	return 0;
}

kingsj0405 7년 전 0

친구가 FFT 알고리즘을 쓰면 n^2 -> n log n이 되서 풀린다고 하더군요.

그런데 저도 FFT 알고리즘을 배우는데 애먹는 중이라 정말인지는 모르겠습니다.

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

문제

문제

출처

ICPC

1067번 질문(시간 초과)

insu_nym 7년 전 0

kingsj0405 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말