#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2500000;
const int BSIZE = 1e4;
const int MOD = 1e9 + 7;
//char buf[BSIZE];
//int ix = BSIZE;
//FILE* fin = fopen( "peru.in", "r" );
//ofstream fout( "peru.out" );
//static inline char get_ch() {
// if ( ix == BSIZE ) {
// fread( buf, 1, BSIZE, fin );
// ix = 0;
// }
// return buf[ix++];
//}
//inline int get_int() {
// int x = 0;
// char ch;
// while ( !isdigit( ch = get_ch() ) );
// do {
// x = x * 10 + ch - '0';
// } while ( isdigit( ch = get_ch() ) );
// return x;
//}
int v[NMAX + 1];
long long dp[NMAX + 1];
deque <int> dq;
deque <pair<int, int>> dq2;
int main() {
int n, k, t;
// cin >> t;
cin >> n >> k;
// n = get_int();
// k = get_int();
for ( int i = 1; i <= n; i ++ ) {
// v[i] = get_int();
cin >> v[i];
}
for ( int i = 1; i <= k; i ++ ) {
while ( !dq.empty() && v[dq.back()] <= v[i] ) {
if ( dq.size() >= 2 && !dq2.empty() && dq2.back().first == dq[dq.size() - 2] && dq2.back().second == dq.back() )
dq2.pop_back();
dq.pop_back();
}
dq.push_back( i );
if ( dq.size() > 1 ) {
int aux1 = dq[dq.size() - 2], aux2 = i;
while ( !dq2.empty() && dp[dq2.back().first] + v[dq2.back().second] >= dp[aux1] + v[aux2] )
dq2.pop_back();
dq2.push_back( { aux1, aux2 } );
}
dp[i] = v[dq.front()];
}
// cout << "OK" << endl;
for ( int i = k + 1; i <= n; i ++ ) {
while ( !dq.empty() && v[dq.back()] <= v[i] ) {
if ( dq.size() >= 2 && !dq2.empty() && dq2.back().first == dq[dq.size() - 2] && dq2.back().second == dq.back() )
dq2.pop_back();
dq.pop_back();
}
dq.push_back( i );
while ( dq.front() <= i - k ) dq.pop_front();
dp[i] = dp[i - k] + v[dq.front()];
if ( dq.size() > 1 ) {
int aux1 = dq[dq.size() - 2], aux2 = i;
while ( !dq2.empty() && dp[dq2.back().first] + v[dq2.back().second] >= dp[aux1] + v[aux2] )
dq2.pop_back();
dq2.push_back( { aux1, aux2 } );
while ( dq2.front().first <= i - k ) dq2.pop_front();
if ( t == 1 )
dp[i] = min( dp[i], dp[dq2.front().first] + v[dq2.front().second] );
}
if ( t == 2 )
for ( int j = 0; j + 1 < dq.size(); j ++ ) {
dp[i] = min( dp[i], dp[dq[j]] + v[dq[j + 1]] );
}
}
int p23 = 1, ans = 0;
for ( int i = n; i >= 1; i -- ) {
ans += dp[i] % MOD * p23 % MOD;
if ( ans >= MOD ) ans -= MOD;
p23 = (long long)p23 * 23 % MOD;
// cout << dp[n - i + 1] << ' ';
}
// cout << endl;
cout << ans;
// fout << endl << ans;
return 0;
}
Compilation message
peru.cpp: In function 'int main()':
peru.cpp:89:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for ( int j = 0; j + 1 < dq.size(); j ++ ) {
| ~~~~~~^~~~~~~~~~~
peru.cpp:84:13: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
84 | if ( t == 1 )
| ^~
/usr/bin/ld: /tmp/cc7cmLax.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqOOqDt.o:peru.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc7cmLax.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status
