| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1092698 |
2024-09-24T18:44:31 Z |
alexdd |
Peru (RMI20_peru) |
C++17 |
|
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
*/
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
