Submission #87420

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
87420	2018-11-30T20:47:52 Z	jovitre	Go (COCI18_go)	C++14	100 / 100	246 ms	173584 KB

go

#include <bits/stdc++.h>

using namespace std;

#define MAXN 2005
#define MAXSZ 2050
#define INF 999999999999999
#define pb push_back

typedef long long ll;
typedef pair <ll, ll> pii;
typedef vector <int> vi;
typedef pair <ll, pii> ppi;

struct houses {
	int h, w, t;
} house[MAXN];

int n, k, m;
int dp[105][105][MAXN][2];

bool comp(houses a, houses b){
	return a.h < b.h;
}

int calc(int l, int r, int tempo, int p){
	if(l < 1 or r > m + 1 or tempo >= MAXN) return 0;

	if(dp[l][r][tempo][p] != -1) return dp[l][r][tempo][p];

	houses atual = p ? house[r] : house[l];

	int lQuery = 0, rQuery = 0;
	int peso = atual.t > tempo ? atual.w : 0;

	if(l > 1) lQuery = calc(l - 1, r, tempo + (atual.h - house[l - 1].h), 0);
	if(r <= m) rQuery = calc(l, r + 1, tempo + (house[r + 1].h - atual.h), 1);

	return dp[l][r][tempo][p] = max(lQuery, rQuery) + peso;
}

int main(){
	scanf("%d%d%d", &n, &k, &m);

	int a, b, c;

	for(int i = 1; i <= m; i++){
		scanf("%d%d%d", &a, &b, &c);
		house[i] = {a, b, c};
	}

	house[m + 1] = {k, 0, 0};

	sort(house + 1, house + m + 2, comp);
	memset(dp, -1, sizeof(dp));

	int start = 0;

	for(int i = 1; i <= m + 1 && !start; i++){
		if(house[i].h == k) start = i;
	}

	int res = calc(start, start, 0, 0);

	printf("%d\n", res);

	return 0;
}

Compilation message

go.cpp: In function 'int main()':
go.cpp:43:7: 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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	173432 KB	Output is correct
2	Correct	158 ms	173440 KB	Output is correct
3	Correct	152 ms	173556 KB	Output is correct
4	Correct	148 ms	173556 KB	Output is correct
5	Correct	175 ms	173556 KB	Output is correct
6	Correct	175 ms	173556 KB	Output is correct
7	Correct	198 ms	173584 KB	Output is correct
8	Correct	215 ms	173584 KB	Output is correct
9	Correct	246 ms	173584 KB	Output is correct
10	Correct	217 ms	173584 KB	Output is correct