제출 #1167112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167112		_rain_	비밀 (JOI14_secret)	C++20	0 / 100	343 ms	13304 KiB

secret

#include<bits/stdc++.h>
using namespace std;
#include "secret.h"
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 build_lef(int l,int r,int dep){
	suf[dep][r]=arr[r];
	for(int i=r-1;i>=l;--i){
		suf[dep][i]=Secret(suf[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;
	
	for(int i=l;i<=m;++i){
		for(int j=m+1;j<=r;++j) d[i][j]=dep;
	}
	
	build_lef(l,m,dep);
	dnc(l,m,dep+1);
	
	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: 0 / 100