Submission #221975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
221975	2020-04-11T16:19:32 Z	ZwariowanyMarcin	Go (COCI18_go)	C++14	100 / 100	247 ms	157328 KB

go

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define sz(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
#define cint int&
 
using namespace std;

const int nax = 2010;
const int inf = 1e9;

void maxi(int &a, int b) {
	a = max(a, b);
}

int n, k, m;
int a[nax], b[nax], c[nax];

int dp[101][101][2001][2]; // dp[l][r][t] maksymalny wynik, jeśli odwiedziliśmy od l do r budynku do czasu t i jestemy w czyms :0

int main() {
	scanf ("%d%d%d", &n, &k, &m);
	rep(l, 1, m)
		rep(r, 1, m)
			rep(t, 0, 2000)
				rep(g, 0, 1)
					dp[l][r][t][g] = -inf;
	rep(i, 1, m) {
		scanf ("%d%d%d", a + i, b + i, c + i);
		int czas = abs(k - a[i]) + 1;
		dp[i][i][czas][0] = (czas <= c[i] ? b[i] : 0);
	}
	int res = 0;
	rep(len, 1, m) 
		rep(l, 1, m - len + 1) {
			int r = l + len - 1;
			rep(czas, 0, 2000) {
				maxi(res, dp[l][r][czas][0]);
				maxi(res, dp[l][r][czas][1]);
				int l1 = abs(a[l] - a[l - 1]);
				int l2 = abs(a[r] - a[l - 1]);
				int r1 = abs(a[r + 1] - a[l]);
				int r2 = abs(a[r + 1] - a[r]);
				if (l != 1) {
					if (czas + l1 <= 2000)
					maxi(dp[l - 1][r][czas + l1][0], dp[l][r][czas][0] + (czas + l1 <= c[l - 1] ? b[l - 1] : 0));
					if (czas + l2 <= 2000)
					maxi(dp[l - 1][r][czas + l2][0], dp[l][r][czas][1] + (czas + l2 <= c[l - 1] ? b[l - 1] : 0));
				}
				if (r != m) {
					if (czas + r1 <= 2000)
					maxi(dp[l][r + 1][czas + r1][1], dp[l][r][czas][0] + (czas + r1 <= c[r + 1] ? b[r + 1] : 0));
					if (czas + r2 <= 2000)
					maxi(dp[l][r + 1][czas + r2][1], dp[l][r][czas][1] + (czas + r2 <= c[r + 1] ? b[r + 1] : 0));					
				}
			}
		}
	printf ("%d\n", res);					
						
	
	return 0;
}

Compilation message

go.cpp: In function 'int main()':
go.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &n, &k, &m);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
go.cpp:37:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d", a + i, b + i, c + i);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	640 KB	Output is correct
2	Correct	7 ms	1920 KB	Output is correct
3	Correct	9 ms	3456 KB	Output is correct
4	Correct	14 ms	6784 KB	Output is correct
5	Correct	67 ms	39808 KB	Output is correct
6	Correct	96 ms	57080 KB	Output is correct
7	Correct	126 ms	77432 KB	Output is correct
8	Correct	161 ms	100856 KB	Output is correct
9	Correct	203 ms	127480 KB	Output is correct
10	Correct	247 ms	157328 KB	Output is correct