Cod sursa(job #27599)

Utilizator cretuMusina Rares cretu Data 6 martie 2007 15:45:33
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#define MAX 200001
#define INF 99999999
#define mini(a, b) ((a) < (b) ? (a) : (b))

using namespace std;

int s[2*MAX], m[2*MAX], a[MAX];

int main()
{
    int n, i, j, bulina, culoare;
    
    s[0] = m[0] = 0;
    
    ifstream fin("buline.in");
    fin >> n;
    for (i = 1; i <= n; i++)    
    {
        fin >> bulina >> culoare;    
        if (!culoare) a[i] = 0-bulina;   
        else          a[i] = bulina;
        s[i] = s[i-1] + a[i];         
    }
    for (i = n+1; i <= 2*n; i++)
    {
        a[i] = a[i-n];
        s[i] = s[i-1] + a[i];
    }
    fin.close();
    
    int naux = n;
    n *= 2;
    
    int res = -INF, pozi, l;
    
    for (i = 1; i <= n; i++)
        m[i] = mini(m[i-1], s[i]);
    
    for (i = 1; i <= n; i++)
        for (j = 1; j < i && j < naux; j++)
            if (i-j <= naux && s[i]-m[j] > res)     
            {
                 res = s[i]-m[j];
                 pozi = j+1;
                 l = i-j;              
            }       
     ofstream fout("buline.out");
     fout << res << " " << pozi << " " << l << "\n";
     fout.close();
     
     return 0;
            
}