Pagini recente » Cod sursa (job #615153) | Cod sursa (job #2290410) | Cod sursa (job #1672575) | Cod sursa (job #2350774) | Cod sursa (job #742041)
Cod sursa(job #742041)
// http://infoarena.ro/problema/buline
#include <stdio.h>
#include <malloc.h>
int main(int argc, char* argv[])
{
long N;
int *v, *dp, maxx, p = 0, pp = 0, i, j;
FILE *f = fopen("buline.in", "r");
fscanf(f, "%d", &N);
v = (int*)malloc(N * sizeof(int));
dp = (int*)malloc(N * 2 * sizeof(int));
int semn;
for (i = 0; i < N; ++i)
{
fscanf(f, "%d %d", &v[i], &semn);
if(semn == 0) v[i] *= -1;
}
dp[0] = maxx = v[0];
fclose(f);
for (i = 0; i < N * 2; ++i)
{
j = i < N ? i : i - N;
if(dp[i-1] > 0) {
dp[i] = dp[i-1] + v[j];
if(maxx < dp[i] && i < pp + N) {
maxx = dp[i];
p = i;
}
}
else {
dp[i] = v[j];
if(maxx < dp[i]) {
maxx = dp[i];
p = i;
}
pp = i;
}
}
f = fopen("buline.out", "w");
fprintf(f, "%d %d %d", maxx, pp + 1, p - pp + 1);
fclose(f);
return 0;
}