Cod sursa(job #1997275)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 3 iulie 2017 20:38:36
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>

using namespace std;

ifstream fin ("bilute.in"); ofstream fout ("bilute.out");

const int nmax = 3e4 + 5;
int c[nmax + 1], l[nmax + 1];
long long dr[nmax + 1];

int main() {
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        fin >> c[ i ] >> l[ i ];
    }

    int cate = 0;
    for (int i = n; i > 0; -- i) {
        dr[ i ] = dr[i + 1] + cate + c[i + 1] * (l[i + 1] + 1);
        cate += c[i + 1];
    }

    cate = 0;
    long long st, st1 = 0, ans = (1LL << 60);
    int bst = 0;
    for (int i = 1; i <= n; ++ i) {
        st = st1 + cate + c[i - 1] * (l[i - 1] + 1);
        cate += c[i - 1];

        if (st + dr[ i ] < ans) {
            ans = st + dr[ i ];
            bst = i;
        }

        st1 = st;
    }

    fout << bst << " " << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}