Cod sursa(job #1482506)

Utilizator akaprosAna Kapros akapros Data 7 septembrie 2015 12:56:02
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 30002
using namespace std;
int n, i, j, pos;
long long s[maxN], sc[maxN], S[maxN], sol, sum;
struct shade{
    int c, l;
}v[maxN];
void read(){
    freopen("bilute.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i){
        scanf("%d %d", &v[i].c, &v[i].l);
        s[i] = s[i - 1] + v[i].l * v[i].c - i * v[i].c * 1LL;
        S[i] = S[i - 1] + v[i].l * v[i].c + i * v[i].c * 1LL;
        sc[i] = sc[i - 1] + v[i].c;
    }
}
void solve(){
    sol = S[n];
    for (i = 1; i <= n; ++ i){
        sum = s[i - 1] + sc[i - 1] * i;
        sum += (S[n] - S[i]) - (sc[n] - sc[i]) * i;
        if (sum < sol)
            pos = i,
                  sol = sum;
    }
}
void write(){
    freopen("bilute.out", "w", stdout);
    printf("%d %lld", pos, sol);
}
int main(){
    read();
    solve();
    write();
}