oj.uz

Submission #483714

# Submission time Handle Problem Language Result Execution time Memory
483714 2021-11-01T01:18:40 Z tranxuanbach Peru (RMI20_peru) C++17
18 / 100
 17 ms 4084 KB 
#include "peru.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;
 
const int N = 2e3 + 5, M = 19, mod = 1e9 + 7;
const ll infll = (ld)1e18 + 7;
 
namespace {
    deque <pair <int, ll>> dq;
    multiset <ll> mtsdp;
    ll dp[N];
    int sparse[M][N];
 
    int rmq(int l, int r){
        int z = __lg(r - l + 1);
        return max(sparse[z][l], sparse[z][r - (1 << z) + 1]);
    }
 
    int convert(int n){
        int ans = 0;
        For(i, 0, n){
            ans = (ll)ans * 23 % mod;
            ans += dp[i] % mod;
            if (ans >= mod){
                ans -= mod;
            }
        }
        return ans;
    }
}
 
int solve(int n, int k, int* a){
    For(i, 0, n){
        sparse[0][i] = a[i];
    }
    For(j, 1, M){
        ForE(i, 0, n - (1 << j)){
            sparse[j][i] = max(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
        }
    }
    if (k == 1){
        For(i, 0, n){
            dp[i] = (i == 0 ? 0 : dp[i - 1]) + a[i];
        }
        return convert(n);
    }
    For(i, 0, n){
        int val = 0;
        while (!dq.empty() and a[dq.front().fi] <= a[i]){
            mtsdp.erase(mtsdp.lower_bound(dq.front().se));
            val = a[dq.front().fi];
            dq.pop_front();
        }
        if (!dq.empty()){
            mtsdp.erase(mtsdp.lower_bound(dq.front().se));
            dq.front().se -= val;
            dq.front().se += a[i];
            mtsdp.insert(dq.front().se);
        }
        dp[i] = infll;
        if (!mtsdp.empty()){
            dp[i] = *mtsdp.begin();
        }
        dp[i] = min(dp[i], rmq(max(0, i - k + 1), i) + (i >= k ? dp[i - k] : 0));
        dq.push_front(make_pair(i, dp[i]));
        mtsdp.insert(dp[i]);
        while (!dq.empty() and dq.back().fi == i - k + 1){
            mtsdp.erase(mtsdp.lower_bound(dq.back().se));
            dq.pop_back();
        }
    }
    // For(i, 0, n){
    //     cout << dp[i] << ' ';
    // } cout << endl;
    return convert(n);
}
 
 
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
*/

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 360 KB Output is correct
4 Correct 1 ms 340 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 340 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 360 KB Output is correct
4 Correct 1 ms 340 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 340 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 Runtime error 17 ms 4084 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -