Pagini recente » Cod sursa (job #731357) | Cod sursa (job #2287209) | Cod sursa (job #1821582) | Cod sursa (job #878768) | Cod sursa (job #66253)
Cod sursa(job #66253)
#include <assert.h>
#include <stdio.h>
enum { maxn = 30001, maxval = 1001 };
int n, minlen, maxlen;
int up[maxn],
down[maxn];
int upm[maxn]; //up modified
int sum[maxn]; //sum upm[0..i]
int best[maxn]; //best sum upm[?..i]
int ans;
bool possible(int value)
{
int i;
//avoiding fp numbers
for(i = 0; i < n; i++)
{
upm[i] = up[i] * 100 - value * down[i];
printf("upm[%d] %d\n", i, upm[i]);
}
printf("\n");
sum[0] = upm[0];
best[0] = upm[0];
for(i = 1; i < n; i++)
{
sum[i] = upm[i] + sum[i - 1];
best[i] = upm[i];
if(best[i - 1] + upm[i] > best[i])
best[i] = best[i - 1] + upm[i];
}
for(i = 0; i < n; i++)
printf("sum[%d] %d\n", i, sum[i]);
printf("\n");
for(i = 0; i < n; i++)
printf("best[%d] %d\n", i, best[i]);
printf("\n");
if(best[minlen - 1] > 0)
return true;
//FIXME: what to do with maxlen?
for(i = minlen; i < n; i++)
{
if(sum[i] - sum[i - minlen] >= 0)
return true;
if(sum[i] - sum[i - minlen] + best[i - minlen] >= 0)
return true;
}
return false;
}
void go()
{
int bottom = 0, top = maxval * 100, mid;
//bottom can't be reached, top can.
while(true)
{
mid = (bottom + top + 1) / 2;
bool ans = possible(mid);
printf("bottom %d top %d mid %d possible %d\n",
bottom, top, mid, ans);
if(mid == top) break;
if(ans) //maybe this one, maybe a bigger one
bottom = mid;
else //surely a smaller one
top = mid - 1;
}
ans = mid;
}
int main()
{
int i;
FILE *f = fopen("secv3.in", "r");
if(!f) return 1;
fscanf(f, "%d%d%d", &n, &minlen, &maxlen);
for(i = 0; i < n; i++)
fscanf(f, "%d", &up[i]);
for(i = 0; i < n; i++)
fscanf(f, "%d", &down[i]);
fclose(f);
f = fopen("secv3.out", "w");
if(!f) return 1;
go();
fprintf(f, "%d.%02d\n", ans / 100, ans % 100);
fclose(f);
return 0;
}