Cod sursa(job #2346989)

Utilizator priboiraduPriboi Radu Bogdan priboiradu Data 18 februarie 2019 12:01:17
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <deque>

int mn = 10000001;
long long s = 0;

std::deque< std::pair< int, int > >dq;

int main() {
    FILE *fin, *fout;
    int n, k, i, pos, nr;
    fin = fopen( "deque.in", "r" );
    fout = fopen( "deque.out", "w" );
    fscanf( fin, "%d%d", &n, &k );
    for ( i = 0; i < n; i++ ) {
        while ( !dq.empty() && i - dq.front().second + 1 > k )
            dq.pop_front();
        fscanf( fin, "%d", &nr );
        while ( !dq.empty() && nr < dq.back().first )
            dq.pop_back();
        dq.push_back( { nr, i } );
        if ( i >= k - 1 )
            s += ( long long )dq.front().first;
    }
    fprintf( fout, "%lld", s );
    fclose( fin );
    fclose( fout );
    return 0;
}