Mai intai trebuie sa te autentifici.
Cod sursa(job #2570217)
Utilizator | Data | 4 martie 2020 15:36:36 | |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.01 kb |
#include <bits/stdc++.h>
#define FILE_NAME "deque"
#define fast ios_base :: sync_with_stdio(0); cin.tie(0);
#pragma GCC optimize("O3")
#define NMAX 5000000
using namespace std;
ifstream f(FILE_NAME ".in");
ofstream g(FILE_NAME ".out");
typedef int64_t ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> llp;
typedef pair<ld,ld> pct;
const ll inf = 1LL << 60;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
void add(ll &a , ll b)
{
a += b;
a %= mod;
}
void sub(ll &a, ll b)
{
a = (a - b + mod) % mod;
}
int n, k;
ll sum, v[NMAX];
deque <int> Q;
int main()
{
f >> n >> k;
for(int i = 1; i <= n; ++i)
f >> v[i];
for(int i = 1; i <= n; ++i)
{
while(!Q.empty() && v[i] <= v[Q.back()]) Q.pop_back();
Q.push_back(i);
while(!Q.empty() && i - k + 1 > Q.front()) Q.pop_front();
if(i - k + 1 > 0)
sum += v[Q.front()];
}
g << sum;
f.close();
g.close();
return 0;
}