oj.uz

Submission #89477

# Submission time Handle Problem Language Result Execution time Memory
89477 2018-12-15T03:35:46 Z inom Divide and conquer (IZhO14_divide) C++14
48 / 100
 1000 ms 3600 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define fi first
#define se second
#define new new228
#define pb push_back
#define rank rank228
#define int long long
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define in freopen("divide.in", "r", stdin);
#define out freopen("divide.out", "w", stdout);

using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma warning(disable : 4996)

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // st.oreder_of_key();

const int N = 300300;
const int INF = 1e15;
const int MOD = 1e9 + 7;

int TN = 1;

int n, ans;
int x[N], g[N], d[N];

bool can(int r, int l) {
	return x[r] - x[l] <= d[r] - d[l - 1];
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
		ans = max(ans, g[i]);
		g[i] += g[i - 1]; d[i] += d[i - 1];		
	}
	for (int i = 1; i <= n; i++) {
		int l = i, r = n;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (can(mid, i)) {
				l = mid + 1;
			} else {
				r = r - 1;
			}
		}
		ans = max(ans, g[r] - g[i - 1]);
		/*if (can(r, i)) {
			ans = max(ans, g[r] - g[i - 1]);
		}
		if (can(l, i)) {
			ans = max(ans, g[l] - g[i - 1]);
		}*/
	}
	printf("%lld\n", ans);
	return;
}

signed main() {
    // ios_base::sync_with_stdio(0);
    // in; out; // cin >> TN;
    while (TN--) { solve(); }
    return 0;
 }

Compilation message

divide.cpp:25:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
divide.cpp: In function 'void solve()':
divide.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
divide.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 696 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 696 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 3 ms 696 KB Output is correct
5 Correct 4 ms 696 KB Output is correct
6 Correct 3 ms 696 KB Output is correct
7 Correct 2 ms 708 KB Output is correct
8 Correct 3 ms 728 KB Output is correct
9 Correct 7 ms 784 KB Output is correct
10 Correct 11 ms 808 KB Output is correct
11 Correct 57 ms 1104 KB Output is correct
12 Correct 55 ms 1256 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1268 KB Output is correct
2 Correct 5 ms 1268 KB Output is correct
3 Correct 6 ms 1272 KB Output is correct
4 Correct 23 ms 2292 KB Output is correct
5 Correct 28 ms 2308 KB Output is correct
6 Correct 55 ms 3472 KB Output is correct
7 Correct 41 ms 3600 KB Output is correct
8 Correct 41 ms 3600 KB Output is correct
9 Correct 40 ms 3600 KB Output is correct
10 Execution timed out 1068 ms 3600 KB Time limit exceeded
11 Halted 0 ms 0 KB -