Cod sursa(job #1324562)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 22 ianuarie 2015 15:50:47
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<stdio.h>
#include<set>
#include<vector>
#include <stdint.h>
#define FIN "deque.in"
#define FOUT "deque.out"
#define MAX 5000000
using namespace std;


struct setOrder
{

    bool operator()(long long a,long long int b) const
    {
        return (int)a < (int)b;

    }
};


multiset<int64_t, setOrder> heap;
int64_t arr[MAX];
int64_t sum;
unsigned long long int n,k;




int read()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d ", &n, &k);

    for(unsigned long int i=1;i<=n;i++)
    {
        scanf("%d", &arr[i]);
    }

    return 0;
}

int solve()
{
    for(int i=1;i<=k;i++)
        heap.insert(arr[i]);

    int index = k;

    while(index < n)
    {
        sum += *heap.begin();

       /* multiset<int64_t>::iterator it = heap.begin();
        for(int i=1;i<=k;i++)
        {
            printf("%d ", *it);
            it++;

        }
*/

       // printf("minimul este %d \n", *heap.begin());
       // printf("sterg %d \n", arr[index - k + 1]);
        heap.erase(arr[index - k + 1]);
        heap.insert(arr[index + 1]);
      //  printf("inserez %d \n", arr[index + 1]);

      //  printf("\n");


        index++;

    }

    sum += *heap.begin();

    return 0;
}

int write()
{
    printf("%d", sum);
    return 0;
}

int main()
{
    read();
    solve();
    write();
}