Cod sursa(job #921629)

Utilizator harababurelPuscas Sergiu harababurel Data 21 martie 2013 10:09:17
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <fstream>
#define nmax 200005
using namespace std;

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

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] = -v[i];

        ssm[i] = v[i] + max(ssm[i-1], 0);
        if(ssm[i] > sol) {
            sol = ssm[i];
            end = 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 (circulara)
    //ci ii o secventa de forma [j, i], cu 1 <= j <= i <= n

    //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 (aici ma folosesc de maxime partiale)

    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]);

    //mp[i] = cea mai mare suma dintre: sum[i,n], sum[i+1,n], ..., sum[n,n]

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

        if(sum[i] + mp[i+1] > sol) {
            sol = sum[i] + mp[i+1];
            end = i;
        }
    }

    begin = end + 1;
    j = sol;            //iau suma obtinuta si reconstitui drumul, pana ajung la suma 0
    while(j > 0) {
        begin--;
        if(begin==0) begin = n;

        j -= v[begin];
        dim++;
    }

    g<<sol<<" "<<begin<<" "<<dim<<"\n";

    return 0;
}