Cod sursa(job #1438203)

Utilizator DeehoroEjkoliPop Darian DeehoroEjkoli Data 19 mai 2015 12:35:07
Problema Subsecventa de suma maxima Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 6000001

using namespace std;
ifstream f("ssm.in");
ofstream g("ssm.out");

int s[nmax], pivot, mx, ltL, ltR, limitL, limitR;
vector <pair <int, int> > sum;

int main()
{
    int n;
    f >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        f >> x;
        s[i] = s[i-1] + x;
        sum.push_back(make_pair(s[i], i));
    }
    sort (sum.begin(), sum.end());
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum.size() - 1; j++)
            if (sum[j].second < i) {
                pivot = s[i] - sum[j].first;
                ltL = sum[j].second + 1;
                ltR = i;
                break;
            }
        if (mx < pivot) {
            mx = pivot;
            limitL = ltL;
            limitR = ltR;
        }
    }
    g << mx << " " << limitL << " " << limitR;
    return 0;
}