| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1079423 |
2024-08-28T14:23:25 Z |
phong |
Two Dishes (JOI19_dishes) |
C++17 |
|
2613 ms |
1048576 KB |
#include<bits/stdc++.h>
#define ll long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, m;
struct node{
ll x, y, z;
}a[nmax], b[nmax];
map<int, ll> adj[nmax];
ll tree[nmax << 2];
ll dp[2005][2005];
void update(int id, int l, int r, int u, ll val){
if(l > u || r < u) return;
if(l == r){
tree[id] = max(tree[id], val);
return;
}
int mid = r + l >> 1;
update(id << 1, l, mid, u, val);
update(id << 1 |1, mid + 1, r, u, val);
tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
if(l >= u && r <=v) return tree[id];
int mid = r + l >> 1;
if(mid < u) return get(id << 1 | 1, mid + 1, r,u, v);
if(mid + 1 > v) return get(id << 1, l, mid, u, v);
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[i].z, a[i].x += a[i - 1].x;
for(int i = 1; i <= m; ++i) cin >> b[i].x >> b[i].y >> b[i].z, b[i].x += b[i - 1].x;
ll ans = 0;
for(int i = 1; i <= n; ++i){
if(a[i].x <= a[i].y){
int l = 1, r = m, it = m + 1;
while(l <= r){
int mid = r + l >> 1;
if(b[mid].x > a[i].y - a[i].x){
r = mid - 1;
it = mid;
}
else l = mid + 1;
}
ans += a[i].z;
if(it <= m) adj[i][it] -= a[i].z;
}
}
for(int i = 1; i <= m; ++i){
if(b[i].x <= b[i].y){
int l = 1, r = n, it = n + 1;
while(l <= r){
int mid = r + l >> 1;
if(a[mid].x > b[i].y - b[i].x){
r = mid - 1;
it = mid;
}
else l = mid + 1;
}
// cout << i << ' ' << it << endl;
if(it > n) ans += b[i].z;
else adj[it][i] += b[i].z;
}
}
// memset(dp, -63, sizeof dp);
// dp[0][0] = 0;
for(int i = 0; i <= n; ++i){
ll sum = 0;
for(int j = 0; j <= m; ++j){
// if(j > 0) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
sum += adj[i][j];
if(i > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j] + sum);
// cout << dp[i][j] << ' ';
}
}
cout << dp[n][m] + ans;
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
1
1 3
*/
Compilation message
dishes.cpp: In function 'void update(int, int, int, int, long long int)':
dishes.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid = r + l >> 1;
| ~~^~~
dishes.cpp: In function 'int get(int, int, int, int, int)':
dishes.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = r + l >> 1;
| ~~^~~
dishes.cpp: At global scope:
dishes.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
40 | main(){
| ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:53:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = r + l >> 1;
| ~~^~~
dishes.cpp:69:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = r + l >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2613 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2613 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2613 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
