Pagini recente » Cod sursa (job #1725774) | Cod sursa (job #367706) | Cod sursa (job #3275181) | Cod sursa (job #1402388) | Cod sursa (job #742072)
Cod sursa(job #742072)
// http://infoarena.ro/problema/buline
#include <stdio.h>
#include <malloc.h>
int main(int argc, char* argv[])
{
long N, i, j, k, sum, l = 0, p = 0, len = 1;
int *v, *dp;
FILE *f = fopen("buline.in", "r");
fscanf(f, "%d", &N);
v = (int*)malloc(N * 2 * 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;
v[i+N] = v[i];
}
sum = dp[0] = v[0];
fclose(f);
for (i = 1; i < 2 * N; ++i)
{
if (len < N)
{
if(dp[i-1] > 0) {
dp[i] = dp[i-1] + v[i];
++len;
if(sum < dp[i]) {
sum = dp[i];
p = i;
l = len;
}
}
else
{
dp[i] = v[i];
len = 1;
if(sum < dp[i]) {
sum = dp[i];
p = i;
l = len;
}
}
}
else
{
if (dp[i-1] - dp[i-len] > 0)
{
dp[i] = dp[i-1] - dp[i-len] + v[i];
if(sum < dp[i]) {
sum = dp[i];
p = i;
l = len;
}
}
else
{
dp[i] = v[i];
len = 1;
if(sum < dp[i]) {
sum = dp[i];
p = i;
l = len;
}
}
}
}
f = fopen("buline.out", "w");
fprintf(f, "%d %d %d", sum, p - l + 2, l);
fclose(f);
return 0;
}