oj.uz

Submission #138063

# Submission time Handle Problem Language Result Execution time Memory
138063 2019-07-29T09:08:12 Z ekrem Triple Jump (JOI19_jumps) C++
0 / 100
 1898 ms 3988 KB 
#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)>>1)
#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[sol]);
}

int qu(int k, int bas, int son, int x, int y){
	if(bas > son 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1898 ms 3988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -