Cod sursa(job #2543941)

Utilizator memecoinMeme Coin memecoin Data 11 februarie 2020 17:33:01
Problema Bilute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "bilute";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

#define MAXN 30003

int64_t n;
int64_t a[MAXN];
int64_t l[MAXN];

int64_t wSum[MAXN];

int main() {
    
    fin >> n;
    
    int s = 0;
    
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];
        fin >> l[i];
        s += l[i];
    }
    
    int64_t best = INF * 100;
    int64_t bestI = 0;
    
    int64_t vSum = 0;
    
    int64_t runningTopSum = 0;
    int64_t runningBottomSum = 0;
    
    for (int64_t i = 1; i <= n; ++i) {
        vSum += a[i] * l[i];
        wSum[i] = wSum[i - 1] + a[i];
        runningTopSum += a[i] * i;
    }
    
    for (int64_t i = 1; i <= n; ++i) {
        int64_t candidate = vSum - (a[i] * l[i]);
        
        runningTopSum -= wSum[n] - wSum[i - 1];
        
        candidate += runningTopSum;
        candidate += runningBottomSum;
        
        if (candidate < best) {
            bestI = i;
            best = candidate;
        }
        
        runningBottomSum += wSum[i];
    }
    
    fout << bestI << " " << best;
    
    return 0;
}