Submission #1227267


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());
  unordered_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;
        t=r[vp[j][k].first];
	d+=h[x];
	dp[t]=max(dp[t],dp[i]+d);
	x++;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Submission Time
Task D - 映画の連続視聴
User aizu_b
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1014 Byte
Status AC
Exec Time 673 ms
Memory 896 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 63
Set Name Test Cases
All sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask1_43.txt, subtask1_44.txt, subtask1_45.txt, subtask1_46.txt, subtask1_47.txt, subtask1_48.txt, subtask1_49.txt, subtask1_50.txt, subtask1_51.txt, subtask1_52.txt, subtask1_53.txt, subtask1_54.txt, subtask1_55.txt, subtask1_56.txt, subtask1_57.txt, subtask1_58.txt, subtask1_59.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 512 KB
sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 191 ms 640 KB
subtask1_02.txt AC 2 ms 256 KB
subtask1_03.txt AC 130 ms 512 KB
subtask1_04.txt AC 381 ms 768 KB
subtask1_05.txt AC 55 ms 512 KB
subtask1_06.txt AC 286 ms 640 KB
subtask1_07.txt AC 9 ms 384 KB
subtask1_08.txt AC 106 ms 512 KB
subtask1_09.txt AC 13 ms 384 KB
subtask1_10.txt AC 256 ms 640 KB
subtask1_11.txt AC 13 ms 384 KB
subtask1_12.txt AC 117 ms 512 KB
subtask1_13.txt AC 201 ms 640 KB
subtask1_14.txt AC 364 ms 768 KB
subtask1_15.txt AC 664 ms 768 KB
subtask1_16.txt AC 645 ms 768 KB
subtask1_17.txt AC 660 ms 768 KB
subtask1_18.txt AC 659 ms 768 KB
subtask1_19.txt AC 667 ms 768 KB
subtask1_20.txt AC 630 ms 896 KB
subtask1_21.txt AC 638 ms 768 KB
subtask1_22.txt AC 632 ms 896 KB
subtask1_23.txt AC 629 ms 768 KB
subtask1_24.txt AC 634 ms 896 KB
subtask1_25.txt AC 632 ms 768 KB
subtask1_26.txt AC 633 ms 768 KB
subtask1_27.txt AC 636 ms 768 KB
subtask1_28.txt AC 624 ms 768 KB
subtask1_29.txt AC 622 ms 768 KB
subtask1_30.txt AC 633 ms 768 KB
subtask1_31.txt AC 626 ms 768 KB
subtask1_32.txt AC 629 ms 768 KB
subtask1_33.txt AC 639 ms 768 KB
subtask1_34.txt AC 638 ms 768 KB
subtask1_35.txt AC 625 ms 768 KB
subtask1_36.txt AC 623 ms 896 KB
subtask1_37.txt AC 638 ms 896 KB
subtask1_38.txt AC 626 ms 896 KB
subtask1_39.txt AC 626 ms 896 KB
subtask1_40.txt AC 665 ms 768 KB
subtask1_41.txt AC 657 ms 768 KB
subtask1_42.txt AC 657 ms 768 KB
subtask1_43.txt AC 664 ms 768 KB
subtask1_44.txt AC 654 ms 768 KB
subtask1_45.txt AC 664 ms 768 KB
subtask1_46.txt AC 652 ms 768 KB
subtask1_47.txt AC 665 ms 768 KB
subtask1_48.txt AC 673 ms 768 KB
subtask1_49.txt AC 661 ms 768 KB
subtask1_50.txt AC 662 ms 768 KB
subtask1_51.txt AC 644 ms 768 KB
subtask1_52.txt AC 662 ms 768 KB
subtask1_53.txt AC 661 ms 896 KB
subtask1_54.txt AC 662 ms 768 KB
subtask1_55.txt AC 669 ms 768 KB
subtask1_56.txt AC 662 ms 768 KB
subtask1_57.txt AC 661 ms 768 KB
subtask1_58.txt AC 655 ms 768 KB
subtask1_59.txt AC 654 ms 768 KB