oj.uz

답안 #635749

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635749 2022-08-26T18:31:21 Z martin_nedev Peru (RMI20_peru) C++14
0 / 100
 6 ms 10964 KB 
#include "peru.h"

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCALTEST
    #include "grader.cpp"
#endif // __LOCALTEST

//first subtask
const int MAXLOG = 15;
const int MAXN = 2050;
const int64_t inf = 1e17;
const int64_t mod = 1e9+7;

struct RangeMaximumQuery
{
    int n;
    int log[MAXN+10];
    int sparseTable[MAXLOG+2][MAXN+10];

    RangeMaximumQuery(int n)
    {
        //precompute log array
        //!log[i] gives the value of log2(i) rounded down

        this->n = n;

        log[1] = 0;
        for (int i = 2; i <= n; i++)
            log[i] = log[i>>1] + 1;


    }

    void Build(int *arr)
    {
        //construct sparse table

        for (int i = 0; i < n; i++)
            sparseTable[0][i] = arr[i];

        for (int lg = 1; lg <= MAXLOG; lg++)
        {
            for (int i = 0; i < n; i++)
            {
                int jump = (1<<(lg-1));

                if (i+jump >= n)
                    sparseTable[lg][i] = sparseTable[lg-1][i];

                else
                    sparseTable[lg][i] = max(sparseTable[lg-1][i], sparseTable[lg-1][i+jump]);
            }
        }
    }

    int Query(int leftQ, int rightQ)
    {
        //answering query
        return max(sparseTable[log[rightQ-leftQ+1]][leftQ],
                   sparseTable[log[rightQ-leftQ+1]][rightQ-(1<<log[rightQ-leftQ+1])+1]);
    }

};

int evaluateAnswer(const int n, int64_t *arr)
{
    int64_t ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans = (ans*23 + arr[i])%mod;
    }

    return ans;
}

int64_t dp1[MAXN+10][MAXN+10];
int64_t dp2[MAXN+10];
int solve(int n, int k, int* v)
{
    RangeMaximumQuery *rmq = new RangeMaximumQuery(n);
    rmq->Build(v);

    for (int i = 0; i < n; i++)
        dp2[i] = inf;

    dp1[0][0] = v[0];
    dp2[0] = v[0];


    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < min(i+1, k); j++)
        {

            if (i == j)
                dp1[i][j] = (rmq->Query(0, i))%mod;

            else
            {
                dp1[i][j] = (int64_t(rmq->Query(i-j, i)) + dp2[i-j-1])%mod;
            }


            dp2[i] = min(dp2[i], dp1[i][j])%mod;


        }
    }

    //cout << evaluateAnswer(n, dp2) << endl;

    int ans = evaluateAnswer(n, dp2);
    return ans;

}

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 10964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 10964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 10964 KB Output isn't correct
2 Halted 0 ms 0 KB -