Ana şi Bogdan au participat la un concurs şi au obţinut premiul I, respectiv premiul al II-lea. La concurs există n premii, numerotate de la 1 la n, în ordinea în care sunt aşezate pe masă. Regulamentul concursului prevede că fiecare câştigător trebuie să aleagă exact k premii aşezate pe poziţii consecutive. Fiindcă Ana are premiul I, ea poate să îşi aleagă prima premiile. Apoi Bogdan va alege şi el k premii aşezate pe poziţii consecutive dintre cele rămase după ce a ales Ana. Ana este foarte supărată pe Bogdan, aşa că ea urmăreşte ca Bogdan să câştige cât mai puţin, fără să o intereseze prea mult ce premii alege ea.

Cerința

Scrieţi un program care, cunoscând n, k şi valorile celor n premii, determină cel mai mic număr valmin, astfel încât Bogdan să nu poate selecta k premii aşezate pe poziţii consecutive cu o valoare totală mai mare decât valmin.

Date de intrare

Fișierul de intrare castig.in conţine pe prima linie două numere naturale n k, reprezentând numărul total de premii şi respectiv numărul de premii consecutive pe care câştigătorii trebuie să le aleagă. Pe a doua linie se află n numere naturale v[1], v[2], …, v[n] reprezentând, în ordinea aşezării pe masă, valorile celor n premii.

Date de ieșire

Fișierul de ieșire castig.out va conţine o singură linie pe care va fi scris numărul natural valmin, determinat conform cerinţei.

Restricții și precizări

3 ≤ n ≤ 100 000
1 ≤ k ≤ n/3
1 ≤ v[i] ≤ 1 000 000 000, pentru 1 ≤ i ≤ n

Exemplu

castig.in

10 3
2 5 7 3 1 22 7 2 9 1

castig.out

Explicație

Dacă Ana alege premiile cu valorile 1 22 7, secvenţa cea mai convenabilă pentru Bogdan este 5 7 3 (deci valmin este 15). Există şi alte alegeri bune pentru Ana (22 7 2), dar valmin rămâne acelaşi.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema castig:

#include <fstream>
#define NMAX 100002
using namespace std;
ifstream fin("castig.in");
ofstream fout("castig.out");
int n, k;
int v[NMAX];
long long int s[NMAX];
long long int smax[NMAX];
long long int dmax[NMAX];
int main()
{long long int sum=0, valmin, maxim;
 int i;
 fin>>n>>k;
 for (i=1; i<=n; i++) fin>>v[i];
 for (i=1; i<=k; i++) sum+=v[i];
 s[1]=smax[1]=sum;
 for (i=2; i<=n-k+1; i++)
     {
      s[i]=s[i-1]-v[i-1]+v[i+k-1];
      smax[i]=smax[i-1];
      if (s[i]>smax[i]) smax[i]=s[i];
     }
 dmax[n-k+1]=s[n-k+1];
 for (i=n-k; i>=1; i--)
     {
         dmax[i]=dmax[i+1];
         if (s[i]>dmax[i]) dmax[i]=s[i];
     }

 valmin=dmax[k+1];
 for (i=2; i<=k; i++)
 if (valmin>dmax[i+k]) valmin=dmax[i+k];

 for (i=k+1; i<=n-k+1; i++)
    {
      maxim=smax[i-k];
      if (maxim<dmax[i+k]) maxim=dmax[i+k];
      if (maxim<valmin)    valmin=maxim;
    }

 fout<<valmin<<'\n';

 fout.close();
 return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2358 castig

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2358 castig de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2358 castig