Cod sursa(job #2552229)

Utilizator dariusandreicotaeCotae Darius Andrei dariusandreicotae Data 20 februarie 2020 18:06:00
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>
#define maxn 40000
//#define INF 2000000001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)

long long INF = 1e9;
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], q[maxn];

FILE *fin = fopen("secv3.in", "rt"), *fout = fopen("secv3.out", "wt");
void addq(int pos)
{
    if (!dr)
        q[++dr] = pos, st = 1;
    else
    {
	   	if (sump[pos] > sump[q[st]])
          q[++dr] = pos;
      	else
        {
        	while (sump[pos] < sump[q[dr]] && dr >= st) dr--;
		    q[++dr] = pos;
		}
	}
	while (pos - q[st] + 1 > U - L + 1) st++;
	if (smax < sump[pos + L] - sump[q[st]])
	{
	    smax = sump[pos + L] - sump[q[st]];
	//	fprintf(fout, "sum:%lld %lld %lld\n", smax, q[st] + 1, pos + L);
	}

}

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, 1, N - L)
		addq(i);
	FOR(i, 1, N - U)
		if (sump[i + U - 1] - sump[i - 1] > smax)
			smax = sump[i + U - 1] - sump[i - 1];
//	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;
}