# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
87420 | jovitre | Go (COCI18_go) | C++14 | 246 ms | 173584 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |