Cod sursa(job #124057)

Utilizator info_arrandrei gigea info_arr Data 17 ianuarie 2008 23:07:30
Problema Bilute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <cmath>
#include <fstream>

using namespace std;

#define FIN "bilute.in"
#define FOUT "bilute.out"
#define MAX_N 30005
#define INF 2000000000

int C[MAX_N];
int L[MAX_N];
int h[MAX_N];
int N, i;

long long V[MAX_N];
long long S[MAX_N];
long long BEST;

    void preproc ()
    {
         int i;
         for (i = 1; i <= N; ++i)
             h[i] = h[i - 1] + C[i];
         
         for (i = 1; i <= N; ++i)
             V[i] = V[i - 1] + (long long)C[i]*L[i];
         for (i = 2; i <= N; ++i)
             S[1] += (long long) C[i]*(i - 1);
         for (i = 2; i <= N; ++i)
             S[i] = (long long)S[i - 1] - (h[N] - h[i - 1]) + h[i - 1];
    } 
    
    void solve ()
    {
         int i, sol;
         BEST = INF;
         for (i = 1; i <= N; ++i)
             if ((long long)S[i] + V[i - 1] + (V[N] - V[i]) < (long long)BEST)
             {
                BEST = (long long)S[i] + V[i - 1] + (V[N] - V[i]);
                sol = i;
             }
         printf ("%d %lld", (int)sol, (long long)BEST);
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d", &N);
        for (i = 1; i <= N; ++i)
            scanf ("%d %d", C + i, L + i);
        
        preproc ();
        solve ();
        
        return 0;
    }