Pagini recente » Cod sursa (job #7024) | Cod sursa (job #422057) | Cod sursa (job #699998) | Cod sursa (job #2945984) | Cod sursa (job #117767)
Cod sursa(job #117767)
#include <cstdio>
const int maxn = 30001;
FILE *in = fopen("bilute.in","r"), *out = fopen("bilute.out","w");
struct bila
{
int c, l;
};
int n;
bila a[maxn];
void read()
{
fscanf(in, "%d", &n);
for ( int i = 1; i <= n; ++i )
fscanf(in, "%d %d", &a[i].c, &a[i].l);
}
int myabs(int x)
{
return x < 0 ? -x : x;
}
int t[maxn]; // t[i] = timpul minim pt a colora toate 1...i-1 in i;
int lt[maxn]; // lt[i] = suma tuturor a[i].c
int p[maxn]; // p[i] = timpul minim pt a colora toate i+1...n in i;
// raspunsul va fi i pt care t[i] + p[i] e minim ;
int lp[maxn]; // ... numai invers
int main()
{
read();
int min = 1 << 30;
int answ = 0;
for ( int i = 1; i <= n; ++i )
lt[i] = lt[i-1] + a[i].c;
for ( int i = n; i; --i )
lp[i] = lp[i+1] + a[i].c;
for ( int i = 1; i <= n; ++i )
t[i] = t[i-1] + a[i-1].c * a[i-1].l + lt[i-1];
for ( int i = n; i ; --i )
p[i] = p[i+1] + a[i+1].c * a[i+1].l + lp[i+1];
for ( int i = 1; i <= n; ++i )
if ( t[i] + p[i] < min )
min = t[i] + p[i], answ = i;
fprintf(out, "%d %d\n", answ, min);
return 0;
}