Pagini recente » Cod sursa (job #3125) | Cod sursa (job #3151190) | Cod sursa (job #398602) | Cod sursa (job #2286595) | Cod sursa (job #213659)
Cod sursa(job #213659)
Utilizator |
|
Data |
10 octombrie 2008 20:59:12 |
Problema |
Buline |
Scor |
100 |
Compilator |
cpp |
Status |
done |
Runda |
Arhiva de probleme |
Marime |
1.8 kb |
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <utility>
#include <functional>
#define pb push_back
#define f first
#define s second
#define sz size
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define C(v) C.erase( all(v) )
#define FORit(it,v) for(it = (v).begin();it != (v).end();++it)
#define mp make_pair
#define N_MAX 1<<18
#define IN "buline.in"
#define OUT "buline.out"
#define oo 1<<30
int N;
int S[N_MAX],T[N_MAX],V[N_MAX];
II void scan()
{
int x,y;
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
scanf("%d\n",&N);
FOR(i,1,N)
{
scanf("%d %d\n",&x,&y);
if(y)
{
V[i] = x;
continue;
}
V[i] = -x;
}
}
II void solve()
{
int start(0),end(0);
FOR(i,1,N)
{
S[i] = S[i-1] + V[i];
T[i] = max(T[i-1],S[i]);
}
int suma(0),best(-oo);
FOR(i,1,N)
if(V[i] > best)
{
best = V[i];
end = i;
}
FOR(i,1,N)
{
suma += V[i];
if(suma > best)
{
best = suma;
end = i;
}
if(suma < 0)
suma = 0;
}
FOR(i,1,N)
{
if(best < S[N] - S[i-1] + T[i-1])
{
best = S[N] - S[i-1] + T[i-1];
end = 0;
start = i;
}
}
suma = 0;
if(!end)
for(int i=start;;suma += V[i],++i)
{
if(i == N+1)
i = 1;
if(suma == best)
{
printf("%d %d %d\n",best,start,N-start+i);
return;
}
}
else
for(int i=end;;suma += V[i],--i)
if(suma == best)
{
printf("%d %d %d\n",best,i+1,end-i);
return;
}
}
int main()
{
scan();
solve();
return 0;
}