Submission #392469

#	Time	Username	Problem	Language	Result	Execution time	Memory
392469		patrikpavic2	Divide and conquer (IZhO14_divide)	C++17	100 / 100	86 ms	9964 KiB

divide

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, pair < ll, ll > > pip;

const int N = 2e5 + 500;
const ll INF = (ll)1e18;

int n;
vector < pip > v;
vector < ll > sz;

int pos(int x){
	return lower_bound(sz.begin(), sz.end(), x) - sz.begin();
}

ll loga[N];

void add(int x, ll val){
	for(x += 10; x < N; x += x & -x)
		loga[x] = min(loga[x], val);
}

ll query(int x){
	ll ans = INF;
	for(x += 10; x ; x -= x & -x)
		ans = min(loga[x], ans);
	return ans;
}

int main(){
	for(int i = 0;i < N;i++) loga[i] = INF;
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		int x, g, e; scanf("%d%d%d", &x, &g, &e);
		v.PB({x, {g, e}}); x++;
	}
	v.PB({0, {0, 0}});
	sort(v.begin(), v.end());
	for(int i = 1;i <= n;i++){
		v[i].Y.X += v[i - 1].Y.X;
		v[i].Y.Y += v[i - 1].Y.Y;
		sz.PB(v[i].Y.Y - v[i].X);
		sz.PB(v[i - 1].Y.Y - v[i].X);
	}	
	sort(sz.begin(), sz.end());
	sz.erase(unique(sz.begin(), sz.end()), sz.end());
	ll sol = 0;
	for(int i = 1;i <= n;i++){
		add(pos(v[i - 1].Y.Y - v[i].X), v[i - 1].Y.X);
		sol = max(sol, v[i].Y.X - query(pos(v[i].Y.Y - v[i].X)));
	}
	printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
divide.cpp:44:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   int x, g, e; scanf("%d%d%d", &x, &g, &e);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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