oj.uz

Submission #746376

# Submission time Handle Problem Language Result Execution time Memory
746376 2023-05-22T12:07:48 Z doowey Peru (RMI20_peru) C++14
18 / 100
 600 ms 12372 KB 
#include <bits/stdc++.h>
#include "peru.h"

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 2511111;
const int MOD = (int)1e9 + 7;
ll dp[N];
ll A[N];
ll ndp[N];
bool off[N];
int pos[N];


int solve(int n, int k, int* v){
    A[0] = (ll)1e18;
    for(int i = 1; i <= n; i ++ ){
        A[i] = v[i - 1];
    }
    priority_queue<pii, vector<pii>, greater<pii>> P;
    deque<pii> L;
    L.push_back(mp(0, -1));
    int id = 0;
    ll mx;
    for(int i = 1; i <= n; i ++ ){

        /*
        while(!L.empty() && A[i] >= A[L.back().fi]){
            if(L.back().se != -1) off[L.back().se] = true;
            L.pop_back();
        }

        while(!L.empty() && L.front().fi <= i - k) {
            if(L.front().se != -1) off[L.front().se] = true;
            L.pop_front();
        }

        if(!L.empty()){
            P.push(mp(A[i] + dp[L.back().fi], id));
            L.back().se = id;
            id ++ ;
        }
        L.push_back(mp(i, -1));
        dp[i] = dp[max(i - k, 0)] + A[L.front().fi];
        while(!P.empty() && off[P.top().se]) P.pop();
        if(!P.empty()) dp[i] = min(dp[i], P.top().fi);
        */
        mx = 0ll;
        dp[i]=(ll)1e18;
        for(int j = i ; j >= max(1, i - k + 1); j -- ){
            mx=max(mx, A[j]);
            dp[i]=min(dp[i], dp[j - 1] + mx);
        }
    }
    int chum = 0;
    int pw = 1;
    for(int i = n; i >= 1; i -- ){
        //cout << dp[i] << " ";
        dp[i] %= MOD;
        chum += (pw * 1ll * dp[i]) % MOD;
        if(chum >= MOD) chum -= MOD;
        pw = (pw * 23ll) % MOD;
    }
    return chum;
}

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:30:9: warning: unused variable 'id' [-Wunused-variable]
   30 |     int id = 0;
      |         ^~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 550 ms 12284 KB Output is correct
16 Correct 437 ms 12264 KB Output is correct
17 Correct 244 ms 12372 KB Output is correct
18 Correct 292 ms 12332 KB Output is correct
19 Correct 349 ms 12264 KB Output is correct
20 Execution timed out 696 ms 12312 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 12284 KB Output is correct
2 Correct 437 ms 12264 KB Output is correct
3 Correct 244 ms 12372 KB Output is correct
4 Correct 292 ms 12332 KB Output is correct
5 Correct 349 ms 12264 KB Output is correct
6 Execution timed out 696 ms 12312 KB Time limit exceeded
7 Halted 0 ms 0 KB -