Submission #1167105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167105		_rain_	Secret (JOI14_secret)	C++20	100 / 100	342 ms	13184 KiB

secret

#include<bits/stdc++.h>
#include "secret.h"
using namespace std;

typedef long long LL;

const int N=(int)1000;
#define pref asdas
#define suf asdss
int pref[N+2][N+2],suf[N+2][N+2];
int arr[N+2],d[N+2][N+2],ans[N+2][N+2];
bool used[N+2][N+2]={};
int n;

namespace Lyphmm{
	int Secret(int X, int Y){
		return min((LL)X+(LL)2*(Y/2),(LL)1000000000);
	}
};

void build_rig(int l,int r,int dep){
	pref[dep][l]=arr[l];
	for(int i=l+1;i<=r;++i) {
		pref[dep][i]=Secret(pref[dep][i-1],arr[i]);
	}

	return;
}

void dnc(int l,int r,int dep){
	if (used[l][r]) return;
	if (l>r) return;
	if (r-l<=1){
		int m=(l+r)/2;
		used[l][r]=true;
		ans[l][r]=(l==r?arr[l]:Secret(arr[l],arr[r]));
		dnc(l,m,dep+1),dnc(m+1,r,dep+1);
		return;
	}
	int m=(l+r)/2;
	dnc(l,m,dep+1);
	
	for(int i=l;i<=m;++i){
		for(int j=m+1;j<=r;++j) d[i][j]=dep;
	}
	
	for(int i=m;i>=l;--i){
		if (used[i][m]) continue;
		
		for(int j=m-1;j>=i;--j){
			if (used[i][j] && used[j+1][m]){
				ans[i][m]=Secret(ans[i][j],ans[j+1][m]);
				used[i][m]=true;
				break;
			}
		}
		assert(used[i][m]);
	}
	for(int i=m;i>=l;--i) suf[dep][i]=ans[i][m];
	
	build_rig(m+1,r,dep);
	dnc(m+1,r,dep+1);
	return;
}

void Init(int num,int a[]){
	n=num;
	for(int i=1;i<=n;++i) arr[i]=a[i-1];
	dnc(1,n,1);
	return;
}
int Query(int l, int r){
	++l,++r;
	if (used[l][r]) return ans[l][r];
	int m=(l+r)/2;
	int ans=Secret(suf[d[l][r]][l],pref[d[l][r]][r]);
	return ans;
}

• Subtask 1: 100 / 100