oj.uz

Submission #88318

# Submission time Handle Problem Language Result Execution time Memory
88318 2018-12-05T09:39:08 Z dimash241 Divide and conquer (IZhO14_divide) C++17
100 / 100
 183 ms 14456 KB 
# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (int i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (int i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
ll x[N], g[N], d[N];
vector < ll > v;

int get_id (ll that) {
	int id = lower_bound(every(v), that) - v.begin();

	return id;
}

ll f[N], ans;

void upd (int pos, ll x) {
	for (int i = pos; i <= sz(v); i = (i | (i + 1)))
		f[i] = min(f[i], x);
}

ll get (ll r) {
	ll res = INF;
	while (r >= 0) {
		res = min(res, f[r]);
		r = (r & (r + 1)) - 1;
	}

	return res;
}


int main () {
	cin >> n;
	ll sd = 0, sg = 0;        	
    
	For (i, 1, n) {
		cin >> x[i] >> g[i] >> d[i];
		v.pb(sd - x[i]);
		
		sd += d[i];
		v.pb(sd - x[i]);
		
	}
	fill(f, f + N, INF);
	
	sort(every(v));
	v.resize(unique(every(v)) - v.begin());
	
    sd = sg = 0;
    For (i, 1, n) {

        upd(get_id(sd - x[i]), sg);
        sg += g[i];
        sd += d[i];
        ans = max(ans, sg - get(get_id(sd - x[i])));
        
    }           

    cout << ans;

    return Accepted;
}

// Coded By OB

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5184 KB Output is correct
3 Correct 7 ms 5184 KB Output is correct
4 Correct 7 ms 5188 KB Output is correct
5 Correct 6 ms 5188 KB Output is correct
6 Correct 7 ms 5188 KB Output is correct
7 Correct 7 ms 5236 KB Output is correct
8 Correct 7 ms 5236 KB Output is correct
9 Correct 7 ms 5236 KB Output is correct
10 Correct 6 ms 5236 KB Output is correct
11 Correct 7 ms 5288 KB Output is correct
12 Correct 6 ms 5328 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5328 KB Output is correct
2 Correct 6 ms 5332 KB Output is correct
3 Correct 6 ms 5356 KB Output is correct
4 Correct 7 ms 5376 KB Output is correct
5 Correct 7 ms 5376 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 7 ms 5376 KB Output is correct
8 Correct 8 ms 5416 KB Output is correct
9 Correct 8 ms 5588 KB Output is correct
10 Correct 10 ms 5588 KB Output is correct
11 Correct 13 ms 5956 KB Output is correct
12 Correct 13 ms 6068 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6068 KB Output is correct
2 Correct 18 ms 6188 KB Output is correct
3 Correct 19 ms 6188 KB Output is correct
4 Correct 76 ms 7840 KB Output is correct
5 Correct 92 ms 7840 KB Output is correct
6 Correct 183 ms 9760 KB Output is correct
7 Correct 135 ms 9760 KB Output is correct
8 Correct 141 ms 9760 KB Output is correct
9 Correct 136 ms 9784 KB Output is correct
10 Correct 137 ms 9784 KB Output is correct
11 Correct 151 ms 12000 KB Output is correct
12 Correct 160 ms 14456 KB Output is correct