Cod sursa(job #173900)

Utilizator varuvasiTofan Vasile varuvasi Data 8 aprilie 2008 11:49:49
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
 #include <stdio.h>  
 #define maxn 40000  
 //#define INF 2000000001  
 #define FOR(i, a, b) for (i = (a); i <= (b); i++)  
   
 long long INF = 1e12;  
 long long N, L, U;  
 long long kmax = 0, smax, sum, st, dr;  
 long long c[maxn], t[maxn], best[maxn], sump[maxn], b[maxn], coada[maxn];  
   
 FILE *fin = fopen("secv3.in", "rt"), *fout = fopen("secv3.out", "wt");  
 void addq(int pos)  
 {  
     if (pos == L + 1)   
         coada[++dr] = pos, sum = b[pos];  
     else  
     {  
         sum += b[pos];  
         coada[++dr] = pos;  
         while (pos - coada[st] > U - L - 1)  
             sum -= b[coada[st]], st++;  
         while (sum < 0 && st <= dr)  
		 {
             sum -= b[coada[st]], st++;  
				if (st < dr)
				{
				 if (smax < sum + sump[coada[st] - 1] - sump[coada[st] - L - 1])
					 smax = sum + sump[coada[st] - 1] - sump[coada[st] - L - 1];
//				 fprintf(fout, "%lld %lld %lld\n", st, coada[st], coada[st] - L - 1);
				}
		 }
     }  
     if (smax < sump[pos] - sump[pos - L])  
         smax = sump[pos] - sump[pos - L];  
     if (sum == 0) coada[st] = pos;  
     if (L < U && smax < sum + sump[coada[st] - 1] - sump[coada[st] - L - 1])  
         smax = sum + sump[coada[st] - 1] - sump[coada[st] - L - 1];  
 // fprintf(fout, "sum:%lld %lld %lld\n", sum, coada[st], st);  
 }  
   
 int proc(long long k)  
 {  
     int i;  
 // fprintf(fout, "%lld\n", k);  
     FOR(i, 1, N) b[i] = c[i] - k*t[i];  
     FOR(i, 1, N) sump[i] = sump[i - 1] + b[i];  
/*  FOR(i, 1, N) 
         fprintf(fout, "%lld ", b[i]); 
     fprintf(fout, "\n"); 
     FOR(i, 1, N) 
         fprintf(fout, "%lld ", sump[i]); 
     fprintf(fout, "\n");  */
     smax = sump[L], sum = 0, st = 1, dr = 0;  
     FOR(i, L + 1, N)   
         addq(i);  
//  fprintf(fout, "%lld\n", smax);  
     if (smax >= 0) return 1;  
     else          return 0;  
 }  
   
 void cbin()  
 {  
     long long lf = 0, rt = INF, mij = 0;  
     while (lf <= rt)  
     {  
         mij = (lf + rt) >> 1;  
  //    fprintf(fout, "%lld\n", mij);  
         if (proc(mij))   
         {  
             lf = mij + 1;  
             kmax = mij;  
         }  
         else   
             rt = mij - 1;  
    //  fprintf(fout, "%lld %lld\n", lf, rt);  
     }  
 }  
   
 int main()  
 {  
     int i;  
     fscanf(fin, "%lld %lld %lld", &N, &L, &U);  
     FOR(i, 1, N)  
         fscanf(fin, "%lld", &c[i]), c[i] *= 100;  
     FOR(i, 1, N)  
         fscanf(fin, "%lld", &t[i]);  
  /* FOR(i, 1, N) 
         fprintf(fout, "%lld %lld\n", c[i], t[i]);  */
     cbin();  
     fprintf(fout, "%.2f", (double)kmax/100.0);  
     fclose(fin), fclose(fout);  
     return 0;  
}