Cod sursa(job #1076540)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 10 ianuarie 2014 12:50:10
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

int v[5000001];

class Compare
{
public:
  bool operator()(const int& p, const int& q)
  {
    if (v[p] > v[q])
      return true;
    return false;
  }
};

int main()
{
  FILE *in, *out;
  
  in  = fopen ("deque.in",  "r");
  out = fopen ("deque.out", "w");

  priority_queue <int, vector<int>, Compare > PQ; 
  long long suma = 0;

  int n, k; fscanf (in, "%d %d", &n, &k);
  for (int i = 1; i <= n; ++i)
      fscanf (in, "%d", &v[i]);

  for (int i = 1; i <= n; ++i)
    {
      PQ.push(i);

      if (i >= k)
	{
	  while (PQ.top() <= i - k)
	    PQ.pop();

	  suma += v[PQ.top()];
	}
    }

  fprintf (out, "%lld\n", suma);

  fclose (in);
  fclose (out);

  return 0;
}