Submission #87174

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
87174	2018-11-29T22:08:51 Z	MatheusLealV	Go (COCI18_go)	C++17	100 / 100	223 ms	173684 KB

go

#include <bits/stdc++.h>
#define N 1050
#define Tmax 2005
#define f first
#define s second
using namespace std;

int n, m, k, dp[105][105][Tmax][2], mid;

struct TT
{
	int A, B, T, f;
} v[N];

bool cmp(TT l, TT r) {
	return l.A < r.A;
}

int solve(int l, int r, int t, int f)
{
	if( (l <= 0 and r > m + 1) or t >= Tmax) return 0;

	if(dp[l][r][t][f] != -1) return dp[l][r][t][f];

	if(f == 0)
	{
		int esq = 0, dir = 0, ganho = (v[l].T > t ? v[l].B : 0);

		if(l >= 2) esq = solve(l - 1, r, t + v[l].A - v[l - 1].A, 0);

		if(r <= m) dir = solve(l, r + 1, t + v[r + 1].A - v[l].A, 1);

		return dp[l][r][t][f] = max(esq, dir) + ganho;
	}	

	else
	{
		int esq = 0, dir = 0, ganho = (v[r].T > t ? v[r].B : 0);

		if(l >= 2) esq = solve(l - 1, r, t + v[r].A - v[l - 1].A, 0) ;

		if(r <= m) dir = solve(l, r + 1, t + v[r + 1].A - v[r].A, 1);

		return dp[l][r][t][f] = max(esq, dir) + ganho;	
	}
}

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

	cin>>n>>k>>m;

	memset(dp, -1, sizeof dp);

	for(int i = 1; i <= m; i++) cin>>v[i].A>>v[i].B>>v[i].T, v[i].f = 0;

	v[m + 1] = {k, 0, 0, 1};

	sort(v + 1, v + m + 2, cmp);

	for(int i = 1; i <= m + 1; i++)
	{
		if(v[i].f == 1)
		{
			cout<<solve(i, i, 0, 0)<<"\n";

			break;
		}
	}

	//cout<<solve(mid, mid, 0, 0)<<"\n";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	173304 KB	Output is correct
2	Correct	141 ms	173428 KB	Output is correct
3	Correct	140 ms	173492 KB	Output is correct
4	Correct	157 ms	173548 KB	Output is correct
5	Correct	178 ms	173548 KB	Output is correct
6	Correct	170 ms	173684 KB	Output is correct
7	Correct	189 ms	173684 KB	Output is correct
8	Correct	209 ms	173684 KB	Output is correct
9	Correct	223 ms	173684 KB	Output is correct
10	Correct	208 ms	173684 KB	Output is correct