글 읽기 - 시간초과 질문

zxcv551133 6년 전 0

아래와 같은 코드로 N^2logN 의 시간복잡도가 되게 제출을 했습니다.

어떤 부분이 문제일까요

#ifndef ONLINE_JUDGE
#define _CRT_SECURE_NO_WARNINGS
#endif // !ONLINE_JUDGE
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <map>
#include <queue>
#include <functional> //greater less
using namespace std;
const int I32MAX = 2147483647;
const vector<pair<int, int>> cardinalP = { {0,1}, {0,-1}, {-1,0}, {1,0} };
// write below



int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif // !ONLINE_JUDGE
	cin.tie(0); ios_base::sync_with_stdio(0);

	//write your code below
	int n; cin >> n;
	vector<int> ar(n); for (int i = 0; i < n; i++) cin >> ar[i];
	sort(ar.begin(), ar.end());

	map<pair<int, int>, int> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (m.find({ j,ar[i] - ar[j] }) != m.end()) {
				m[{ i, ar[i] - ar[j] }] = 1 + m[{ j, ar[i] - ar[j] }];
			}
			else {
				m[{ i, ar[i] - ar[j] }] = 1;
			}
		}
	}
	int ans = 0;
	for (auto it = m.begin(); it != m.end(); it++) {
		ans = max(ans, (*it).second);
	}
	cout << ans +1 << '\n';
	// code ended
	return 0;
}

lim551 6년 전 1

m에 총 N^2개의 원소가 들어갈 수 있으니

시간복잡도가 N^2logN이 아니라 N^3 같네요 ㅎㅎ

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

문제

문제

출처

ICPC

시간초과 질문

zxcv551133 6년 전 0

lim551 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말