oj.uz

답안 #87174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
87174 2018-11-29T22:08:51 Z MatheusLealV Go (COCI18_go) C++17
100 / 100
 223 ms 173684 KB 
#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

# 결과 실행 시간 메모리 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