Pagini recente » Cod sursa (job #2498718) | Cod sursa (job #177181) | Cod sursa (job #354853) | Cod sursa (job #2277392) | Cod sursa (job #921471)
Cod sursa(job #921471)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
#define nmax 200005
#define ll long long
#define inf (1<<30)
int n, a[nmax], poz[nmax], dr[nmax];
int Rez, startA, Lung;
void citeste(){
f >> n;
int x;
for(int i=1; i<=n; ++i){
f >> a[i] >> x; if (x == 0) a[i] = -a[i];
}
}
void faSol(int sum, int x, int y){
int lung = y - x + 1; if (lung <= 0) lung += n;// pt circularitate
if (sum > Rez){
Rez = sum; startA = x; Lung = lung;
}else if (sum == Rez){
if (startA > x){
startA = x; Lung = lung;
}else if (startA == x){
if (Lung > lung){
Lung = lung;
}
}
}
}
void bagaSsm(){
Rez = -inf;
int sum =0; int st = 1;
for(int i=1; i<=n; ++i){
if (sum + a[i] >= a[i]){// daca aduce profit
sum = sum + a[i];
}else sum = a[i], st = i;
faSol(sum, st, i);// incepe in st, si se termina la i
}
}
void rezolva(){
// primaadata caut secventa cea mai buna din sir iar apoi pentru fiecare secventa 1..i leg cea mai buna secventa j..n(j > i)
// astfel tratez circularitatea
bagaSsm();
// acum imi precalculez dr[i] = cea mai bun secventa ce se termina pe n din intervalul i...n
int sum = 0;
for(int i=n; i>=1; --i){
sum += a[i];
if (dr[i+1] > sum){
dr[i] = dr[i+1]; poz[i] = poz[i+1];
}else{
dr[i] = sum; poz[i] = i;
}
}
sum = 0;
for(int i=1; i<n; ++i){
sum += a[i]; faSol(sum + dr[i+1], poz[i+1], i);
//cout << sum << " " << i << " " << dr[i+1] << "\n";
}
//cout << Rez << " " << startA << " " << Lung << "\n";
g << Rez << " " << startA << " " << Lung << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}