#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 -- ;
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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
