Submission #221973

# Submission time Handle Problem Language Result Execution time Memory
221973 2020-04-11T16:04:47 Z ZwariowanyMarcin Go (COCI18_go) C++14
70 / 100
247 ms 157304 KB
#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]);
		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);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 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 Incorrect 66 ms 39808 KB Output isn't correct
6 Incorrect 87 ms 57080 KB Output isn't correct
7 Correct 123 ms 77432 KB Output is correct
8 Correct 161 ms 100984 KB Output is correct
9 Correct 204 ms 127608 KB Output is correct
10 Incorrect 247 ms 157304 KB Output isn't correct