Cod sursa(job #1044724)

Utilizator Mitsa3Neamt Mihai Mitsa3 Data 30 noiembrie 2013 11:50:07
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
#define maxn 50005
#define INF 0x3f3f3f3f
int s[maxn],a[maxn],mn[maxn],poz[maxn];
void sume_part(int a[], int n)
{
    for( int i = 1; i <= n; i++)
        s[i]+=a[i]+s[i-1];
}
void pozi(int mn[], int n, int poz[])
{
    for( int i = 1; i<=n; i++){
        if(mn[i-1]<s[i]){
            poz[i]=poz[i-1];
            mn[i]=mn[i-1];
        }
        else{
            poz[i]=i;
            mn[i]=s[i];
        }
    }
}
int main()
{
    int n,k;
    fin >> n >> k;
    for( int i = 1; i <= n; i++)
        fin >> a[i];
    sume_part(a,n);
    pozi(mn,n,poz);

    int x,y,mx=-INF;
    for(int i = n; i>=k; i--)
    {
        if(mx<s[i]-s[i-k+1])
        {
            mx=s[i]-s[i-k+1];
            x=poz[i-k+1];
            y=i;
        }
    }
    fout << x << " " << y << " " << mx << "\n";
    return 0;
}