Cod sursa(job #2049205)

Utilizator herbertoHerbert Mohanu herberto Data 26 octombrie 2017 22:48:00
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include<stdio.h>
#include<stdlib.h>
#include<deque>
using namespace std;
#define MAXN 30001

deque <int> d;
deque <int> poz;

int c[MAXN], t[MAXN], b[MAXN];
int main(){
  FILE*fin=fopen("secv3.in", "r");
  FILE*fout=fopen("secv3.out", "w");
  int n, a, l, u, i, ok, p1, p2, s1, s2, intreg, rest;
  int max, s, st, dr, ans, x;
  fscanf(fin, "%d%d%d", &n, &l, &u);
  for(i=1; i<=n; i++){
    fscanf(fin, "%d", &c[i]);
    c[i]*=100;
  }
  for(i=1; i<=n; i++){
    fscanf(fin, "%d", &t[i]);
//    t[i]*=100;
  }

  st=1; dr=3000000;
  ans=-23232323;
  ok=1;
  while(st<=dr && ok==1){
    x=(st+dr)/2;
//    if(x==83)
//    printf("\n");
    for(i=1; i<=n; i++){
      b[i]=c[i]-x*t[i];
//      if(x==83)
//      printf("%d ", b[i]);
    }
//    if(x==83)
//    printf("\n");
    s=0;
    max=-999999999;
    for(i=1; i<=n; i++){
      if(!d.empty() && poz.front()<i-u){
        d.pop_front();
        poz.pop_front();
      }
//      printf("%d\n", d.size());
      s=s+b[i];
      while(!d.empty() && s<=d.back()){
        d.pop_back();
        poz.pop_back();
      }
//      if(x==50000000)
//        printf("%d %d", max, s-d.front());
      d.push_back(s);
      poz.push_back(i);
//      printf("%d %d %d %d\n", s, d.front(), poz.front(), i-u);
      if(!d.empty() && s-d.front()>max && i!=poz.front()){
        max=s-d.front();
        p1=poz.front();
        p2=i;

//        printf("DA");
      }
//      if(x==50000000)
//        printf("max%d posmax%d\n", max, s-d.front());
    }
    while(!d.empty()){
      d.pop_front();
      poz.pop_front();
    }
//    if(x==83)
//      printf("\n");
//    printf("%d %d %d %d\n", x, st, dr, max);
    if(max!=-999999999){
      s1=0; s2=0;
      p1++;
      for(i=p1; i<=p2; i++){
        s2+=c[i];
        s1+=t[i];
      }
//      if(x==83)
//      printf("%d %d %d %d %d\n", x, p1, p2, s1, s2);
      if(s2/s1==x){
        ans=x;
        ok=0;
      }
    }
    if(max>0)
      st=x+1;
    if(max<0)
      dr=x-1;


  }
  intreg=ans/100;
  rest=ans%100;
  fprintf(fout, "%d.%d", intreg, rest);
  fclose(fin);
  fclose(fout);
  return 0;
}