답안 #381235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381235 2021-03-24T20:59:32 Z SavicS 금 캐기 (IZhO14_divide) C++14
100 / 100
59 ms 9196 KB
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

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

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n;
array<ll,3> niz[maxn];

ll G[maxn];
ll E[maxn];

ll bor[4*maxn];
void update(int v, int tl, int tr, int poz, ll vre) {
	if(tl == tr) {
		bor[v] = vre;
		return;
	}
	int mid = (tl + tr) / 2;
	if(poz <= mid)update(v * 2, tl, mid, poz, vre);
	else update(v * 2 + 1, mid + 1, tr, poz, vre);
	bor[v] = max(bor[v * 2], bor[v * 2 + 1]);
}

int k_th(int v, int tl, int tr, int x) {
	if(tl == tr)return tl;
	int mid = (tl + tr) / 2;
	if(bor[v * 2 + 1] >= x)return k_th(v * 2 + 1, mid + 1, tr, x);
	return k_th(v * 2, tl, mid, x);
}

int main() {
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	cin >> n;
	ff(i,1,n)ff(j,0,2)cin >> niz[i][j];

	ff(i,1,n) {
		G[i] = G[i - 1] + niz[i][1];
		E[i] = E[i - 1] + niz[i][2];
		update(1,1,n,i,E[i] - niz[i][0]);
	}

	ll rez = 0;
	ff(i,1,n) {
		ll poz = k_th(1,1,n,E[i - 1] - niz[i][0]);
		rez = max(rez, G[poz] - G[i - 1]);
	}

	cout << rez << endl;
	return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 2 ms 492 KB Output is correct
23 Correct 4 ms 748 KB Output is correct
24 Correct 4 ms 748 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 2 ms 492 KB Output is correct
23 Correct 4 ms 748 KB Output is correct
24 Correct 4 ms 748 KB Output is correct
25 Correct 3 ms 748 KB Output is correct
26 Correct 6 ms 1132 KB Output is correct
27 Correct 7 ms 1132 KB Output is correct
28 Correct 26 ms 4332 KB Output is correct
29 Correct 28 ms 4716 KB Output is correct
30 Correct 59 ms 9196 KB Output is correct
31 Correct 51 ms 8044 KB Output is correct
32 Correct 50 ms 8172 KB Output is correct
33 Correct 49 ms 8044 KB Output is correct
34 Correct 53 ms 7916 KB Output is correct
35 Correct 53 ms 8428 KB Output is correct
36 Correct 54 ms 8684 KB Output is correct