oj.uz

답안 #123332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123332 2019-07-01T07:29:42 Z 구재현(#3026) Two Dishes (JOI19_dishes) C++14
0 / 100
 21 ms 16888 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXT = 2100000;
const int mod = 1e9 + 7;
using lint = long long;
using pi = pair<int, int>;

struct pnt{
	int x, y;
	lint c;
	bool operator<(const pnt &p)const{
		return pi(x, y) < pi(p.x, p.y);
	}
};

struct seg{
	lint lazy[MAXT], tree[MAXT];
	void lazydown(int p){
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		tree[2*p] += lazy[p];
		tree[2*p+1] += lazy[p];
		lazy[p] = 0;
		tree[2*p] = max(tree[2*p], tree[p]);
		tree[2*p+1] = max(tree[2*p+1], tree[p]);
		tree[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, lint v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			lazy[p] += v;
			tree[p] += v;
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm + 1, pe, 2*p + 1, v);
	}
	void upperize(int s, int e, int ps, int pe, int p, lint v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p] = max(tree[p], v);
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		upperize(s, e, ps, pm, 2*p, v);
		upperize(s, e, pm+1, pe, 2*p+1, v);
	}
	lint query(int pos, int s, int e, int p){
		if(s == e) return tree[p];
		int m = (s + e) / 2;
		lazydown(p);
		if(pos <= m) return query(pos, s, m, 2*p);
		return query(pos, m+1, e, 2*p+1);
	}
}seg;

int n, m;
lint a[MAXN], s[MAXN], p[MAXN];
lint b[MAXN], t[MAXN], q[MAXN];
int da[MAXN], db[MAXN];
lint dp[MAXN];
vector<pnt> v, w;

lint getCostV(int s, int e, int x){
	lint ret = 0;
	for(auto &i : v){
		if(s <= i.x && i.x <= e && i.y >= x) ret += i.c; 
	}
	return ret;
}

lint getCostW(int s, int e, int x){
	lint ret = 0;
	for(auto &i : w){
		if(s <= i.x && i.x <= e && i.y <= x) ret += i.c; 
	}
	return ret;
}

int main(){
	scanf("%d %d",&n,&m);
	if(n > 2000 || m > 2000) return 0;
	for(int i=1; i<=n; i++){
		scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
		a[i] += a[i-1];
	}
	for(int i=1; i<=m; i++){
		scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
		b[i] += b[i-1];
	}
	lint ret = 0;
	v.push_back({0, 0, 0});
	for(int i=1; i<=n; i++){
		da[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b;
		if(da[i] > 0){
			if(p[i] > 0) v.push_back({i, da[i], p[i]});
			else w.push_back({i, da[i], -p[i]}), ret += p[i];
		}
	}
	for(int i=1; i<=m; i++){
		db[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a;
		if(db[i] > 0){
			if(q[i] > 0) w.push_back({db[i], i, q[i]});
			else v.push_back({db[i], i, -q[i]}), ret += q[i];
		}
	}
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	v.push_back({n + 1, m + 1, 0});
	lint tree[MAXT] = {};
//	fill(tree + 1, tree + m + 2, -1e18);
	int pw = 0;
	for(int i=1; i<v.size(); i++){
		for(int j = 0; j <= v[i].y; j++) tree[j] += v[i].c;
//		seg.add(0, v[i].y, 0, m + 1, 1, v[i].c);
		while(pw < w.size() && pi(w[pw].x, w[pw].y) <= pi(v[i].x, v[i].y)){
			for(int j = w[pw].y + 1; j <= m + 1; j++){
				tree[j] += w[pw].c;
			}
			pw++;
		}
		dp[i] = tree[v[i].y];
		for(int j=v[i].y + 1; j <= m + 1; j++){
			tree[j] = max(tree[j], dp[i]);
		}
	}
	lint dap = *max_element(tree, tree + MAXT);
	//dp[v.size() - 1];
	cout << ret + dap << endl;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<v.size(); i++){
               ~^~~~~~~~~
dishes.cpp:120:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pw < w.size() && pi(w[pw].x, w[pw].y) <= pi(v[i].x, v[i].y)){
         ~~~^~~~~~~~~~
dishes.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16888 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 21 ms 16888 KB Output is correct
4 Correct 18 ms 16888 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 18 ms 16888 KB Output is correct
7 Correct 17 ms 16888 KB Output is correct
8 Incorrect 17 ms 16888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16888 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 21 ms 16888 KB Output is correct
4 Correct 18 ms 16888 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 18 ms 16888 KB Output is correct
7 Correct 17 ms 16888 KB Output is correct
8 Incorrect 17 ms 16888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16888 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 21 ms 16888 KB Output is correct
4 Correct 18 ms 16888 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 18 ms 16888 KB Output is correct
7 Correct 17 ms 16888 KB Output is correct
8 Incorrect 17 ms 16888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16888 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 21 ms 16888 KB Output is correct
4 Correct 18 ms 16888 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 18 ms 16888 KB Output is correct
7 Correct 17 ms 16888 KB Output is correct
8 Incorrect 17 ms 16888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16888 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 21 ms 16888 KB Output is correct
4 Correct 18 ms 16888 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 18 ms 16888 KB Output is correct
7 Correct 17 ms 16888 KB Output is correct
8 Incorrect 17 ms 16888 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -