oj.uz

답안 #401497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401497 2021-05-10T12:11:32 Z tranxuanbach Peru (RMI20_peru) C++17
49 / 100
 148 ms 87416 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 = 4e5 + 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] = 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.find(dq.front().se));
            val = a[dq.front().fi];
            dq.pop_front();
        }
        if (!dq.empty()){
            mtsdp.erase(mtsdp.find(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.find(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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 118 ms 33232 KB Output is correct
16 Correct 127 ms 33228 KB Output is correct
17 Correct 109 ms 33252 KB Output is correct
18 Correct 93 ms 33232 KB Output is correct
19 Correct 89 ms 33216 KB Output is correct
20 Correct 83 ms 33220 KB Output is correct
21 Correct 128 ms 33288 KB Output is correct
22 Correct 120 ms 33316 KB Output is correct
23 Correct 126 ms 33360 KB Output is correct
24 Correct 115 ms 33176 KB Output is correct
25 Correct 123 ms 33288 KB Output is correct
26 Correct 111 ms 33164 KB Output is correct
27 Correct 111 ms 33280 KB Output is correct
28 Correct 145 ms 33356 KB Output is correct
29 Correct 110 ms 33552 KB Output is correct
30 Correct 113 ms 33192 KB Output is correct
31 Correct 114 ms 33228 KB Output is correct
32 Correct 122 ms 33304 KB Output is correct
33 Correct 113 ms 33252 KB Output is correct

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 33232 KB Output is correct
2 Correct 127 ms 33228 KB Output is correct
3 Correct 109 ms 33252 KB Output is correct
4 Correct 93 ms 33232 KB Output is correct
5 Correct 89 ms 33216 KB Output is correct
6 Correct 83 ms 33220 KB Output is correct
7 Correct 128 ms 33288 KB Output is correct
8 Correct 120 ms 33316 KB Output is correct
9 Correct 126 ms 33360 KB Output is correct
10 Correct 115 ms 33176 KB Output is correct
11 Correct 123 ms 33288 KB Output is correct
12 Correct 111 ms 33164 KB Output is correct
13 Correct 111 ms 33280 KB Output is correct
14 Correct 145 ms 33356 KB Output is correct
15 Correct 110 ms 33552 KB Output is correct
16 Correct 113 ms 33192 KB Output is correct
17 Correct 114 ms 33228 KB Output is correct
18 Correct 122 ms 33304 KB Output is correct
19 Correct 113 ms 33252 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Runtime error 148 ms 87416 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -