#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(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 pa {
int c , f , v ;
} a [maxn] , b [maxn] ;
bool cmp_f ( pa u , pa v )
{
return u.f > v.f ;
}
int sum_c ;
ll dp [100009] ;
void update ( pa A , int id )
{
vl F (sum_c+2,-1e18) ;
for ( int i = 0 ; i <= sum_c ; i ++ )
{
int New = i+A.c*id ;
if ( New >= 0 && New <= sum_c ) chkmax (F[New],dp[i]-A.v*id) ;
}
for ( int i = 0 ; i <= sum_c ; i ++ ) chkmax (dp[i],F[i]) ;
}
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0) ;
// rf () ;
cin >> n ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i].c >> a[i].f >> a[i].v , sum_c += a[i].c ;
cin >> m ;
for ( int i = 1 ; i <= m ; i ++ ) cin >> b[i].c >> b[i].f >> b[i].v ;
sort (a+1,a+n+1,cmp_f) ;
sort (b+1,b+m+1,cmp_f) ;
memset ( dp , -0x3f , sizeof dp ) ;
dp [0] = 0 ;
int j = 1 ;
for ( int i = 1 ; i <= m ; i ++ )
{
while ( j <= n && a[j].f >= b[i].f ) update (a[j++],1) ;
update (b[i],-1) ;
}
ll res = 0 ;
for ( int i = 0 ; i <= sum_c ; i ++ ) chkmax (res,dp[i]) ;
cout << res ;
}
// range , error , check special , ...
// find key , find key
//'-std=c++11' stay hard
// there is no tomorrow
Compilation message
clo.cpp: In function 'void rf()':
clo.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) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
3 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4696 KB |
Output is correct |
7 |
Correct |
4 ms |
4700 KB |
Output is correct |
8 |
Correct |
4 ms |
4744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
58 ms |
4764 KB |
Output is correct |
6 |
Correct |
3 ms |
4696 KB |
Output is correct |
7 |
Correct |
186 ms |
5168 KB |
Output is correct |
8 |
Correct |
55 ms |
4700 KB |
Output is correct |
9 |
Correct |
394 ms |
5416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
2 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
16 ms |
4780 KB |
Output is correct |
4 |
Correct |
3 ms |
4572 KB |
Output is correct |
5 |
Correct |
429 ms |
5116 KB |
Output is correct |
6 |
Correct |
818 ms |
5652 KB |
Output is correct |
7 |
Correct |
743 ms |
5464 KB |
Output is correct |
8 |
Correct |
752 ms |
5464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4696 KB |
Output is correct |
3 |
Correct |
48 ms |
4912 KB |
Output is correct |
4 |
Correct |
10 ms |
4592 KB |
Output is correct |
5 |
Correct |
784 ms |
5464 KB |
Output is correct |
6 |
Correct |
794 ms |
5468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
3 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4696 KB |
Output is correct |
7 |
Correct |
4 ms |
4700 KB |
Output is correct |
8 |
Correct |
4 ms |
4744 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
1 ms |
4700 KB |
Output is correct |
11 |
Correct |
1 ms |
4700 KB |
Output is correct |
12 |
Correct |
1 ms |
4700 KB |
Output is correct |
13 |
Correct |
58 ms |
4764 KB |
Output is correct |
14 |
Correct |
3 ms |
4696 KB |
Output is correct |
15 |
Correct |
186 ms |
5168 KB |
Output is correct |
16 |
Correct |
55 ms |
4700 KB |
Output is correct |
17 |
Correct |
394 ms |
5416 KB |
Output is correct |
18 |
Correct |
1 ms |
4700 KB |
Output is correct |
19 |
Correct |
1 ms |
4700 KB |
Output is correct |
20 |
Correct |
1 ms |
4700 KB |
Output is correct |
21 |
Correct |
1 ms |
4700 KB |
Output is correct |
22 |
Correct |
1 ms |
4700 KB |
Output is correct |
23 |
Correct |
1 ms |
4700 KB |
Output is correct |
24 |
Correct |
2 ms |
4700 KB |
Output is correct |
25 |
Correct |
1 ms |
4700 KB |
Output is correct |
26 |
Correct |
1 ms |
4700 KB |
Output is correct |
27 |
Correct |
1 ms |
4700 KB |
Output is correct |
28 |
Correct |
16 ms |
4780 KB |
Output is correct |
29 |
Correct |
3 ms |
4572 KB |
Output is correct |
30 |
Correct |
429 ms |
5116 KB |
Output is correct |
31 |
Correct |
818 ms |
5652 KB |
Output is correct |
32 |
Correct |
743 ms |
5464 KB |
Output is correct |
33 |
Correct |
752 ms |
5464 KB |
Output is correct |
34 |
Correct |
1 ms |
4696 KB |
Output is correct |
35 |
Correct |
1 ms |
4696 KB |
Output is correct |
36 |
Correct |
48 ms |
4912 KB |
Output is correct |
37 |
Correct |
10 ms |
4592 KB |
Output is correct |
38 |
Correct |
784 ms |
5464 KB |
Output is correct |
39 |
Correct |
794 ms |
5468 KB |
Output is correct |
40 |
Correct |
49 ms |
4772 KB |
Output is correct |
41 |
Correct |
149 ms |
5032 KB |
Output is correct |
42 |
Correct |
11 ms |
4700 KB |
Output is correct |
43 |
Correct |
856 ms |
5544 KB |
Output is correct |
44 |
Correct |
890 ms |
5588 KB |
Output is correct |
45 |
Correct |
807 ms |
5592 KB |
Output is correct |
46 |
Correct |
6 ms |
4700 KB |
Output is correct |
47 |
Correct |
10 ms |
4700 KB |
Output is correct |
48 |
Correct |
10 ms |
4796 KB |
Output is correct |