Submission #615166


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int INF = 1e9;



map< pair<int,int> , pair<int,int> > seg[3010];


int n;
int H[3010];
int M[3010],S[3010],E[3010];
void init(){
	vector< pair<int,int> > s[3010];
	for(int i = 0 ; i < n ; i++){
		s[M[i]].push_back({E[i],S[i]});
	}
	for(int i = 0 ; i < n ; i++){
		s[i].push_back({INF,INF});
		sort(s[i].begin(),s[i].end());
		for( auto &j : s[i] ) swap(j.first,j.second);
		for( auto j : s[i] ){
			for( auto k : s[i] ){
				if( j.second <= k.first ){
					seg[i][j] = k;
					break;
				}
			}
		}
	}
}


vector< pair<int,int> > info[100010];

int dp[100010];
int dfs(int x){
	if( x == 100005 ) return 0;
	if( dp[x] != -1 ) return dp[x];
	int ans = dfs(x+1);
	for( auto i : info[x] ){
		int y = i.first;
		int kind = i.second;
		pair<int,int> cur = {x,y};
		for(int k = 1 ; cur != pair<int,int>{INF,INF} ; k++){
			ans = max(dfs(cur.second) + H[k] , ans);
			cur = seg[kind][cur];
		}
	}
	return dp[x] = ans;
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		cin >> H[i];
		H[i] += H[i-1];
	}
	for(int i = 0 ; i < n ; i++){
		cin >> M[i] >> S[i] >> E[i];
		M[i]--;
		info[S[i]].push_back({E[i],M[i]});
	}
	init();
	for(int i = 100000 ; i >= 0 ; i--)
		dfs(i);
	cout << dfs(0) << endl;
}

Submission Info

Submission Time
Task D - 映画の連続視聴
User kyuridenamida
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1339 Byte
Status AC
Exec Time 81 ms
Memory 4396 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 61
Set Name Test Cases
All 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 34 ms 3680 KB
sample_02.txt AC 33 ms 3680 KB
subtask1_01.txt AC 39 ms 4128 KB
subtask1_02.txt AC 34 ms 3680 KB
subtask1_03.txt AC 39 ms 3996 KB
subtask1_04.txt AC 41 ms 4180 KB
subtask1_05.txt AC 37 ms 3936 KB
subtask1_06.txt AC 42 ms 4128 KB
subtask1_07.txt AC 32 ms 3748 KB
subtask1_08.txt AC 38 ms 4000 KB
subtask1_09.txt AC 35 ms 3740 KB
subtask1_10.txt AC 44 ms 4124 KB
subtask1_11.txt AC 35 ms 3752 KB
subtask1_12.txt AC 40 ms 4004 KB
subtask1_13.txt AC 48 ms 4064 KB
subtask1_14.txt AC 42 ms 4256 KB
subtask1_15.txt AC 44 ms 4260 KB
subtask1_16.txt AC 46 ms 4256 KB
subtask1_17.txt AC 46 ms 4264 KB
subtask1_18.txt AC 47 ms 4264 KB
subtask1_19.txt AC 45 ms 4260 KB
subtask1_20.txt AC 77 ms 4388 KB
subtask1_21.txt AC 75 ms 4384 KB
subtask1_22.txt AC 80 ms 4392 KB
subtask1_23.txt AC 76 ms 4392 KB
subtask1_24.txt AC 77 ms 4384 KB
subtask1_25.txt AC 77 ms 4388 KB
subtask1_26.txt AC 78 ms 4264 KB
subtask1_27.txt AC 75 ms 4384 KB
subtask1_28.txt AC 77 ms 4384 KB
subtask1_29.txt AC 77 ms 4388 KB
subtask1_30.txt AC 76 ms 4388 KB
subtask1_31.txt AC 78 ms 4388 KB
subtask1_32.txt AC 77 ms 4388 KB
subtask1_33.txt AC 76 ms 4268 KB
subtask1_34.txt AC 77 ms 4396 KB
subtask1_35.txt AC 78 ms 4388 KB
subtask1_36.txt AC 79 ms 4396 KB
subtask1_37.txt AC 81 ms 4384 KB
subtask1_38.txt AC 77 ms 4384 KB
subtask1_39.txt AC 80 ms 4388 KB
subtask1_40.txt AC 47 ms 4264 KB
subtask1_41.txt AC 46 ms 4252 KB
subtask1_42.txt AC 46 ms 4272 KB
subtask1_43.txt AC 46 ms 4260 KB
subtask1_44.txt AC 46 ms 4268 KB
subtask1_45.txt AC 47 ms 4256 KB
subtask1_46.txt AC 46 ms 4260 KB
subtask1_47.txt AC 44 ms 4324 KB
subtask1_48.txt AC 46 ms 4264 KB
subtask1_49.txt AC 47 ms 4264 KB
subtask1_50.txt AC 46 ms 4256 KB
subtask1_51.txt AC 46 ms 4260 KB
subtask1_52.txt AC 47 ms 4264 KB
subtask1_53.txt AC 46 ms 4252 KB
subtask1_54.txt AC 46 ms 4256 KB
subtask1_55.txt AC 46 ms 4264 KB
subtask1_56.txt AC 44 ms 4264 KB
subtask1_57.txt AC 46 ms 4256 KB
subtask1_58.txt AC 47 ms 4252 KB
subtask1_59.txt AC 46 ms 4252 KB