Code Formula 2014 本選

Submission #1513420

Source codeソースコード

#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<58;
const double pi=acos(-1);
const double eps=1e-7;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
vi h,m,s,e;

int main(){
	cin>>n;
	h=m=s=e=vi(n);
	vp a(n+1);
	vector<vip> b(n);
	for(int i=0;i<n;i++){
		cin>>h[i];
		if(i) h[i]+=h[i-1];
	}
	for(int i=0;i<n;i++){
		cin>>m[i]>>s[i]>>e[i];
		m[i]--;
		a[i]={e[i],i};
		b[m[i]].push_back({{s[i],e[i]},i});
	}
	a[n]={0,-1};
	sort(a.begin(),a.end());
	for(int i=0;i<n;i++) sort(b[i].begin(),b[i].end());
	vi dp(n+1);
	for(int i=1;i<=n;i++){
		int I=a[i].second,J=0,l=inf,cnt=0;
		dp[i]=dp[i-1];
		while(b[m[I]][J].second!=I) J++;
		while(J>=0){
			P p=b[m[I]][J].first;
			if(p.second<=l){
				l=p.first;
				int it=upper_bound(a.begin(),a.end(),make_pair(l,inf))-a.begin()-1;
				dp[i]=max(dp[i],dp[it]+h[cnt]);
				cnt++;
			}
			J--;
		}
	}
	cout<<dp[n]<<endl;
}

Submission

Task問題 D - 映画の連続視聴
User nameユーザ名 MAK
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1861 Byte
File nameファイル名
Exec time実行時間 38 ms
Memory usageメモリ使用量 512 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask1_01.txt AC 7 ms 384 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 5 ms 384 KB
subtask1_04.txt AC 10 ms 384 KB
subtask1_05.txt AC 3 ms 256 KB
subtask1_06.txt AC 9 ms 384 KB
subtask1_07.txt AC 2 ms 256 KB
subtask1_08.txt AC 5 ms 384 KB
subtask1_09.txt AC 2 ms 256 KB
subtask1_10.txt AC 8 ms 384 KB
subtask1_11.txt AC 2 ms 256 KB
subtask1_12.txt AC 5 ms 384 KB
subtask1_13.txt AC 7 ms 384 KB
subtask1_14.txt AC 10 ms 384 KB
subtask1_15.txt AC 13 ms 384 KB
subtask1_16.txt AC 13 ms 384 KB
subtask1_17.txt AC 13 ms 512 KB
subtask1_18.txt AC 13 ms 512 KB
subtask1_19.txt AC 13 ms 384 KB
subtask1_20.txt AC 37 ms 512 KB
subtask1_21.txt AC 38 ms 512 KB
subtask1_22.txt AC 38 ms 512 KB
subtask1_23.txt AC 38 ms 512 KB
subtask1_24.txt AC 37 ms 512 KB
subtask1_25.txt AC 37 ms 512 KB
subtask1_26.txt AC 38 ms 512 KB
subtask1_27.txt AC 38 ms 512 KB
subtask1_28.txt AC 38 ms 384 KB
subtask1_29.txt AC 37 ms 512 KB
subtask1_30.txt AC 38 ms 512 KB
subtask1_31.txt AC 38 ms 512 KB
subtask1_32.txt AC 37 ms 512 KB
subtask1_33.txt AC 38 ms 512 KB
subtask1_34.txt AC 38 ms 512 KB
subtask1_35.txt AC 37 ms 512 KB
subtask1_36.txt AC 38 ms 512 KB
subtask1_37.txt AC 38 ms 512 KB
subtask1_38.txt AC 37 ms 512 KB
subtask1_39.txt AC 37 ms 512 KB
subtask1_40.txt AC 13 ms 384 KB
subtask1_41.txt AC 13 ms 512 KB
subtask1_42.txt AC 13 ms 384 KB
subtask1_43.txt AC 13 ms 512 KB
subtask1_44.txt AC 13 ms 512 KB
subtask1_45.txt AC 13 ms 512 KB
subtask1_46.txt AC 12 ms 512 KB
subtask1_47.txt AC 13 ms 512 KB
subtask1_48.txt AC 12 ms 512 KB
subtask1_49.txt AC 12 ms 512 KB
subtask1_50.txt AC 12 ms 512 KB
subtask1_51.txt AC 13 ms 512 KB
subtask1_52.txt AC 13 ms 512 KB
subtask1_53.txt AC 13 ms 512 KB
subtask1_54.txt AC 13 ms 384 KB
subtask1_55.txt AC 13 ms 384 KB
subtask1_56.txt AC 13 ms 512 KB
subtask1_57.txt AC 13 ms 512 KB
subtask1_58.txt AC 13 ms 512 KB
subtask1_59.txt AC 13 ms 384 KB