Pagini recente » Cod sursa (job #2214964) | Istoria paginii utilizator/pestcontrol210 | Istoria paginii problema/cheerleader | Cod sursa (job #141818) | Cod sursa (job #2543940)
#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;
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;
}