Cod sursa(job #2023112)

Utilizator cella.florescuCella Florescu cella.florescu Data 18 septembrie 2017 11:43:43
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e4;

long long st[MAXN + 2], dr[MAXN + 2];
pair <int, int> v[MAXN + 1];

int main()
{
    int n, sum = 0;
    ifstream fin("bilute.in");
    fin >> n;
    int nr = 0;
    for (int i = 1; i <= n; ++i) {
      fin >> v[i].first >> v[i].second;
      sum += v[i].first * v[i].second;
      st[i] = st[i - 1] + nr;
      nr += v[i].first;
    }
    fin.close();
    nr = 0;
    for (int i = n; i > 0; --i) {
      dr[i] = dr[i + 1] + nr;
      nr += v[i].first;
    }
    long long ans = LLONG_MAX;
    int ind = 0;
    for (int i = 1; i <= n; ++i)
      if (ans > sum - v[i].first * v[i].second + st[i] + dr[i]) {
        ans = sum - v[i].first * v[i].second + st[i] + dr[i];
        ind = i;
      }
    ofstream fout("bilute.out");
    fout << ind << " " << ans;
    fout.close();
    return 0;
}