글 읽기 - 시간초과가 나는데 이 문제는 어떻게 접근을 해야하나요?

kdy312 7년 전 1

여러가지 방법을 생각해 보았는데

전부 틀렸습니다.

입력받는 즉시 다른 배열에 값을 계산에서 부분 배열 길이 가 주어지면 그 배열의 인덱스값끼리 빼주는 방식 도 해보고

값을 계산해서 숫자가 더해지는 값만큼 다시 배열에 저장해서 차례로 더하는 방법도 해봤는데 아닙니다....

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
	int num[100005] = { 0 };
	int cal[100005] = { 0 };
	int many = 0;
	int cycle = 0;
	int num1 = 0, num2 = 0;
	long long total = 0;
	int ck = 1;

	cin >> many >> cycle;

	for (int i = 0; i < many; i++)
		scanf_s("%d", &num[i]);

	memcpy(cal, num, sizeof(num));

	for (int j = 0; j < cycle; j++)
	{
		scanf_s("%d %d", &num1, &num2);

		sort(cal + num1 - 1, cal + num2);

		for (int k = num1 - 1; k < num2; k++)
		{
			if (cal[k] == cal[k + 1])
				ck++;
			else
			{
				total += pow(ck, 2)*cal[k];
				ck = 1;
			}
		}
		memcpy(cal, num, sizeof(num));

		printf("%d\n", total);
		total = 0;
	}

	return 0;
}