oj.uz

Submission #433960

# Submission time Handle Problem Language Result Execution time Memory
433960 2021-06-20T12:44:09 Z Azimjon Triple Jump (JOI19_jumps) C++17
19 / 100
 2206 ms 189856 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], ka[N][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;
	};

	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			ka[i][j] = max(ka[i][j - 1], a[j]);
		}
	}

	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] + ka[l + 1][(l + r) / 2];

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

		dp[l][r] = ans;

		return dp[l][r];
	};

	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 0 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 2 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 2 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 2085 ms 189808 KB Output is correct
12 Correct 2112 ms 189628 KB Output is correct
13 Correct 2066 ms 189768 KB Output is correct
14 Correct 2116 ms 189856 KB Output is correct
15 Correct 2128 ms 189828 KB Output is correct
16 Correct 2111 ms 189088 KB Output is correct
17 Correct 2121 ms 189220 KB Output is correct
18 Correct 2206 ms 189040 KB Output is correct
19 Correct 2181 ms 189672 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 460 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 0 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 2 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 2085 ms 189808 KB Output is correct
12 Correct 2112 ms 189628 KB Output is correct
13 Correct 2066 ms 189768 KB Output is correct
14 Correct 2116 ms 189856 KB Output is correct
15 Correct 2128 ms 189828 KB Output is correct
16 Correct 2111 ms 189088 KB Output is correct
17 Correct 2121 ms 189220 KB Output is correct
18 Correct 2206 ms 189040 KB Output is correct
19 Correct 2181 ms 189672 KB Output is correct
20 Runtime error 15 ms 460 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -