# PBinfo #2358 – castig – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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

15
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.

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2358)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2358/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2358/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)