Pagini recente » Cod sursa (job #2234801) | Cod sursa (job #738802) | Cod sursa (job #424063) | Cod sursa (job #2473265) | Cod sursa (job #921614)
Cod sursa(job #921614)
#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;
}