ks

Ana şi Bogdan au inventat din nou un joc, pe care l-au denumit ks. Pe tabla de joc sunt plasate pe poziţii consecutive n jetoane, pe fiecare jeton fiind scris un număr natural nenul.

Ana este prima la mutare şi are voie să extragă de pe tablă exact k jetoane situate pe poziţii consecutive.

Bogdan mută al doilea şi are şi el voie să extragă exact k jetoane, dintre cele rămase pe tablă, situate de asemenea pe poziţii consecutive.

Punctajul asociat unei mutări este egal cu suma numerelor scrise pe jetoanele extrase la mutarea respectivă.

Scopul Anei este să efectueze mutarea sa astfel încât punctajul obţinut de Bogdan să fie cât mai mic. Considerăm că atât Ana, cât şi Bogdan joacă optim.

Cerința

Cunoscând numărul de jetoane de pe tabla de joc, valorile înscrise pe acestea, precum şi valoarea k, scrieţi un program care să determine care este cel mai bun punctaj pe care Bogdan îl poate obţine, ştiind că ambii jucători joacă optim.

Date de intrare

Fișierul de intrare ks.in conține pe prima linie două numere naturale separate prin spaţiu n k, având semnificaţia din enunţ. Pe cea de a doua linie se află n valori naturale nenule, separate prin câte un spaţiu, reprezentând valorile înscrise pe cele n jetoane, în ordinea în care acestea sunt plasate pe tabla de joc.

Date de ieșire

Fișierul de ieșire ks.out va conține o singură linie pe care va fi scris un număr natural reprezentând punctajul maxim pe care îl poate obţine Bogdan la mutarea sa, ştiind că ambii jucători joacă optim.

Restricții și precizări

  • 3 ≤ n ≤ 100 000
  • 1 ≤ k ≤ n/3
  • Valorile înscrise pe jetoane sunt numere naturale nenule ≤109.
  • După ce Ana extrage jetoanele sale, jetoanele rămase pe tablă îşi vor păstra poziţiile iniţiale.

Exemplu

ks.in

10 3
1 2 5 4 15 2 4 5 1 6

ks.out

12

Explicație

Există mai multe mutări optime pentru Ana. Una dintre acestea este de a selecta jetoanele 5, 4, 15.

În acest caz cea mai bună mutare pentru Bogdan este de a selecta jetoanele 5, 1, 6 care i-ar aduce un punctaj egal cu 12, maxim posibil.

O altă mutare optimă pentru Ana este de a alege jetoanele 4, 15, 2, sau 15, 2, 4 punctajul maxim pe care îl poate obţine Bogdan rămânând acelaşi, 12.

SOLUTIE 1

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("ks.in");
ofstream fout("ks.out");
const int nm=100005,gol=-1;
long long int a[nm],st[nm],dr[nm],s[nm],i,n,k,su=0,rez=200000000000000000;
int main()
{
    fin>>n>>k;
    fill(s,s+n+2,gol);
    for(i=1;i<=n;i++)
    {
        fin>>a[i];su+=a[i];
        if(i>=k){su-=a[i-k];s[i-k+1]=su;}
    }
    st[k]=s[1];
    for(i=k+1;i<=n;i++)st[i]=max(st[i-1],s[i-k+1]);
    dr[n-k+1]=s[n-k+1];
    for(i=n-k;i>0;i--)dr[i]=max(dr[i+1],s[i]);
    for(i=2;i<=n-k+1;i++)
     rez=min(rez,max(st[i-1],dr[i+k]));
    fout<<rez;
    return 0;
}

SOLUTIE 2

#include <fstream>
#define NMAX 100002

using namespace std;

int n, K;
long long int S[NMAX];
long long int maxst[NMAX];
long long int maxdr[NMAX];
int a[NMAX];

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

void citire();
void det_sume();
long long int rezolva();

int main()
{
    citire();
    det_sume();
    fout<<rezolva()<<'\n';
    fout.close();
    return 0;
}

void citire()
{int i;
 fin>>n>>K;
 for (i=1; i<=n; i++) fin>>a[i];
}

void det_sume()
{int i;
 for (i=1; i<=K; i++) {S[1]+=a[i]; maxst[i]=-1;}
 maxst[K]=S[1];
 for (i=2; i<=n-K+1; i++)
     {S[i]=S[i-1]-a[i-1]+a[i+K-1];
      if (S[i]>maxst[i+K-2])
          maxst[i+K-1]=S[i];
          else
          maxst[i+K-1]=maxst[i+K-2];
     }
 for (i=n; i>n-K+1; i--) maxdr[i]=-1;
 maxdr[n-K+1]=S[n-K+1];
 for (i=n-K; i>0; i--)
      if (S[i]>maxdr[i+1])
         maxdr[i]=S[i];
         else
         maxdr[i]=maxdr[i+1];
}

long long int rezolva()
{
  long long int optim=maxdr[K+1], maxim;
  int i;
  for (i=2; i<K; i++)
      if (optim>maxdr[i+K]) optim=maxdr[i+K];
  for (i=K; i<=n-K+1; i++)
      {//Ana ia o secventa de K jetoane incepand cu pozitia i
       maxim=maxst[i-1];
       if (maxim<maxdr[i+K]) maxim=maxdr[i+K];
       if (optim>maxim) optim=maxim;
      }
   for (i=n-K+2; i<=n; i++)
        if (optim>maxst[i-1]) optim=maxst[i-1];
  return optim;
}