제출 #1237147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237147		antromancap	비밀 (JOI14_secret)	C++20	100 / 100	344 ms	9324 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1001;
int n, dp[N][N], a[N];
bool ok[N][N];
// #define MAX_N 1000
// #define MAX_Q 10000
// #define MAX_VALUE 1000000000

// static int secret_count;
// int Secret(int X, int Y) {
// 	++secret_count;
// 	if (!(0 <= X && X <= MAX_VALUE)) {
// 		fprintf(stderr, "Wrong Answer [1]\n");
// 		exit(0);
// 	}
// 	if (!(0 <= Y && Y <= MAX_VALUE)) {
// 		fprintf(stderr, "Wrong Answer [1]\n");
// 		exit(0);
// 	}
// 	return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
// }

void divi(int l, int r) {
	if (l >= r) return;
	int m = (l + r) >> 1;
	divi(l, m);
	divi(m + 1, r);
	for (int i = m - 1; i >= l; i--)
		if (!ok[i][m]) dp[i][m] = Secret(a[i], dp[i + 1][m]), ok[i][m] = 1;
	for (int i = m + 2; i <= r; i++)
		if (!ok[m + 1][i]) dp[m + 1][i] = Secret(dp[m + 1][i - 1], a[i]), ok[m + 1][i] = 1;
}

void Init(int N, int A[]) {
	for (int i = 0; i < N; i++) a[i] = dp[i][i] = A[i], ok[i][i] = 1;
	divi(0, N - 1);
}

int Query(int l, int r) {
	if (ok[l][r]) return dp[l][r];
	for (int i = l; i < r; i++)
		if (ok[l][i] && ok[i + 1][r]) return Secret(dp[l][i], dp[i + 1][r]);
	assert(0);
}

// int main() {
// 	int A[] = { 1, 4, 7, 2, 5, 8, 3, 6 };
// 	Init(8, A);
// 	cout << Query(0, 3) << '\n';
// 	cout << Query(1, 7) << '\n';
// 	cout << Query(5, 5) << '\n';
// 	cout << Query(2, 4) << '\n';
// }

• Subtask 1: 100 / 100