Code Formula 2014 本選

Submission #1513404

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;
				auto it=upper_bound(dp.begin(),dp.end(),l)-1;
				dp[i]=max(dp[i],*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状態 WA
Score得点 0
Source lengthソースコード長 1836 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 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 WA
subtask1_02.txt WA
subtask1_03.txt WA
subtask1_04.txt WA
subtask1_05.txt WA
subtask1_06.txt WA
subtask1_07.txt WA
subtask1_08.txt WA
subtask1_09.txt WA
subtask1_10.txt WA
subtask1_11.txt WA
subtask1_12.txt WA
subtask1_13.txt WA
subtask1_14.txt WA
subtask1_15.txt WA
subtask1_16.txt WA
subtask1_17.txt WA
subtask1_18.txt WA
subtask1_19.txt WA
subtask1_20.txt WA
subtask1_21.txt WA
subtask1_22.txt WA
subtask1_23.txt WA
subtask1_24.txt WA
subtask1_25.txt WA
subtask1_26.txt WA
subtask1_27.txt WA
subtask1_28.txt WA
subtask1_29.txt WA
subtask1_30.txt WA
subtask1_31.txt WA
subtask1_32.txt AC 27 ms 512 KB
subtask1_33.txt WA
subtask1_34.txt WA
subtask1_35.txt WA
subtask1_36.txt WA
subtask1_37.txt WA
subtask1_38.txt WA
subtask1_39.txt WA
subtask1_40.txt WA
subtask1_41.txt WA
subtask1_42.txt WA
subtask1_43.txt WA
subtask1_44.txt WA
subtask1_45.txt WA
subtask1_46.txt WA
subtask1_47.txt WA
subtask1_48.txt WA
subtask1_49.txt WA
subtask1_50.txt WA
subtask1_51.txt WA
subtask1_52.txt WA
subtask1_53.txt WA
subtask1_54.txt WA
subtask1_55.txt WA
subtask1_56.txt WA
subtask1_57.txt WA
subtask1_58.txt WA
subtask1_59.txt WA