Submission #1272034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272034		ezzzay	Secret (JOI14_secret)	C++20	0 / 100	351 ms	12356 KiB

secret

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

vector<int> a;
int n;
static int dp[5005][5005]; // use a bit larger static array

void build(int L, int R){
    if(L == R){
        dp[L][R] = a[L];
        return;
    }
    int mid = (L + R) / 2;

    // ensure dp[mid][mid] is set
    dp[mid][mid] = a[mid];

    // compute dp[i][mid] for i = mid-1 .. L  (range i..mid)
    for(int i = mid - 1; i >= L; --i){
        // dp[i+1][mid] must already exist (we work leftwards)
        dp[i][mid] = Secret(a[i], dp[i+1][mid]); // a[i] ★ (a[i+1]★...★a[mid])
    }

    // compute dp[mid][i] for i = mid+1 .. R  (range mid..i)
    for(int i = mid + 1; i <= R; ++i){
        dp[mid][i] = Secret(dp[mid][i-1], a[i]); // (a[mid]★...★a[i-1]) ★ a[i]
    }

    // recurse
    build(L, mid);
    build(mid+1, R);
}

void Init(int N, int A[]){
    n = N;
    // initialize dp to a sentinel (here -1)
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            dp[i][j] = -1;

    a.clear();
    a.pb(0); // dummy so that a[1..n] exists
    for(int i = 0; i < N; ++i) a.pb(A[i]);

    build(1, n);
}

int Query(int L, int R){
    // user supplies 0-based L,R; your code increments them to 1-based
    ++L; ++R;
    if(L > R) return -1;
    if(dp[L][R] != -1) return dp[L][R];

    // try to find a split i in [L..R-1] such that dp[L][i] and dp[i+1][R] are known
    for(int i = L; i <= R - 1; ++i){
        if(dp[L][i] != -1 && dp[i+1][R] != -1){
            return Secret(dp[L][i], dp[i+1][R]);
        }
    }
    // should not happen if build fully covers needed ranges
    return -1;
}

• Subtask 1: 0 / 100