Submission #895537

#TimeUsernameProblemLanguageResultExecution timeMemory
895537thunoproTwo Dishes (JOI19_dishes)C++14
15 / 100
177 ms34144 KiB
#include<bits/stdc++.h> using namespace std ; #define ll long long #define maxn 200009 #define fi first #define se second #define pb push_back #define left id<<1 #define right id<<1|1 #define re exit(0); #define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 const int mod = 1e9+7 ; const int INF = 1e9 ; const int LOG = 18 ; typedef vector<int> vi ; typedef pair<int,int> pii ; typedef vector<ll> vl ; typedef vector<pii> vii ; void add ( int &a , int b ) { a += b ; if ( a < 0 ) a += mod ; if ( a >= mod ) a -= mod ; } template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } void rf () { freopen ("bai1.inp","r",stdin) ; // freopen ("bai1.out","w",stdout) ; } int _pow ( int a , int n ) { if ( n == 0 ) return 1 ; int res = _pow (a,n/2) ; if ( n % 2 ) return 1ll*res*res%mod*a%mod ; else return 1ll*res*res%mod ; } int n , m ; struct para{ int t ; ll end ; int score ; } a [maxn] , b [maxn] ; bool check_sub1 () { set <ll> S ; for ( int i = 1 ; i <= n ; i ++ ) S . insert (a[i].end) ; for ( int i = 1 ; i <= m ; i ++ ) S . insert (b[i].end) ; return (S.size() == 1) ; } void sub1 () { ll sum_scoreA [n+2] , sum_scoreB [m+2] ; sum_scoreA [0] = 0 ; sum_scoreB [0] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) sum_scoreA [i] = sum_scoreA [i-1] + a [i].score ; for ( int i = 1 ; i <= m ; i ++ ) sum_scoreB [i] = sum_scoreB [i-1] + b [i].score ; ll sum_timeA [n+2] , sum_timeB [m+2] ; sum_timeA [0] = 0 ; sum_timeB [0] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) sum_timeA [i] = sum_timeA [i-1] + a [i].t ; for ( int i = 1 ; i <= m ; i ++ ) sum_timeB [i] = sum_timeB [i-1] + b [i].t ; int j = m ; ll res = - 1e18 ; ll special_time = a [1].end ; for ( int i = 0 ; i <= n ; i ++ ) { while ( j && sum_timeA [i] + sum_timeB [j] > special_time ) j -- ; if ( sum_timeA [i] + sum_timeB [j] <= special_time ) chkmax (res,sum_scoreA [i] + sum_scoreB [j] ) ; } cout << res ; } void sub2 () { ll sum_timeA [n+2] , sum_timeB [m+2] ; sum_timeA [0] = 0 ; sum_timeB [0] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) sum_timeA [i] = sum_timeA [i-1] + a [i].t ; for ( int i = 1 ; i <= m ; i ++ ) sum_timeB [i] = sum_timeB [i-1] + b [i].t ; ll dp [n+2][m+2] ; memset ( dp , -0x3f , sizeof dp ) ; dp [0][0] = 0 ; for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= m ; j ++ ) { if ( i < n ) { int score ; if ( sum_timeA [i+1] + sum_timeB [j] <= a[i+1].end ) score = a[i+1].score ; else score = 0 ; chkmax (dp[i+1][j],dp[i][j]+score) ; } if ( j < m ) { int score ; if ( sum_timeA [i] + sum_timeB [j+1] <= b [j+1].end ) score = b [j+1].score ; else score = 0 ; chkmax (dp[i][j+1],dp[i][j]+score) ; } } } cout << dp [n][m] ; } int main () { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0) ; // rf () ; cin >> n >> m ; for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i].t >> a [i].end >> a [i].score ; for ( int i = 1 ; i <= m ; i ++ ) cin >> b [i].t >> b [i].end >> b [i].score ; if ( check_sub1 () ) sub1 () ; else if ( n <= 2000 && m <= 2000 ) sub2 () ; } // range , error , check speical , ... // find key , find key //'-std=c++11' stay hard // there is no tomorrow

Compilation message (stderr)

dishes.cpp: In function 'void rf()':
dishes.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...