Submission #246867


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>

#include <unordered_map>

using namespace std; using namespace placeholders;

using VI = vector<int>; using VVI = vector<VI>;
using PII = pair<int,int>; using VPII = vector< pair<int,int> >;
template < typename T = int > using VT = vector<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() ); };

#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 PB( n ) push_back( n )
#define EB emplace_back

#define fst first
#define snd second

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;
	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 ].EB( 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();

	unordered_map<int,int> time2idx;
	REP( i, 0, M )
	{
		time2idx[ times[i] ] = i;
	}

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

	REP( i, 0, M )
	{
		REP( j, 0, n )
		{
			int t = times[i];
			VI ends;

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

			REP( k, 0, ends.size() )
			{
				int &next = dp[ time2idx[ ends[k] ] ];
				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 2189 Byte
Status AC
Exec Time 657 ms
Memory 1560 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 30 ms 984 KB
sample_02.txt AC 29 ms 992 KB
subtask1_01.txt AC 193 ms 1416 KB
subtask1_02.txt AC 30 ms 980 KB
subtask1_03.txt AC 159 ms 1240 KB
subtask1_04.txt AC 375 ms 1372 KB
subtask1_05.txt AC 87 ms 1180 KB
subtask1_06.txt AC 305 ms 1308 KB
subtask1_07.txt AC 41 ms 1112 KB
subtask1_08.txt AC 136 ms 1248 KB
subtask1_09.txt AC 43 ms 1152 KB
subtask1_10.txt AC 258 ms 1372 KB
subtask1_11.txt AC 42 ms 1156 KB
subtask1_12.txt AC 142 ms 1184 KB
subtask1_13.txt AC 199 ms 1416 KB
subtask1_14.txt AC 364 ms 1308 KB
subtask1_15.txt AC 604 ms 1372 KB
subtask1_16.txt AC 608 ms 1372 KB
subtask1_17.txt AC 597 ms 1440 KB
subtask1_18.txt AC 595 ms 1364 KB
subtask1_19.txt AC 635 ms 1376 KB
subtask1_20.txt AC 387 ms 1444 KB
subtask1_21.txt AC 403 ms 1496 KB
subtask1_22.txt AC 424 ms 1440 KB
subtask1_23.txt AC 400 ms 1504 KB
subtask1_24.txt AC 390 ms 1372 KB
subtask1_25.txt AC 405 ms 1496 KB
subtask1_26.txt AC 409 ms 1500 KB
subtask1_27.txt AC 390 ms 1368 KB
subtask1_28.txt AC 396 ms 1372 KB
subtask1_29.txt AC 422 ms 1368 KB
subtask1_30.txt AC 406 ms 1376 KB
subtask1_31.txt AC 403 ms 1560 KB
subtask1_32.txt AC 399 ms 1440 KB
subtask1_33.txt AC 397 ms 1372 KB
subtask1_34.txt AC 404 ms 1540 KB
subtask1_35.txt AC 398 ms 1372 KB
subtask1_36.txt AC 393 ms 1380 KB
subtask1_37.txt AC 394 ms 1496 KB
subtask1_38.txt AC 390 ms 1440 KB
subtask1_39.txt AC 384 ms 1544 KB
subtask1_40.txt AC 604 ms 1376 KB
subtask1_41.txt AC 612 ms 1372 KB
subtask1_42.txt AC 628 ms 1364 KB
subtask1_43.txt AC 613 ms 1368 KB
subtask1_44.txt AC 586 ms 1372 KB
subtask1_45.txt AC 629 ms 1376 KB
subtask1_46.txt AC 631 ms 1436 KB
subtask1_47.txt AC 625 ms 1368 KB
subtask1_48.txt AC 608 ms 1440 KB
subtask1_49.txt AC 601 ms 1376 KB
subtask1_50.txt AC 624 ms 1440 KB
subtask1_51.txt AC 614 ms 1376 KB
subtask1_52.txt AC 657 ms 1376 KB
subtask1_53.txt AC 614 ms 1384 KB
subtask1_54.txt AC 623 ms 1360 KB
subtask1_55.txt AC 646 ms 1356 KB
subtask1_56.txt AC 632 ms 1376 KB
subtask1_57.txt AC 610 ms 1364 KB
subtask1_58.txt AC 619 ms 1368 KB
subtask1_59.txt AC 605 ms 1440 KB