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 |
|
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 |