oj.uz

Submission #433949

# Submission time Handle Problem Language Result Execution time Memory
433949 2021-06-20T12:34:49 Z Azimjon Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 119080 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
// Muallif: Azimjon Mehmonali o'g'li

#include <bits/stdc++.h>

using namespace std;

// #define int long long

const long double PI = 3.1415926535897;
const int mod = 1000000007LL;
const int INF = 1e18;

const int N = 5005;

int a[N], b[N], t[4 * N];
long long dp[N][N];
int n;

void build(int v = 1, int tl = 1, int tr = n) {
	if (tl == tr) {
		t[v] = a[tl];
		return;
	}

	int tm = (tl + tr) / 2;

	build(v + v, tl, tm);
	build(v + v + 1, tm + 1, tr);

	t[v] = max(t[v + v], t[v + v + 1]);
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (r < tl || tr < l) return 0;

	if (l <= tl && tr <= r) {
		return t[v];
	}

	int tm = (tl + tr) / 2;

	return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}

	build();

	int q;
	cin >> q;

	function<int(int, int, int)> f = [&](int l, int r, int first) {
		// cerr << l << " " << r << endl;
		// if (r - l + 1 <= 2) return 0ll;
		vector<pair<int, int>> v;
		for (int i = l; i <= r; i++) {
			v.emplace_back(a[i], i);
		}

		sort(v.rbegin(), v.rend());

		int tl = v[0].second, tr = v[1].second;

		if (tl > tr) {
			swap(tl, tr);
		}

		int re = 0;

		for (int i = 1; i <= n; i++) {
			vector<int> d{tl, tr, i};
			sort(d.begin(), d.end());
			if (i == tl || i == tr || l > i || i > r
				|| d[2] - d[1] < d[1] - d[0])
				continue;

			re = max(re, a[i]);
		}

		int ans = v[0].first + v[1].first + re;

		if (!first) return ans;

		a[v[0].second] = 0;
		ans = max(ans, f(l, r, first - 1));

		a[v[1].second] = 0;
		ans = max(ans, f(l, r, first - 1));

		a[v[0].second] = b[v[0].second];
		a[v[1].second] = b[v[1].second];
		return ans;
	};

	function<long long(int, int)> ff = [&](int l, int r) {
		if (r - l + 1 <= 2) return 0ll;

		if (dp[l][r] != 0) return dp[l][r];

		long long ans = 1ll * a[l] + a[r] + get(l + 1, (l + r) / 2);

		ans = max(ans, ff(l, r - 1));
		ans = max(ans, ff(l + 1, r));

		return (dp[l][r] = ans);
	};

	ff(1, n);

	while (q--) {
		int l, r;
		cin >> l >> r;

		cout << ff(l, r) << endl;
	}

	return 0;
}

Compilation message

jumps.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("O3")
      | 
jumps.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization("unroll-loops")
      | 
jumps.cpp:15:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int INF = 1e18;
      |                 ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Execution timed out 4097 ms 119080 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Execution timed out 4097 ms 119080 KB Time limit exceeded
12 Halted 0 ms 0 KB -