Cod sursa(job #833589)
Utilizator | Moraru 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";
}
}