Submission #1227231

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int dp[6666];
signed main(){
  int n;
  cin>>n;
  int h[n];
  for(int i=0;i<n;i++) cin>>h[i];
  int m[n],s[n],e[n];
  for(int i=0;i<n;i++) cin>>m[i]>>s[i]>>e[i];
  vector<int> vt;
  vector<P> vp[n];
  for(int i=0;i<n;i++){
    m[i]--;
    vp[m[i]].push_back(P(e[i],s[i]));
    vt.push_back(s[i]);
    vt.push_back(e[i]);
  }
  sort(vt.begin(),vt.end());
  vt.erase(unique(vt.begin(),vt.end()),vt.end());
  map<int,int> r;
  for(int i=0;i<(int)vt.size();i++) r[vt[i]]=i;

  for(int i=0;i<n;i++) sort(vp[i].begin(),vp[i].end());
  memset(dp,0,sizeof(dp));
  int ans=0;
  for(int i=0;i<=(int)vt.size();i++){
    ans=max(ans,dp[i]);
    for(int j=0;j<n;j++){
      for(int k=0,x=0,t=i,d=0;k<(int)vp[j].size();k++){
	if(r[vp[j][k].second]<t) continue;
	int u=r[vp[j][k].first];
	d+=h[x];
	dp[u]=max(dp[u],dp[i]+d);
	t=u;
	x++;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result