Submission #138072

#	Time	Username	Problem	Language	Result	Execution time	Memory
138072		ekrem	Triple Jump (JOI19_jumps)	C++98	0 / 100	1828 ms	4088 KiB

jumps

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i]
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define mod 1000000007
#define inf 1000000009
#define N 1000005

using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;

int n, m, ans, seg[4*N];
ii a[N];

void bu(int k, int bas, int son){
	if(bas == son){
		seg[k] = a[bas].st;
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
	seg[k] = max(seg[sol], seg[sag]);
}

int qu(int k, int bas, int son, int x, int y){
	if(x > y or bas > y or son < x)
		return 0;
	if(bas >= x and son <= y)
		return seg[k];
	return max(qu(sol, bas, orta, x, y), qu(sag, orta + 1, son, x, y));
}

int main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i].st);
		a[i].nd = i;
	}
	bu(1, 1, n);
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	m = min(n, 2000);
	for(int i = 1; i <= m; i++)
		for(int j = i + 1; j <= m; j++){
			int bas = a[i].nd;
			int son = a[j].nd;
			if(bas > son)
				swap(bas, son);
			int mx = qu(1, 1, n, bas + 1, orta);
			// cout << bas << " " << son << " " << bas + 1 << " " << orta << " = " << mx << endl;
			if(bas > 1)
				mx = max(mx, qu(1, 1, n, max(bas - (son - bas), 1), bas - 1));

			mx = max(mx, qu(1, 1, n, son + (son - bas), n));
			// if(mx + a[i].st + a[j].st == 13){
			// 	cout << bas << " " << son << " " << mx << endl;
			// }
			ans = max(ans, mx + a[i].st + a[j].st);
		}
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
jumps.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i].st);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54