Cod sursa(job #1413216)

Utilizator hrazvanHarsan Razvan hrazvan Data 1 aprilie 2015 18:55:44
Problema Buline Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#define MAXN 200000
int v[2 * MAXN];

int main(){
  FILE *in = fopen("buline.in", "r");
  int n, i, x, y;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d", &x, &y);
    if(y == 0)
      y = -1;
    v[i] = x * y;
  }
  fclose(in);
  for(i = 0; i < n; i++)
    v[i + n] = v[i];
  int st, dr, stc = 0;
  long long smax = 0, sc = -1;
  for(i = 0; i < 2 * n; i++){
    if(i - stc + 1 > n){
      sc -= v[stc];
      stc++;
    }
    if(sc < 0){
      sc = 0;
      stc = i;
    }
    sc += v[i];
    if(sc > smax){
      smax = sc;
      st = stc;
      dr = i;
    }
  }
  dr = dr - st + 1;
  st++;
  FILE *out = fopen("buline.out", "w");
  fprintf(out, "%lld %d %d", smax, st, dr);
  fclose(out);
  return 0;
}