Submission #1293690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293690		rayan_bd	비밀 (JOI14_secret)	C++20	0 / 100	20080 ms	35500 KiB

secret

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

using namespace std;

const int mxN = 1005;

int a[mxN], dp[mxN][mxN], n;
unordered_map<int, unordered_map<int, int>> mp;
map<pair<int, int>, int> cnt;

int token = 0;

int get(int x, int y){
    if(x == -1) return y;
    if(y == -1) return x;
    if(mp.count(x)){
        if(mp[x].count(y)){
            return mp[x][y];
        }
    }
    token += 1;
    return mp[x][y] = Secret(x, y);
}

void hehe(int l, int r){
    if(l > r) return;
    cnt[{l, r}] += 1;
    if(l == r) return;
    int mid = (l + r) / 2;
    hehe(l, mid), hehe(mid + 1, r);
}

int solve(int l, int r){
    if(l > r) return -1;
    if(dp[l][r] != -1) return dp[l][r];
    if(l + 1 == r) return dp[l][r] = get(a[l], a[r]);
    int mid = (l + r) / 2;
    int left = solve(l, mid), right = solve(mid + 1, r);
    return dp[l][r] = get(left, right);
}

int get_token(int l, int r){
    if(l > r) return 0;
    if(dp[l][r] != -1) return 0;
    if(l + 1 == r) return 1;
    int mid = (l + r) / 2;
    int left = get_token(l, mid), right = get_token(mid + 1, r);
    return left + right;
}

void operation(int l, int r){
    if(r >= n) return;
    if((get_token(l, r) + token + 1) <= 8000) solve(l, r);  
}


void Init(int N, int A[]) {
    memset(dp, -1, sizeof(dp));
    n = N;
    for(int i = 0; i < N; ++i){
        a[i] = A[i];
        dp[i][i] = A[i];
    }
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            hehe(i, j);
        }
    }
    vector<vector<int>> vc;
    for(auto it : cnt){
        vc.push_back({it.second, it.first.first, it.first.second});
    }
    sort(vc.begin(), vc.end());
    for(int i = vc.size() - 1; i >= 0; --i){
        operation(vc[i][1], vc[i][2]);
    }
}


int Query(int L, int R) {
    return solve(L, R);
}

• Subtask 1: 0 / 100