Cod sursa(job #921853)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 21 martie 2013 17:58:28
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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]
    }
	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;
}