Cod sursa(job #792698)

Utilizator idomiralinIdomir Alin idomiralin Data 29 septembrie 2012 10:30:44
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
# include <cstdio>

using namespace std;

int n, x, cul, best, bestsum, pozi, pozf, pozfi, pozff, v[200005];
int main()
{
    int i;
    
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    
    scanf("%d",&n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d%d",&x,&cul);
        v[i] = (!cul ? - x : x);
        }
    
    for (i = n + 1; i <= 2 * n; i++)
        v[i] = v[i - n];
        
    best = v[1]; pozi = 1;
    for (i = 2; i <= 2 * n; i++)
    {
        if (best + v[i] >= v[i] && i - pozi + 1 <= n)
                 best += v[i], pozf = i;
            else {
                      best = v[i];
                      pozi = i;
                      pozf = i;
                      }
        
        if (bestsum < best)
        {
                    bestsum = best;
                    pozfi = pozi;
                    pozff = pozf;
                    }
        }
        
    printf("%d %d %d",bestsum, pozfi, pozff - pozfi + 1);
    
return 0;
}