Cod sursa(job #28006)

Utilizator cretuMusina Rares cretu Data 7 martie 2007 13:25:10
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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 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 < n; j++)
            if (i > j && s[i]-m[j] > res)     
            {
                 res = s[i]-m[j];
                 pozi = j+1;
                 l = i-j;              
            }  
            else if (j > i && s[i+n]-m[j] > res)
                 {
                     res = s[i+n]-m[j];
                     pozi = j+1;
                     l = i-j+n;            
                 }     
     ofstream fout("buline.out");
     fout << res << " " << pozi << " " << l << "\n";
     fout.close();
     
     return 0;
            
}