oj.uz

Submission #721337

# Submission time Handle Problem Language Result Execution time Memory
721337 2023-04-10T17:40:02 Z lukameladze Two Dishes (JOI19_dishes) C++14
5 / 100
 550 ms 60492 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5, inf = 1e17;
int n,m,a[N],b[N],s[N],p[N],q[N],t[N],x[N],y[N],ans;
 
 
int maxim[4 * N], lazy[4 * N];
vector <pii> v[N];
int merge(int a, int b) {
	return max(a, b);
}
void push(int node, int le, int ri) {
	if (le == ri) {
		maxim[node] += lazy[node];
		lazy[node] = 0;
		return ;
	}
	maxim[2 * node] = max(maxim[2 * node], maxim[node]);
	maxim[2 * node + 1] = max(maxim[2 * node + 1], maxim[node]);
	maxim[node] += lazy[node];
	lazy[2 * node] += lazy[node];
	lazy[2 * node + 1] += lazy[node];
	
	lazy[node] = 0;	
	maxim[node] = -inf;
}
 
void build(int node, int le, int ri) {
	if (le == ri) {
		maxim[node] = 0;
		return ;
	} else maxim[node] = -inf;
	int mid = (le + ri) / 2;
	build(2 * node, le, mid);
	build(2 * node + 1, mid + 1, ri);
}
void update(int node, int le, int ri, int start, int end, int val) {
	push(node, le, ri);
	if (le > end || ri < start || start > end) return ;
	if (le >= start && ri <= end) {
		lazy[node] += val;
		push(node, le, ri);
		return ;
	}
	int mid = (le + ri) / 2;
	update(2 * node, le, mid, start, end, val);
	update(2 * node + 1, mid + 1, ri, start, end, val);
}
void maximize(int node, int le, int ri, int start, int end, int val) {
	push(node, le, ri);
	if (le > end || ri < start || start > end) return ;
	if (le >= start && ri <= end) {
		//cout<<node<<"      "<<val<<"\n";
		maxim[node] = max(maxim[node], val);
		push(node, le, ri);
		return ;
	}
	int mid = (le + ri) / 2;
	maximize(2 * node, le, mid,start,end,val);
	maximize(2 * node + 1, mid + 1, ri, start, end, val);
}
int getans(int node, int le, int ri, int idx) {
	push(node, le, ri);
	if (le > idx || ri < idx) return -inf;
	if (le == ri) {
		return maxim[node];	
	}
	int mid = (le + ri) / 2;
	return merge(getans(2 * node, le, mid, idx), getans(2 * node + 1, mid + 1, ri, idx));
}
/*
void prnt(int node, int le, int ri) {
//	cout<<node<<" "<<le<<" "<<ri<<"   "<<maxim[node]<<" "<<lazy[node]<<"\n";
	if (le == ri) return ; 
	int mid = (le + ri) / 2;
	prnt(2 * node, le, mid);
	prnt(2 * node + 1, mid + 1, ri);
}
 */
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (int i = 1; i <= n; i++) {
		cin>>a[i]>>s[i]>>p[i];
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= m; i++) {
		cin>>b[i]>>t[i]>>q[i];
		b[i] += b[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] > s[i]) continue;
		x[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b; // x[i] = minimum index such that pra[i] + prb[idx] > s[i] 
		if (x[i] > m) {
		    ans += p[i]; continue;
		}
		v[i].pb({x[i], p[i]});
	//	cout<<i<<"   "<<x[i]<<"\n";
	}
	build(1, 0, m);
	for (int i = 1; i <= m; i++) {
		if (b[i] > t[i]) continue;
		y[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a; // y[i] = minimum index such that prb[i] + pra[idx] > t[i];
		if (y[i] > n) {
		    ans += q[i]; continue; 
		}
	//	cout<<y[i]<<" --   "<<i<<"\n";
		ans += q[i];
		v[y[i]].pb({i, -q[i]});
	}
	for (int i = 1; i <= n; i++) {
		v[i].pb({m + 1, 0});
		sort(v[i].begin(), v[i].end());
		for (pii sth : v[i]) {
			int j = sth.f; int cost = sth.s; 
			update(1, 0, m, 0, j - 1, cost);
		}
		// prefix maximization
		for (pii sth : v[i]) {
			int j = sth.f; int cost = sth.s;
			int x = getans(1,0,m, j - 1);
			maximize(1,0,m,j, m,x);
		}
	/*	for (int i = 0; i <= m; i++) {
		    cout<<getans(1, 0, m, i)<<" ";
		}
		cout<<"\n";*/
	}
	int ans1 = -inf;
	for (int i = 1; i <= m; i++) {
		ans1 = max(ans1, getans(1,0,m, i));
	}
	cout<<ans + ans1<<"\n";
}

Compilation message

dishes.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main() {
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:125:23: warning: unused variable 'cost' [-Wunused-variable]
  125 |    int j = sth.f; int cost = sth.s;
      |                       ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 58324 KB Output is correct
2 Correct 533 ms 58952 KB Output is correct
3 Correct 247 ms 51064 KB Output is correct
4 Correct 454 ms 55200 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 490 ms 57088 KB Output is correct
7 Correct 127 ms 38348 KB Output is correct
8 Correct 97 ms 36632 KB Output is correct
9 Correct 288 ms 51064 KB Output is correct
10 Correct 538 ms 60492 KB Output is correct
11 Correct 227 ms 51036 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23780 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23876 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 13 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23780 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23876 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 13 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23780 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23876 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 13 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23780 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23876 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 13 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23780 KB Output is correct
2 Correct 12 ms 23776 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23876 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 13 ms 23892 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 58324 KB Output is correct
2 Correct 533 ms 58952 KB Output is correct
3 Correct 247 ms 51064 KB Output is correct
4 Correct 454 ms 55200 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 490 ms 57088 KB Output is correct
7 Correct 127 ms 38348 KB Output is correct
8 Correct 97 ms 36632 KB Output is correct
9 Correct 288 ms 51064 KB Output is correct
10 Correct 538 ms 60492 KB Output is correct
11 Correct 227 ms 51036 KB Output is correct
12 Correct 12 ms 23780 KB Output is correct
13 Correct 12 ms 23776 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 13 ms 23876 KB Output is correct
16 Correct 12 ms 23816 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Incorrect 13 ms 23892 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 58324 KB Output is correct
2 Correct 533 ms 58952 KB Output is correct
3 Correct 247 ms 51064 KB Output is correct
4 Correct 454 ms 55200 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 490 ms 57088 KB Output is correct
7 Correct 127 ms 38348 KB Output is correct
8 Correct 97 ms 36632 KB Output is correct
9 Correct 288 ms 51064 KB Output is correct
10 Correct 538 ms 60492 KB Output is correct
11 Correct 227 ms 51036 KB Output is correct
12 Correct 12 ms 23780 KB Output is correct
13 Correct 12 ms 23776 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 13 ms 23876 KB Output is correct
16 Correct 12 ms 23816 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Incorrect 13 ms 23892 KB Output isn't correct
20 Halted 0 ms 0 KB -