Cod sursa(job #3216911)

Utilizator BoggiGurau Bogdan Boggi Data 20 martie 2024 12:34:14
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
/*
AM un sir cu N elem vr sa iau subsiruri de lg K si sa
iau minimul subsirului si sa l adun la o suma;

idee : HEAP
cand trecem la o sub ce incepe cu i+1 de la cea cu i
pierdem primul el, si adaugam urm
in heap avem elMinim;
daca pos lui < i, ii dam pop;
dam push
*/

#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

const int MAX_VAL = 10000000;

#define VI vector<int>
#define PI pair<int, int>
#define PQ priority_queue

void brute();
void heapSol();

VI sir;
int N, K;
PQ<PI, vector<PI>, greater<PI>> heap;

int main() {
    fin >> N >> K;
    sir = VI(N + 1);
    for (int i = 0; i < N; ++i) {
        fin >> sir[i];
    }
    fout << -1;
}

void heapSol() {
    fin >> N >> K;
    for (int i = 0; i < K; ++i) {
        int no;
        fin >> no;
        heap.push(make_pair(no, i));
    }
    long long suma = heap.top().first;
    for (int i = K; i < N; ++i) {
        int no;
        fin >> no;
        heap.push(make_pair(no, i));
        while (heap.top().second < i - K + 1) {
            heap.pop();
        }
        //fout <<heap.top().first << ' ';
        suma += heap.top().first;
    }
    fout << suma;
}

void brute() {
    fin >> N >> K;
    sir = VI(N + 1);
    for (int i = 0; i < N; ++i) {
        fin >> sir[i];
    }
    long long suma = 0;
    int lastPos = -1;
    int minSub;
    for (int i = 0; i <= N - K; ++i) {
        if (lastPos < i) {
            //fout << " AIO";
            minSub = MAX_VAL;
            for (int j = 0; j < K; ++j) {
                if (sir[i + j] < minSub) {
                    minSub = sir[i + j];
                    lastPos = i + j;
                }
            }
        } else {
            minSub = min(sir[i + K - 1], minSub);
        }
        suma += minSub;
    }
    fout << suma;
}