글 읽기 - 시간초과가 왜 뜨는지 잘 모르겠습니다 ㅠㅠ

yomyom0824 5년 전 0

시간초과가 왜 뜨는지 잘 모르겠습니다 ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <math.h>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <regex>
#include <sstream>
#include <utility>
#include <list>
#define MAX 1000000000
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
int dx[] = { 0,1,-1,0,0 };
int dy[] = { 0,0,0,-1,1 };
int n, m;
int arr[50001];
int dp[66669][4];


int sol(int cur, int picked) {
	int &ret = dp[cur + m][picked];
	if (ret != -1) return ret;
	ret = 0;
	if (picked == 3) return ret = arr[cur + m - 1] - arr[cur - 1];
	int limit = n - (3 - picked) * m + 1;
	for (int next = cur + m; next <= limit; next++)
		ret = max(ret, sol(next, picked + 1));

	ret += arr[cur + m - 1] - (cur - 1 >= 0 ? arr[cur - 1] : 0);
	return ret;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(dp, -1, sizeof(dp));
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		arr[i] += arr[i - 1];
	}
	cin >> m;


	cout << sol(1 - m, 0);
	return 0;
}

choko100 1년 전 0

https://www.acmicpc.net/board/... 질문과 중복해서 게시된 것 같습니다! 해당 게시물에 댓글을 남겼는데 확인 부탁드립니다.

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

문제

문제

출처

ICPC

시간초과가 왜 뜨는지 잘 모르겠습니다 ㅠㅠ

yomyom0824 5년 전 0

choko100 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

​시간초과가 왜 뜨는지 잘 모르겠습니다 ㅠㅠ

yomyom0824 5년 전 0

choko100 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

시간초과가 왜 뜨는지 잘 모르겠습니다 ㅠㅠ