oj.uz

답안 #1092698

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092698 2024-09-24T18:44:31 Z alexdd Peru (RMI20_peru) C++17
18 / 100
 600 ms 12628 KB 
#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long INF = 1e18;
long long a[2500005];
long long dp[2500005];
long long getmax(int le, int ri)
{
    long long mxm=0;
    for(int i=le;i<=ri;i++)
        mxm = max(mxm, a[i]);
    return mxm;
}
multiset<long long> s;
int solve(int n, int k, int* v)
{
    a[0]=2e9+2;
    deque<pair<long long,long long>> dq;///{poz,mxm}
    dq.push_back({0,0});
    s.insert(0);
    for(int i=1;i<=n;i++)
    {
        a[i]=v[i-1];
        dp[i]=INF;
        dp[i] = min(dp[i], dp[max(0,i-k)]+getmax(max(0,i-k)+1,i));
        while(!dq.empty() && dq.front().first < i-k)
        {
            s.erase(s.find(dp[dq.front().first]+dq.front().second));
            dq.pop_front();
        }
        int ult=-1;
        while(!dq.empty() && a[i] > dq.back().second)
        {
            ult = dq.back().first;
            s.erase(s.find(dp[dq.back().first]+dq.back().second));
            dq.pop_back();
        }
        if(ult!=-1)
        {
            dq.push_back({ult,a[i]});
            s.insert(dp[ult]+a[i]);
        }
        if(!s.empty()) dp[i] = min(dp[i], *s.begin());
        dq.push_back({i,0});
        s.insert(dp[i]);
    }

    long long rez=0,put23=1;
    for(int i=n;i>0;i--)
    {
        rez = (rez + dp[i]%MOD*put23)%MOD;
        put23 = put23*23LL%MOD;
    }
    return rez;
}
/*
8 3
3 2 9 8 7 11 3 4
*/

Subtask #1
18.0 / 18.0

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

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 334 ms 12376 KB Output is correct
16 Correct 291 ms 12368 KB Output is correct
17 Correct 186 ms 12384 KB Output is correct
18 Correct 175 ms 12356 KB Output is correct
19 Correct 218 ms 12380 KB Output is correct
20 Correct 388 ms 12236 KB Output is correct
21 Correct 307 ms 12372 KB Output is correct
22 Correct 574 ms 12560 KB Output is correct
23 Execution timed out 681 ms 12628 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 12376 KB Output is correct
2 Correct 291 ms 12368 KB Output is correct
3 Correct 186 ms 12384 KB Output is correct
4 Correct 175 ms 12356 KB Output is correct
5 Correct 218 ms 12380 KB Output is correct
6 Correct 388 ms 12236 KB Output is correct
7 Correct 307 ms 12372 KB Output is correct
8 Correct 574 ms 12560 KB Output is correct
9 Execution timed out 681 ms 12628 KB Time limit exceeded
10 Halted 0 ms 0 KB -