oj.uz

Submission #401605

# Submission time Handle Problem Language Result Execution time Memory
401605 2021-05-10T14:45:03 Z maximath_1 Peru (RMI20_peru) C++17
100 / 100
 158 ms 60156 KB 
#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
 
#define ll long long
const ll mod = 1e9 + 7;
const ll base = 23;
const ll inf_ll = mod * 2ll * mod + 69ll;
const int MX = 2500005;
 
ll pwbase[MX];
int n, k, v[MX];
ll dp[MX];
struct dt{
	int id;
	ll dp_id, dp_min;
};
deque<dt> dq;
 
int vv = 0;
void pop_front(){
	if(dq.size()) dq.pop_front();
	if(dq.size()){
		ll dp_i = dq.front().dp_id;
		dq.front().dp_id = inf_ll;
		dq.front().dp_min = inf_ll;
 
		for(int i = 1; i < dq.size(); i ++){
			if(dq[i].dp_id <= dp_i) break;
			vv ++;
			dq[i].dp_min = min(dq[i - 1].dp_min, dq[i].dp_id);
		}
	}
}
 
void push_back(int id){
	if(dq.empty()){
		dq.push_back((dt){id, inf_ll, inf_ll});
		return;
	}
 
	ll bf = dp[dq.back().id];
	dq.push_back((dt){id, bf + v[id], min(bf + v[id], dq.back().dp_min)});
	return;
}
 
int solve(int N, int K, int* V){
	n = N; k = K;
	for(int i = 0; i < n; i ++) v[i] = V[i];
 
	for(int i = 0; i < n; i ++){
		if(dq.size() && i - dq.front().id >= k) pop_front();
		while(dq.size() && v[i] >= v[dq.back().id]) dq.pop_back();
 
		push_back(i);
		dp[i] = (ll)v[dq.front().id];
 
		if(i >= k) dp[i] += dp[i - k];
		if(dq.size())
			dp[i] = min(dp[i], dq.back().dp_min);
	}
 
	assert(vv <= 5 * n);
 
	pwbase[0] = 1ll;
	for(int i = 1; i < n; i ++)
		pwbase[i] = (pwbase[i - 1] * 1ll * base) % mod;
 
	ll ans = 0ll;
 
	for(int i = 0; i < n; i ++){
		dp[i] %= mod;
		(ans += (pwbase[n - 1 - i] * 1ll * dp[i]) % mod) %= mod;
	}
 
	return ans;
}

Compilation message

peru.cpp: In function 'void pop_front()':
peru.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<dt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i = 1; i < dq.size(); i ++){
      |                  ~~^~~~~~~~~~~

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 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 0 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
31.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 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 0 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 22 ms 9848 KB Output is correct
16 Correct 35 ms 9768 KB Output is correct
17 Correct 25 ms 9812 KB Output is correct
18 Correct 26 ms 9784 KB Output is correct
19 Correct 36 ms 9724 KB Output is correct
20 Correct 37 ms 9760 KB Output is correct
21 Correct 29 ms 9824 KB Output is correct
22 Correct 27 ms 9888 KB Output is correct
23 Correct 32 ms 9892 KB Output is correct
24 Correct 25 ms 9812 KB Output is correct
25 Correct 25 ms 9808 KB Output is correct
26 Correct 23 ms 9852 KB Output is correct
27 Correct 24 ms 9876 KB Output is correct
28 Correct 20 ms 9900 KB Output is correct
29 Correct 20 ms 9980 KB Output is correct
30 Correct 23 ms 9860 KB Output is correct
31 Correct 28 ms 9756 KB Output is correct
32 Correct 20 ms 9796 KB Output is correct
33 Correct 27 ms 9860 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9848 KB Output is correct
2 Correct 35 ms 9768 KB Output is correct
3 Correct 25 ms 9812 KB Output is correct
4 Correct 26 ms 9784 KB Output is correct
5 Correct 36 ms 9724 KB Output is correct
6 Correct 37 ms 9760 KB Output is correct
7 Correct 29 ms 9824 KB Output is correct
8 Correct 27 ms 9888 KB Output is correct
9 Correct 32 ms 9892 KB Output is correct
10 Correct 25 ms 9812 KB Output is correct
11 Correct 25 ms 9808 KB Output is correct
12 Correct 23 ms 9852 KB Output is correct
13 Correct 24 ms 9876 KB Output is correct
14 Correct 20 ms 9900 KB Output is correct
15 Correct 20 ms 9980 KB Output is correct
16 Correct 23 ms 9860 KB Output is correct
17 Correct 28 ms 9756 KB Output is correct
18 Correct 20 ms 9796 KB Output is correct
19 Correct 27 ms 9860 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 141 ms 59176 KB Output is correct
35 Correct 130 ms 59212 KB Output is correct
36 Correct 133 ms 59160 KB Output is correct
37 Correct 134 ms 59164 KB Output is correct
38 Correct 134 ms 59292 KB Output is correct
39 Correct 127 ms 59212 KB Output is correct
40 Correct 135 ms 59248 KB Output is correct
41 Correct 146 ms 59240 KB Output is correct
42 Correct 139 ms 59268 KB Output is correct
43 Correct 51 ms 24012 KB Output is correct
44 Correct 93 ms 35668 KB Output is correct
45 Correct 92 ms 35656 KB Output is correct
46 Correct 97 ms 35648 KB Output is correct
47 Correct 137 ms 59444 KB Output is correct
48 Correct 139 ms 59344 KB Output is correct
49 Correct 126 ms 59588 KB Output is correct
50 Correct 135 ms 60044 KB Output is correct
51 Correct 138 ms 59832 KB Output is correct
52 Correct 148 ms 60156 KB Output is correct
53 Correct 147 ms 60128 KB Output is correct
54 Correct 156 ms 59180 KB Output is correct
55 Correct 137 ms 59132 KB Output is correct
56 Correct 137 ms 59108 KB Output is correct
57 Correct 134 ms 59188 KB Output is correct
58 Correct 133 ms 59172 KB Output is correct
59 Correct 140 ms 59128 KB Output is correct
60 Correct 154 ms 59292 KB Output is correct
61 Correct 156 ms 59324 KB Output is correct
62 Correct 158 ms 59388 KB Output is correct
63 Correct 149 ms 59288 KB Output is correct