Submission #682674

#	Time	Username	Problem	Language	Result	Execution time	Memory
682674		CyberCow	Divide and conquer (IZhO14_divide)	C++17	100 / 100	75 ms	8088 KiB

divide

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <stack>
#include <deque>
#define fi first
#define se second
using namespace std;
using ll = long long;
vector<pair<ll, pair<ll, ll>>> v;
ll ans = 0;

void conc(int l, int r)
{
	if (l == r)
	{
		ans = max(ans, v[l].se.fi);
		return;
	}
	int m = (l + r) / 2;
	ll gum = 1, hashv = 0, zoloto = 0, demipox = 0;
	vector<pair<ll ,ll>> a;
	vector<ll> mi;
	for (int i = m + 1; i <= r; i++)
	{
		zoloto += v[i].se.fi;
		hashv += v[i].se.se - (v[i].fi - v[i - 1].fi);
		a.push_back({hashv, zoloto});
		mi.push_back(0);
	}
	sort(a.begin(), a.end());
	mi.back() = a.back().second;
	for (int i = mi.size() - 2; i >= 0; i--)
	{
		mi[i] = max(mi[i + 1], a[i].second);
	}
	for (int i = m; i >= l; i--)
	{
		gum += v[i].se.se;
		demipox += v[i].se.fi;
		int ind = lower_bound(a.begin(), a.end(), make_pair(-(gum - (v[m].fi - v[i].fi + 1)), 0LL)) - a.begin();
		if (ind < a.size())
		{
			ans = max(ans, mi[ind] + demipox);
		}
	}
	conc(l, m);
	conc(m + 1, r);
}

void solve()
{
	int n, i, j, x, y, a, b, c;
	cin >> n;
	for ( i = 0; i < n; i++)
	{
		cin >> a >> b >> c;
		v.push_back({ a, {b, c} });
	}
	conc(0,n - 1);
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--)
	{
		solve();
	}
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'void conc(int, int)':
divide.cpp:52:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if (ind < a.size())
      |       ~~~~^~~~~~~~~~
divide.cpp: In function 'void solve()':
divide.cpp:63:12: warning: unused variable 'j' [-Wunused-variable]
   63 |  int n, i, j, x, y, a, b, c;
      |            ^
divide.cpp:63:15: warning: unused variable 'x' [-Wunused-variable]
   63 |  int n, i, j, x, y, a, b, c;
      |               ^
divide.cpp:63:18: warning: unused variable 'y' [-Wunused-variable]
   63 |  int n, i, j, x, y, a, b, c;
      |                  ^

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52