Pagini recente » Cod sursa (job #1247674) | Cod sursa (job #1569618) | Cod sursa (job #1623156) | Cod sursa (job #2487090) | Cod sursa (job #2554946)
#include <iostream>
#include <fstream>
#include <deque>
std::ifstream f("buline.in");
std::ofstream g("buline.out");
const int NMAX = 400'005;
int n,v[NMAX],op,s[NMAX],maxx,I,J;
std::deque<int>d;
int main(){
f >> n;
/// cautam cea mai mare secventa de maxim n elemente astfel incat suma obtinuta este maxima
/// ca sa gasim cea mai mare suma folosim un deque pe care il updatam astfel incat primul element din deque sa fie suma minima de la 1 la indexul acestuia
/// si distanta dintre I si indexul de pe Deque.front() sa fie mai mic sau egal cu n
/// calculam rezultatul max(rezultat,s[i] - s[d.front()])
/// unde s reprezinta vectorul de suma partiala
for(int i = 1;i <= n;++i){
f >> v[i] >> op;
if(op == 0)
v[i] = -v[i];
v[n + i] = v[i];
}
for(int i = 1;i <= 2 * n;++i)
s[i] = s[i - 1] + v[i];
maxx = -((1LL << 31) - 1);
d.push_back(1);
for(int i = 1;i <= 2 * n;++i){
while(!d.empty() && s[i] <= s[d.back()])
d.pop_back();
d.push_back(i);
if(i - d.front() == n)
d.pop_front();
if(s[i] - s[d.front()] > maxx){
maxx = s[i] - s[d.front()];
I = d.front() + 1;
J = i;
}
}
g << maxx << ' ' << I << ' ' << J - I + 1;
return 0;
}