Cod sursa(job #1629068)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 4 martie 2016 12:33:08
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int Mn = 2e5 + 6;
const int oo = 2e9 + 10;

int n, id, len, sum, ans = -oo, st = 1;
int s[Mn], mx[Mn], last[Mn];

int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);

    mx[0] = -oo;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int a,b;
        scanf("%d %d", &a, &b);
        if (b == 0)
           a = -a;

        sum += a;
        if (sum < a)
           sum = a, st = i;

        if (sum > ans)
           ans = sum, id = st, len = i - st + 1;

        s[i] = s[i - 1] + a;
        if (mx[i - 1] > s[i])
           mx[i] = mx[i - 1], last[i] = last[i - 1];
      else
           mx[i] = s[i], last[i] = i;

        //printf("%d %d\n", s[i], mx[i]);
    }

    if (ans < mx[id - 1] + sum)
       ans = mx[id - 1] + sum, len += last[id - 1];

    printf("%d %d %d\n", ans, id, len);

  return 0;
}