제출 #87170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87170		MatheusLealV	Go (COCI18_go)	C++17	30 / 100	228 ms	173760 KiB

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 / 100