Submission #244825


Source Code Expand

#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std; using namespace placeholders;

using LL = long long; using ULL = unsigned long long;
using VI = vector<int>; using VVI = vector<VI>;
using VS = vector<string>;
using SS = stringstream;
using PII = pair<int,int>; using VPII = vector< pair<int,int> >;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using VVT = VT< VT<T> >;
template < typename T = int > using LIM = numeric_limits<T>;

template < typename T > inline void input_n( VT< T > &out ) { copy_n( istream_iterator< T >( cin ), out.size(), out.begin() ); };
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()
#define AALL( a, t ) (t*)a, (t*)a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define EM emplace( n )
#define EB emplace_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

constexpr int INF = LIM<>::max() / 2;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI hs( n );
	input_n( hs );

	VI csum_hs( 1, 0 );
	partial_sum( ALL( hs ), back_inserter( csum_hs ) );

	VT< VPII > movies( n );
	VI times( 1, 0 );
	REP( i, 0, n )
	{
		int m, s, e;
		cin >> m >> s >> e;

		movies[ m - 1 ].emplace_back( s, e );

		times.PB( s );
		times.PB( e );
	}
	FOR( row, movies )
	{
		sort( ALL( row ), []( const PII &a, const PII &b ){ return a.snd < b.snd; } );
	}
	
	sort( ALL( times ) );
	times.erase( unique( ALL( times ) ), times.end() );

	const int M = times.size();

	VI dp( M, -INF );
	dp[0] = 0;

	REP( i, 0, M )
	{
		REP( j, 0, n )
		{
			if ( movies[j].empty() )
			{
				continue;
			}

			int t = times[i];
			VI ends( movies[j].size() + 1, INF );
			ends[0] = t;

			int selected = 0;
			FOR( movie, movies[j] )
			{
				if ( t <= movie.fst )
				{
					t = movie.snd;
					ends[ ++selected ] = t;
				}
			}

			REP( k, 1, ends.size() )
			{
				if ( ends[k] == INF )
				{
					break;
				}

				int &next = dp[ lower_bound( ALL( times ), ends[k] ) - times.begin() ];
				next = max( next, dp[i] + csum_hs[k] );
			}
		}
	}

	cout << *max_element( ALL( dp ) ) << endl;

	return 0;
}

Submission Info

Submission Time
Task D - 映画の連続視聴
User torus711
Language C++11 (GCC 4.8.1)
Score 100
Code Size 3031 Byte
Status AC
Exec Time 1071 ms
Memory 1064 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 25 ms 796 KB
sample_02.txt AC 23 ms 932 KB
subtask1_01.txt AC 312 ms 1060 KB
subtask1_02.txt AC 24 ms 800 KB
subtask1_03.txt AC 227 ms 800 KB
subtask1_04.txt AC 613 ms 1060 KB
subtask1_05.txt AC 107 ms 924 KB
subtask1_06.txt AC 492 ms 976 KB
subtask1_07.txt AC 31 ms 800 KB
subtask1_08.txt AC 184 ms 804 KB
subtask1_09.txt AC 34 ms 928 KB
subtask1_10.txt AC 438 ms 1056 KB
subtask1_11.txt AC 35 ms 932 KB
subtask1_12.txt AC 204 ms 804 KB
subtask1_13.txt AC 328 ms 932 KB
subtask1_14.txt AC 600 ms 928 KB
subtask1_15.txt AC 989 ms 932 KB
subtask1_16.txt AC 984 ms 928 KB
subtask1_17.txt AC 993 ms 1052 KB
subtask1_18.txt AC 979 ms 1052 KB
subtask1_19.txt AC 989 ms 1060 KB
subtask1_20.txt AC 684 ms 936 KB
subtask1_21.txt AC 689 ms 996 KB
subtask1_22.txt AC 712 ms 932 KB
subtask1_23.txt AC 687 ms 932 KB
subtask1_24.txt AC 685 ms 1052 KB
subtask1_25.txt AC 693 ms 924 KB
subtask1_26.txt AC 694 ms 928 KB
subtask1_27.txt AC 687 ms 932 KB
subtask1_28.txt AC 686 ms 932 KB
subtask1_29.txt AC 699 ms 936 KB
subtask1_30.txt AC 693 ms 1056 KB
subtask1_31.txt AC 687 ms 936 KB
subtask1_32.txt AC 685 ms 1052 KB
subtask1_33.txt AC 694 ms 1056 KB
subtask1_34.txt AC 697 ms 996 KB
subtask1_35.txt AC 691 ms 932 KB
subtask1_36.txt AC 706 ms 1056 KB
subtask1_37.txt AC 694 ms 936 KB
subtask1_38.txt AC 688 ms 1064 KB
subtask1_39.txt AC 685 ms 932 KB
subtask1_40.txt AC 989 ms 932 KB
subtask1_41.txt AC 984 ms 932 KB
subtask1_42.txt AC 1003 ms 928 KB
subtask1_43.txt AC 982 ms 1060 KB
subtask1_44.txt AC 976 ms 936 KB
subtask1_45.txt AC 977 ms 932 KB
subtask1_46.txt AC 1071 ms 928 KB
subtask1_47.txt AC 991 ms 932 KB
subtask1_48.txt AC 990 ms 932 KB
subtask1_49.txt AC 978 ms 932 KB
subtask1_50.txt AC 985 ms 1056 KB
subtask1_51.txt AC 989 ms 928 KB
subtask1_52.txt AC 986 ms 936 KB
subtask1_53.txt AC 987 ms 932 KB
subtask1_54.txt AC 991 ms 932 KB
subtask1_55.txt AC 986 ms 932 KB
subtask1_56.txt AC 978 ms 928 KB
subtask1_57.txt AC 984 ms 996 KB
subtask1_58.txt AC 980 ms 928 KB
subtask1_59.txt AC 987 ms 1056 KB