oj.uz

답안 #87420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
87420 2018-11-30T20:47:52 Z jovitre Go (COCI18_go) C++14
100 / 100
 246 ms 173584 KB 
#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

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