제출 #522608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522608		blue	Two Dishes (JOI19_dishes)	C++17	0 / 100	74 ms	62220 KiB

dishes

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;

#define sz(x) int(x.size())
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

const int mx = 1'000'000;
const ll INF = 1'000'000'000'000'000'000LL;

int N, M;
vi A(1+mx), S(1+mx), P(1+mx);
vi B(1+mx), Q(1+mx), T(1+mx);

vll Asum(1+mx, 0);
vll Bsum(1+mx, 0);




struct delta
{
	int p;
	ll v;
};

bool operator < (delta A, delta B)
{
	if(A.p == B.p) return A.v < B.v;
	return A.p < B.p;
}




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	for(int i = 1; i <= N; i++)
	{
		cin >> A[i] >> S[i] >> P[i];
		Asum[i] = Asum[i-1] + A[i];
	}

	for(int j = 1; j <= M; j++)
	{
		cin >> B[j] >> Q[j] >> T[j];
		Bsum[j] = Bsum[j-1] + B[j];
	}

















	multiset<delta> hi_points[1+M], lo_points[1+M];

	ll basicCost = 0;




	for(int i = 1; i <= N; i++)
	{
		int lo = 0, hi = M;
		while(lo != hi)
		{
			int mid = (lo+hi)/2 + 1;

			if(Bsum[mid] + Asum[i] <= S[i])
				lo = mid;
			else
				hi = mid-1;
		}

		if(lo == 0) continue;

		if(lo == M)
		{
			basicCost += P[i];

			// cerr << i << " : " << "basicCost += " << P[i] << '\n';
		}
		else
		{
			delta cr{i, +P[i]};
			// cerr << lo+1 << " : " << i << ' ' << P[i] << '\n';
			// cerr << lo+1 << ' ' << i << ' ' << +P[i] << '\n';

			if(cr.v >= 0) hi_points[lo+1].insert(cr);
			else 
			{
				cr.v *= -1;
				lo_points[lo+1].insert(cr);
			}
		}
	}

	// cerr << "-----\n";









	for(int j = 1; j <= M; j++)
	{
		int lo = 0, hi = N;
		while(lo != hi)
		{
			int mid = (lo+hi)/2+1;

			if(Asum[mid] + Bsum[j] <= Q[j])
				lo = mid;
			else
				hi = mid-1;
		}

		if(lo == 0) continue;

		if(lo == N)
		{
			basicCost += T[j];
			// cerr << j << " : " << "basicCost += " << T[j] << '\n';
		}
		else
		{
			basicCost += T[j];
			delta cr{lo+1, -T[j]};

			// cerr << j << ' ' << lo+1 << ' ' << -T[j] << '\n';

			if(cr.v >= 0) hi_points[j].insert(cr);
			else 
			{
				cr.v *= -1;
				lo_points[j].insert(cr);
			}
		}
	}




	vi init_size(1+M, 0);
	for(int j = 1; j <= M; j++) init_size[j] = sz(hi_points[j]) + sz(lo_points[j]);







	multiset<delta>* hp[1+M];
	multiset<delta>* lp[1+M];
	for(int j = 1; j <= M; j++)
	{
		hp[j] = &hi_points[j];
		lp[j] = &lo_points[j];
	}

	for(int j = 1; j <= M; j++)
	{
		while(!lp[j]->empty())
		{
			auto lit = lp[j]->begin();

			delta lpv = *lit;


			auto hit = hp[j]->lower_bound({lpv.p, -INF});

			if(hit == hp[j]->end())
			{
				lp[j]->clear();
				break;
			}

			delta hpv = *hit;


			ll cng = min(lpv.v, hpv.v);


			lp[j]->erase(lit);
			if(lpv.v != cng)
				lp[j]->insert({lpv.p, lpv.v - cng});

			hp[j]->erase(hit);
			if(hpv.v != cng)
				hp[j]->insert({hpv.p, hpv.v - cng});
		}

		if(j < M)
		{
			if(init_size[j] > init_size[j+1])
			{
				swap(lp[j], lp[j+1]);
				swap(hp[j], hp[j+1]);
			}

			for(delta x : *lp[j])
				lp[j+1]->insert(x);

			for(delta y : *hp[j])
				hp[j+1]->insert(y);

			lp[j]->clear();
			hp[j]->clear();
		}
	}

	// cerr << "basicCost = "<< basicCost << '\n';





	ll ans = basicCost;

	for(delta z : *hp[M])
		ans += z.v;

	cout << ans << '\n';


}

• 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