Cod sursa(job #921625)

Utilizator h2g2Ford Prefect h2g2 Data 21 martie 2013 10:05:05
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 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, 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

    //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]

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

    begin = end + 1;
    j = sol;
    while(j > 0) {
        begin--;
        if(begin==0) begin = n;

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



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

    return 0;
}