Pagini recente » Monitorul de evaluare | Diferente pentru problema/buline intre reviziile 11 si 9 | Cod sursa (job #3324400) | Cod sursa (job #3324417)
#include <fstream>
using namespace std;
#define int long long
ifstream in("buline.in");
ofstream out("buline.out");
int n;
int v[200005];
int sp[200005];
int INF = (1LL << 60);
signed main()
{
in>>n;
int x, y;
int total = 0;
for(int i = 1; i<=n; i++)
{
in>>x>>y;
if(y == 0)
{
v[i] = -x;
}
else
{
v[i] = x;
}
total += v[i];
sp[i] = sp[i - 1] + v[i];
}
int best = 0;
int smax = -INF;
int stmax, drmax;
for(int i = 1; i<=n; i++)
{
int sum = sp[i] - sp[best];
if(sum > smax)
{
smax = sum;
stmax = best + 1;
drmax = i;
}
if(sp[i] <= sp[best])
{
best = i;
}
}
best = 0;
int smin = INF;
int stmin, drmin;
for(int i = 1; i<=n; i++)
{
int sum = sp[i] - sp[best];
if(sum < smin)
{
smin = sum;
stmin = best + 1;
drmin = i;
}
if(sp[i] > sp[best])
{
best = i;
}
}
// out<<total<<'\n';
// out<<smax<<" "<<smin<<'\n';
if(smax > total - smin)
{
out<<smax<<" "<<stmax<<" "<<drmax - stmax + 1;
}
else
{
out<<total - smin<<" "<<drmin + 1<<" "<<stmin + n - 1 - drmin;
}
return 0;
}