Submission #1218088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218088		KindaGoodGames	Peru (RMI20_peru)	C++20	0 / 100	205 ms	327680 KiB

peru

#include "peru.h"
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

int INF = numeric_limits<int>::max()/2;
int mod = 1e9+7;
int MAXK = 28;

struct SegmentTree{
    int len = 1;
    vector<int> S;

    SegmentTree(vector<int> arr){
        int n = arr.size();
        while(len < n){
            len <<= 1;
        }

        S.resize(2*len);
        for(int i = 0; i < n; i++){
            S[i+len] = arr[i];
        }
        for(int i = len-1; i > 0; i--){
            S[i] = max(S[i*2], S[i*2+1]);
        }
    }

    int query(int ql, int qr, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;

        if(ql <= l && r <= qr) return S[i];
        if(r <= ql || qr <= l) return 0;
        
        int mid = (l+r)/2;
        return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
    }
};

int exp(int a, int k){
    if(k == 0) return 1;
    int res = exp(a,k/2);

    if(k % 2 == 0) return (res * res) % mod;
    return ((res*res% mod) * a )% mod;
}
 
int32_t solve(int32_t n, int32_t K, int32_t* S){
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        v[i] = S[i];
    }
    vector<int> dp(n+1, INF);
    vector<vector<int>> dpJ(MAXK, vector<int>(n+1, INF));
    vector<vector<tiii>> dpJP(MAXK, vector<tiii>(n+1, {INF,INF,INF}));

    SegmentTree seg(v);

    dpJ[0][0] = 0;
    dpJP[0][0] = {0,0,0};
    for(int i = 1; i <= n; i++){
        dpJ[0][i] = dpJ[0][i-1]+v[i-1];
        dpJP[0][i] = make_tuple(dpJ[0][i-1], v[i-1], i-1LL);
    } 
    for(int k = 1; k < MAXK; k++){
        dpJ[k][0] = 0;
        dpJP[k][0] = {0,0,0};
        int p2 = 1 << k;
        for(int i = 1; i <= n; i++){
            int v1, m1, l1;
            tie(v1,m1,l1) = dpJP[k-1][i];
            int v2, m2, l2; 
            int prev =max(0LL,i-p2);
            tie(v2,m2,l2) = dpJP[k][prev];

            // either staying at the same point
            int r1 = m1+dpJ[k][l1]; 
            // or moving as far as possible
            int r2 = dpJ[k][prev]+seg.query(max(0LL,i-p2), i);

            if(r1 < r2){
                dpJ[k][i] = r1;
                dpJP[k][i] = {dpJ[k][l1],m1,l1};
            }else{
                dpJ[k][i] = r2;
                dpJP[k][i] = {v2,seg.query(max(0LL,i-p2), i),prev};
            }
        }
    }

    dp[0] = 0;

    int res = 0;

    for(int i = 1; i <= n; i++){
        tiii r = {INF,INF,INF};
        int v = INF; 
        int csum = 0;
        for(int k = 0; k < MAXK; k++){
            int p2 = 1 << k;
            if((K & p2) == 0) continue;
            csum += p2;
            if(get<0>(r) == INF) {
                r = dpJP[k][i];
                v = dpJ[k][i];
                continue;
            }

            int v1, m1, l1;
            tie(v1,m1,l1) = r;
            int v2, m2, l2; 
            int prev =max(0LL,i-csum);
            tie(v2,m2,l2) = dpJP[k][prev];

            // either staying at the same point
            int r1 = m1+dp[l1]; 
            // or moving as far as possible
            int r2 = dp[prev]+seg.query(max(0LL,prev), i);

            if(r1 < r2){
                v = r1;
                r = {dpJ[k][l1],m1,l1};
            }else{
                v = r2;
                r = { dp[prev],seg.query(max(0LL,prev), i),prev};
            }
        }
        dp[i] = v;

        res += ((dp[i]%mod) * exp(23, n-i))%mod; 
        res %= mod;
    }
    return res;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51