Pagini recente » Statistici Balaita Andrei-Stefan (Stefan371) | Cod sursa (job #2761129) | Cod sursa (job #2585046) | Cod sursa (job #794733) | Cod sursa (job #41529)
Cod sursa(job #41529)
#include <cstdio>
const int NMAX = 1 << 19;
const int INF = 0x3f3f3f3f;
int N;
long long S[NMAX], Q[NMAX], mx;
int poz[NMAX];
int str, l;
void read() {
FILE *fin = fopen("buline.in", "rt");
int i, v, t;
fscanf(fin, " %d", &N);
for (i = 1; i <= N; ++i) {
fscanf(fin, " %d %d", &v, &t);
if (t == 0) v = -v;
S[i] = S[i - 1] + v;
}
for (i = 1; i <= N; ++i)
S[N + i] = S[N] + S[i];
fclose(fin);
}
void insert(long long Q[], int &st, int &dr, long long v, int p) {
while (st <= dr && poz[st] + N <= p) ++st;
while (st <= dr && Q[dr] > v) --dr;
++dr;
Q[dr] = v; poz[dr] = p;
}
void solve() {
int i, st, dr;
st = 0; dr = -1;
for (i = 0; i < N; ++i)
insert(Q, st, dr, S[i], i);
mx = - ((long long)INF * INF);
for (i = N; i <= (N << 1); ++i) {
// printf("%lld %d\n", Q[st], poz[st]);
if (mx < S[i] - Q[st])
mx = S[i] - Q[st],
str = poz[st] + 1,
l = i - poz[st];
insert(Q, st, dr, S[i], i);
}
}
void write() {
FILE *fout = fopen("buline.out", "wt");
fprintf(fout, "%lld %d %d\n", mx, str > N ? str - N : str, l);
fclose(fout);
}
int main() {
read();
solve();
write();
return 0;
}