제출 #593392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593392		haojiandan	3단 점프 (JOI19_jumps)	C++14	46 / 100	395 ms	125052 KiB

jumps

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=(5e5)+10;
int n,a[maxn];
int q;
int st[maxn][20],lg[maxn];
int query(int x,int y) {
	assert(1<=x&&x<=y&&y<=n);
	int j=lg[y-x+1];
	return max(st[x][j],st[y-(1<<j)+1][j]);
}
namespace BF {
ll mx[5010][5010];
void solve() {
	for (int len=1;len<=n;len++)
	for (int i=1,j=len;j<=n;i++,j++) {
		mx[i][j]=max(mx[i+1][j],mx[i][j-1]);
		int l=i+1,r=(i+j)>>1;
		if (l<=r) mx[i][j]=max(mx[i][j],(ll)a[i]+a[j]+query(l,r));
	}
	read(q);
	while (q--) {
		int x,y; read(x),read(y);
		printf("%lld\n",mx[x][y]);
	}
	exit(0);
}
};
namespace Q1 {
ll ans;
pair<int,int> b[maxn];
void chkmax(ll &x,ll y) { if (x<y) x=y; }
void solve() {
	for (int i=1;i<=n;i++) b[i]=MP(a[i],i);
	sort(b+1,b+n+1),reverse(b+1,b+n+1);
	for (int i=1;i<=n&&i<=50;i++) {
		int x=b[i].second;
		int l,r;
		for (int y=x+1;y<=n;y++) {
			l=y*2-x,r=n;
			if (l<=r) chkmax(ans,(ll)a[x]+a[y]+query(l,r));
		}
		for (int y=1;y<x;y++) {
			l=x*2-y,r=n;
			if (l<=r) chkmax(ans,(ll)a[x]+a[y]+query(l,r));
		}
		for (int y=1;y<x;y++) {
			l=max(1,y*2-x),r=y-1;
			if (l<=r) chkmax(ans,(ll)a[x]+a[y]+query(l,r));
		}
	}
	printf("%lld\n",ans);
}
};
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	for (int i=1;i<=n;i++) read(a[i]),st[i][0]=a[i];
	for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for (int i=1;i<=19;i++) for (int j=1;j+(1<<i)-1<=n;j++)
		st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
	if (n<=5000) BF::solve();
	Q1::solve();
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

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