답안 #590628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590628 2022-07-06T07:47:33 Z fuad27 금 캐기 (IZhO14_divide) C++17
0 / 100
0 ms 212 KB
/*
 * Created: 2022-07-06 11:21
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
// using namespace atcoder

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
const ll inf = 1e18;

#define pii		pair<int,int>
#define pll		pair<ll,ll>
#define vi		vector<int>
#define vll		vector<ll>
#define rep(i, a, b)	for(int i = (a);i<(b);i++)
#define repn(i, a, b)	for(int i = (a);i>=(b);i--)
#define ss		second
#define ff		first
#define mkp		make_pair
#define pb		push_back

#define all(x)		(x).begin(), (x).end()
const int N = 100010;
long long g[N];
long long d[N];
long long x[N];

long long dv(int l, int r) {
	if(l == r) {
		if(d[l] == 1)return g[l];
		return 0;
	}
	ll ans2 = 0;
	int mid = (l+r)/2;
	ans2=max(ans2, max(dv(l, mid), dv(mid+1, r)));
	map<ll, ll> mp;
	int prev = x[mid+1];
	long long sumg=0;
	long long sum = 0;
	mp[0]=1;
	for(int i = mid+1;i<=r;i++) {
		sum+=d[i];
		sum-=x[i]-prev;
		prev=x[i];
		sumg+=g[i];
		mp[sum]=sumg+1;
	}
	long long ans = 0;
	sumg=0;
	sum=0;
	prev=x[mid+1];
	for(int i = mid;i>=l;i--) {
		sum+=prev-x[i];	
		sum-=d[i];
		sumg+=g[i];
		prev=x[i];
		ans=max(ans, sumg+mp[sum]-1);
	}
	return max(ans2, ans);
}
void solve() {
	int n;
	cin >> n;
	for(int i = 0;i<n;i++) {
		cin >> x[i] >> g[i] >> d[i];
	}
	cout << dv(0, n-1) << "\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while(t--) {
		solve();
	}
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -