#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3yqVz8E ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
int dp[2011][102][102][2];
signed main(){
_3yqVz8E;
int n,k,m;
cin>>n>>k>>m;
using T=pair<int,pii>;
vec(T) a(m);
rep(i,m){
cin>>a[i].fi>>a[i].se.fi>>a[i].se.se;
}
sort(a.begin(),a.end());
const int _til=2001;
const int inf=1e9;
rep(i,_til){
rep(l,m){
rep(r,m){
rep(t,2){
dp[i][l][r][t]=-inf;
}
}
}
}
int ans=0;
rep(j,m){
int i=abs(k-a[j].fi);
int now=0;
if(i<a[j].se.se) now=a[j].se.fi;
dp[i][j][j][0]=now;
ans=max(ans,now);
}
rep(i,_til){
rep(l,m){
rng(r,l,m){
rep(t,2){
ans=max(ans,dp[i][l][r][t]);
// if(dp[i][l][r][t]!=-inf) print(i,l,r,t,dp[i][l][r][t]);
int pvt=a[l].fi;
if(t) pvt=a[r].fi;
if(l){
int _dist=abs(pvt-a[l-1].fi);
if(i+_dist<_til){
dp[i+_dist][l-1][r][0]=max(dp[i+_dist][l-1][r][0],dp[i][l][r][t]+(i+_dist<a[l-1].se.se?a[l-1].se.fi:0));
}
}
if(r+1<m){
int _dist=abs(pvt-a[r+1].fi);
if(i+_dist<_til){
int now=dp[i][l][r][t]+(i+_dist<a[r+1].se.se?a[r+1].se.fi:0);
if(i+_dist<a[r+1].se.se and now==10){
print("go",l,r,t,dp[i][l][r][t]);
}
dp[i+_dist][l][r+1][1]=max(dp[i+_dist][l][r+1][1],dp[i][l][r][t]+(i+_dist<a[r+1].se.se?a[r+1].se.fi:0));
}
}
}
}
}
}
print(ans);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
13396 KB |
Output is correct |
2 |
Correct |
16 ms |
22996 KB |
Output is correct |
3 |
Correct |
22 ms |
29504 KB |
Output is correct |
4 |
Correct |
38 ms |
39196 KB |
Output is correct |
5 |
Correct |
163 ms |
87476 KB |
Output is correct |
6 |
Correct |
206 ms |
103628 KB |
Output is correct |
7 |
Incorrect |
318 ms |
119692 KB |
Output isn't correct |
8 |
Correct |
429 ms |
135804 KB |
Output is correct |
9 |
Correct |
465 ms |
151884 KB |
Output is correct |
10 |
Correct |
669 ms |
163388 KB |
Output is correct |