답안 #140611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140611	2019-08-03T19:05:55 Z	MatheusLealV	3단 점프 (JOI19_jumps)	C++17	19 / 100	560 ms	242424 KB

jumps

#include <bits/stdc++.h>
#define N 5010
using namespace std;

int n, q, v[N], C[N][N], menor[N][N], dp[N][N];

int solve(int i, int j)
{
	if(i > j) return 0;

	if(dp[i][j] != -1) return dp[i][j];

	return dp[i][j] = max({solve(i + 1, j), solve(i, j - 1), C[i][j]});
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int i = 1; i <= n; i++) cin>>v[i];

	memset(dp, -1, sizeof dp);

	for(int i = 1; i <= n; i++)
	{
		menor[i][i] = v[i];

		for(int j = i + 1; j <= n; j++)
			menor[i][j] = max(menor[i][j - 1], v[j]);
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = i + 1; j <= n; j++)
		{
			int mid = (i + j)/2;

			C[i][j] = menor[i + 1][mid] + v[i] + v[j];
		}
	}

	cin>>q;

	for(int i = 1, l, r; i <= q; i++)
	{
		cin>>l>>r;

		cout<<solve(l, r)<<"\n";
	}
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	98680 KB	Output is correct
2	Correct	84 ms	99448 KB	Output is correct
3	Correct	83 ms	99448 KB	Output is correct
4	Correct	83 ms	99448 KB	Output is correct
5	Correct	83 ms	99448 KB	Output is correct
6	Correct	94 ms	99428 KB	Output is correct
7	Correct	83 ms	99444 KB	Output is correct
8	Correct	83 ms	99464 KB	Output is correct
9	Correct	96 ms	99448 KB	Output is correct
10	Correct	97 ms	99448 KB	Output is correct

Subtask #2

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	98680 KB	Output is correct
2	Correct	84 ms	99448 KB	Output is correct
3	Correct	83 ms	99448 KB	Output is correct
4	Correct	83 ms	99448 KB	Output is correct
5	Correct	83 ms	99448 KB	Output is correct
6	Correct	94 ms	99428 KB	Output is correct
7	Correct	83 ms	99444 KB	Output is correct
8	Correct	83 ms	99464 KB	Output is correct
9	Correct	96 ms	99448 KB	Output is correct
10	Correct	97 ms	99448 KB	Output is correct
11	Correct	528 ms	242400 KB	Output is correct
12	Correct	527 ms	242296 KB	Output is correct
13	Correct	536 ms	242424 KB	Output is correct
14	Correct	529 ms	242328 KB	Output is correct
15	Correct	524 ms	242424 KB	Output is correct
16	Correct	531 ms	241784 KB	Output is correct
17	Correct	560 ms	241692 KB	Output is correct
18	Correct	525 ms	241784 KB	Output is correct
19	Correct	544 ms	242424 KB	Output is correct

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	271 ms	199508 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 54.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	98680 KB	Output is correct
2	Correct	84 ms	99448 KB	Output is correct
3	Correct	83 ms	99448 KB	Output is correct
4	Correct	83 ms	99448 KB	Output is correct
5	Correct	83 ms	99448 KB	Output is correct
6	Correct	94 ms	99428 KB	Output is correct
7	Correct	83 ms	99444 KB	Output is correct
8	Correct	83 ms	99464 KB	Output is correct
9	Correct	96 ms	99448 KB	Output is correct
10	Correct	97 ms	99448 KB	Output is correct
11	Correct	528 ms	242400 KB	Output is correct
12	Correct	527 ms	242296 KB	Output is correct
13	Correct	536 ms	242424 KB	Output is correct
14	Correct	529 ms	242328 KB	Output is correct
15	Correct	524 ms	242424 KB	Output is correct
16	Correct	531 ms	241784 KB	Output is correct
17	Correct	560 ms	241692 KB	Output is correct
18	Correct	525 ms	241784 KB	Output is correct
19	Correct	544 ms	242424 KB	Output is correct
20	Runtime error	271 ms	199508 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Halted	0 ms	0 KB	-