Cod sursa(job #921614)

Utilizator h2g2Ford Prefect h2g2 Data 21 martie 2013 09:53:14
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#define nmax 200005
using namespace std;

int v[nmax], ssm[nmax], sum[nmax], mp[nmax];
int n, i, j, sol = 0, temp;

int main() {
    ifstream f("buline.in");
    ofstream g("buline.out");

    f>>n;

    mp[0] = 0;
    ssm[0] = 0;
    sum[0] = 0;
    for(i=1; i<=n; i++) {
        f>>v[i]>>temp;

        if(temp==0) v[i] *= -1;

        ssm[i] = v[i] + max(ssm[i-1], 0);
        sol = max(sol, ssm[i]);

        sum[i] = sum[i-1] + v[i];   //sum[i] = suma pe secventa [1, i]
    }

    //am acum s[i] = suma maxima a unei subsecvente care se termina pe poz i
    //               si incepe undeva in dreapta pozitiei 1
    //asta-i pentru cazul in care subsecventa solutie nu ii intrerupta

    //in cazul in care subsecventa solutie se intrerupe (ii circulara)
    //atunci ea ii de forma [i, n] + [1, j]


    //astfel, pentru fiecare secventa [1, j], pot sa pun inaintea ei una dintre:
    //[j+1, n], [j+2, n], ..., [n-1, n], [n, n].
    //si o aleg pe cea care are suma maxima

    mp[n] = v[n];
    for(i=n-1; i>=1; i--) mp[i] = mp[i+1] + v[i];
    for(i=n-1; i>=1; i--) mp[i] = max(mp[i], mp[i+1]);

    for(i=1; i<n; i++) {
        //iau secventa [1, i] si pun in urma ei maximul dintre secventele care se termina pe n
        //adica chiar mp[i+1]

        sol = max(sol, sum[i] + mp[i+1]);
    }

    g<<sol<<"\n1\n1\n";

    return 0;
}