Cod sursa(job #1996665)

Utilizator mihaicivMihai Vlad mihaiciv Data 2 iulie 2017 12:29:23
Problema Bilute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#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;
}