Submission #1186441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186441		ayat	Divide and conquer (IZhO14_divide)	C++20	0 / 100	0 ms	324 KiB

divide

//============================================================================
// Name        : div.cpp
// Author      : hk
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(n) n.begin(), n.end()
#define fi first
#define se second
const int maxn = 1e7 * 1.5;
const int mod = 1e9 + 7;


signed main() {

	int n;
	cin>>n;

	map <int,pair<int,int>> min;
	int mx = 0;
	for(int i = 0;i < n;i++){
		int a,b,c;
		cin>>a>>b>>c;

		min[a] = {b,c};
		mx = max(mx, a);
	}

	int ans = 0;

	vector <bool> vis(mx + 1, false);


	for(int i = 0;i <= mx;i++){
		if(min.find(i) == min.end() || vis[i])continue ;

		int ener = min[i].se;
		int ind = i;
		int cur = 0;
		while(ener >= 0 && ind <= mx){
				cur += min[ind].fi;
				vis[cur] = 1;
				ener--;
				ind++;

				if(min.find(ind) != min.end())
					ener += min[ind].se;
		}
		ans = max(ans,cur);
	}

	fill(all(vis), 0);

	for(int i = mx;i >= 0;i--){
		if(min.find(i) == min.end() || vis[i])continue ;

		int ener = min[i].se;
		int ind = i;
		int cur = 0;
		while(ener >= 0 && ind >= 0){
				cur += min[ind].fi;
				vis[cur] = 1;
				ener--;
				ind--;

				if(min.find(ind) != min.end())
					ener += min[ind].se;
			}
		ans = max(ans,cur);
	}

	cout<<ans<<'\n';
	return 0;
}

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