Cod sursa(job #833589)

Utilizator valentina506Moraru Valentina valentina506 Data 12 decembrie 2012 19:29:57
Problema Subsecventa de suma maxima Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
using namespace std;
int n,m,t,i,j,l[1000001],d[1000001],a[2000001],ok,st,dr;
long long s;
int main()
{
    ifstream f("raliu.in");
    ofstream g("raliu.out");
    f>>t;
    while(t--)
    {
        f>>n;
        for(i=1;i<=n;++i)
        f>>l[i];
        for(i=1;i<=n;++i)
        {
            f>>d[i];
            a[i]=a[i+n]=l[i]-d[i];
        }
        ok=s=m=0;
        for(i=1;i<=2*n&&!ok;i++)
        {
            if(s<0)
            s=a[i],m=1;
            else
            s+=a[i],m++;
            if(s>=0&&m==n)
            {
               ok=1;
               st=i-n+1;
            }
            g<<s<<" ";

        }

        if(ok)
        g<<"DA\n"<<st<<"\n";
        else
        g<<"NU\n";

    }

}