Submission #105847

#	Time	Username	Problem	Language	Result	Execution time	Memory
105847		Pro_ktmr	Two Dishes (JOI19_dishes)	C++14	0 / 100	4690 ms	1049600 KiB

dishes

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair

struct RSQ{
private:
	int N;
	vector<LL> node;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		for(int i=0; i<2*N-1; i++) node.PB(0LL);
	}
	void update(int k, LL x){
		k += N-1;
		node[k] = x;
		while(k > 0){
			k = (k-1)/2;
			node[k] = node[2*k+1] + node[2*k+2];
		}
	}
	LL sum(int a, int b, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		if(r <= a || b <= l) return 0;
		if(a <= l && r <= b) return node[k];
		return sum(a, b, 2*k+1, l, (l+r)/2) + sum(a, b, 2*k+2, (l+r)/2, r);
	}
	void print(){
		for(int i=0; i<node.size(); i++) cout << node[i] << " ";
		cout << endl;
	}
};

int N,M;
LL A[1000000],B[1000000],S[1000000],T[1000000],P[1000000],Q[1000000],yoyuA[1000000],yoyuB[1000000];
vector<pair<LL,LL>> v1,v2; //yoyu,point
RSQ rsq1,rsq2;

map<pair<int,int> , LL> dp;
LL solve(int i, int j, LL nowA, LL nowB, RSQ rsq1, RSQ rsq2){
	if(dp.count(MP(i,j)) == 1) return dp[MP(i,j)];
	LL ans = 0;
	while(i+j < N+M){
		//cout << "# " << i << " " << j << endl;
		if(j == M){
			if(yoyuA[i] >= nowB) ans += P[i];
			nowA += S[i];
			int idx = lower_bound(v1.begin(), v1.end(), MP(yoyuA[i], P[i])) - v1.begin();
			rsq1.update(idx,0);
			i++;
			continue;
		}
		if(i == N){
			if(yoyuB[j] >= nowA) ans += Q[j];
			nowB += T[j];
			int idx = lower_bound(v2.begin(), v2.end(), MP(yoyuB[j], Q[j])) - v2.begin();
			rsq2.update(idx,0);
			j++;
			continue;
		}
		int idx1 = lower_bound(v1.begin(), v1.end(), MP(nowB,LLONG_MIN)) - v1.begin();
		int idx2 = lower_bound(v1.begin(), v1.end(), MP(nowB+B[j],LLONG_MIN)) - v1.begin();
		LL tmpA = rsq1.sum(idx1, N) - rsq1.sum(idx2, N); //ima toranakya yabai
		//cout << idx1 << " " << idx2 << " " << tmpA << endl;
		idx1 = lower_bound(v2.begin(), v2.end(), MP(nowA,LLONG_MIN)) - v2.begin();
		idx2 = lower_bound(v2.begin(), v2.end(), MP(nowA+A[i],LLONG_MIN)) - v2.begin();
		LL tmpB = rsq2.sum(idx1, M) - rsq2.sum(idx2, M);
		//cout << idx1 << " " << idx2 << " " << tmpB << endl;
		if(tmpA == tmpB){
			if(yoyuA[i] >= nowB) ans += P[i];
			nowA += A[i];
			int idx = lower_bound(v1.begin(), v1.end(), MP(yoyuA[i], P[i])) - v1.begin();
			rsq1.update(idx,0);
			i++;
			LL tmp = ans + solve(i, j, nowA, nowB, rsq1, rsq2);
			i--;
			rsq1.update(idx,v1[i].second);
			nowA -= A[i];
			if(yoyuA[i] >= nowB) ans -= P[i];
			
			if(yoyuB[j] >= nowA) ans += Q[j];
			nowB += B[j];
			idx = lower_bound(v2.begin(), v2.end(), MP(yoyuB[j], Q[j])) - v2.begin();
			rsq2.update(idx,0);
			j++;
			return dp[MP(i,j)] = max(tmp, ans + solve(i, j, nowA, nowB, rsq1, rsq2));
		}
		else if(tmpA > tmpB){
			if(yoyuA[i] >= nowB) ans += P[i];
			nowA += A[i];
			int idx = lower_bound(v1.begin(), v1.end(), MP(yoyuA[i], P[i])) - v1.begin();
			rsq1.update(idx,0);
			i++;
			continue;
		}
		else{
			if(yoyuB[j] >= nowA) ans += Q[j];
			nowB += B[j];
			int idx = lower_bound(v2.begin(), v2.end(), MP(yoyuB[j], Q[j])) - v2.begin();
			rsq2.update(idx,0);
			j++;
			continue;
		}
	}
	return dp[MP(i,j)] = ans;
}

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++) scanf("%lld%lld%lld", A+i, S+i, P+i);
	for(int i=0; i<M; i++) scanf("%lld%lld%lld", B+i, T+i, Q+i);
	
	//
	
	LL wa = 0;
	for(int i=0; i<N; i++){
		wa += A[i];
		v1.PB(MP(S[i]-wa, P[i]));
		yoyuA[i] = S[i]-wa;
	}
	sort(v1.begin(), v1.end());
	//for(int i=0; i<N; i++) cout << v1[i].first << " " << v1[i].second << endl;
	wa = 0;
	for(int i=0; i<M; i++){
		wa += B[i];
		v2.PB(MP(T[i]-wa, Q[i]));
		yoyuB[i] = T[i]-wa;
	}
	sort(v2.begin(), v2.end());
	//for(int i=0; i<M; i++) cout << v2[i].first << " " << v2[i].second << endl;
	
	//
	
	rsq1.init(N);
	for(int i=0; i<N; i++){
		rsq1.update(i, v1[i].second);
	}
	//rsq1.print();
	rsq2.init(M);
	for(int i=0; i<M; i++){
		rsq2.update(i, v2[i].second);
	}
	//rsq2.print();
	
	//
	
	
	
	cout << solve(0,0,0,0,rsq1,rsq2) << endl;
	
	return 0;
}

Compilation message (stderr)

dishes.cpp: In member function 'void RSQ::print()':
dishes.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<node.size(); i++) cout << node[i] << " ";
                ~^~~~~~~~~~~~
dishes.cpp: In function 'int main()':
dishes.cpp:112: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:113:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%lld%lld%lld", A+i, S+i, P+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:114:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<M; i++) scanf("%lld%lld%lld", B+i, T+i, Q+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9