Pagini recente » Cod sursa (job #789711) | Cod sursa (job #15668) | Cod sursa (job #2964303) | Cod sursa (job #2758829) | Cod sursa (job #1996665)
#include <iostream>
#include <fstream>
#include <cmath>
#define inf 30000000000000000
#include <cstdlib>
#define nmax 30001
using namespace std;
ifstream f("bilute.in");
ofstream g("bilute.out");
int l[nmax],c[nmax],n;
unsigned long long val[nmax],d[nmax];
void citire()
{
f>>n;
for (int i=1;i<=n;i++)
{
f>>c[i]>>l[i];
}
}
void rezolvaren2()
{
long long int cost=0;
long long int costmaxim=inf;
int pos=0;
for (int i=1;i<=n;i++)
{
cost=0;
for (int j=1;j<=n;j++)
{
if (j!=i)
{
cost=cost+c[j]*l[j]+c[j]*abs(i-j);
}
}
if (cost<costmaxim)
{
costmaxim=cost;
pos=i;
}
}
g<<pos<<" "<<costmaxim;
}
unsigned long long cost(int x)
{
long int suma=0;
for (int i=1;i<=n;i++)
{
if (i!=x)
{
suma+=l[i]*c[i]+abs(x-i)*c[i];
}
}
return suma;
}
void rezolvaren()
{
for (int i=1;i<=n;i++)
{
val[i]=val[i-1]+c[i];
}
d[1]=cost(1);
for (int i=2;i<=n;i++)
{
d[i]=d[i-1]+c[i-1]*l[i-1]-c[i]*l[i]+(val[i-1]-val[n]+val[i-1]);
}
int pos=1;
unsigned long long minim=d[1];
for (int i=2;i<=n;i++)
{
if (minim>d[i])
{
pos=i;
minim=d[i];
}
}
g<<pos<<" "<<d[pos];
}
void rez()
{
if (n<=1000)
{
rezolvaren2();
}
else rezolvaren();
}
int main()
{
citire();
rez();
return 0;
}