Submission #87170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
87170	2018-11-29T22:03:11 Z	MatheusLealV	Go (COCI18_go)	C++17	30 / 100	228 ms	173760 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 + 1), 0);

		if(r <= m) dir = solve(l, r + 1, t + v[r + 1].A - v[l].A + 1, 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 + 1, 0) ;

		if(r <= m) dir = solve(l, r + 1, t + v[r + 1].A - v[r].A + 1, 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

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	173304 KB	Output is correct
2	Correct	142 ms	173432 KB	Output is correct
3	Incorrect	140 ms	173516 KB	Output isn't correct
4	Correct	143 ms	173588 KB	Output is correct
5	Incorrect	160 ms	173588 KB	Output isn't correct
6	Incorrect	162 ms	173588 KB	Output isn't correct
7	Incorrect	201 ms	173624 KB	Output isn't correct
8	Incorrect	205 ms	173624 KB	Output isn't correct
9	Incorrect	228 ms	173624 KB	Output isn't correct
10	Incorrect	212 ms	173760 KB	Output isn't correct