Pagini recente » Cod sursa (job #3131750) | Cod sursa (job #2852891) | Istoria paginii runda/arhiva-vianu | Cod sursa (job #2877798) | Cod sursa (job #921853)
Cod sursa(job #921853)
#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;
}