Poj 3262 Protecting the Flowers

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct P {
  int t, d;
};

// Greedy approach to minimize cost
// cost = 2 * T * (total - D)
// Therefore, larger D and smaller T are better
// Key insight: convert to D / T ratio - larger is better
bool cmp(const P &a, const P &b) {
  return b.d * a.t < a.d * b.t;
}

vector<P> v;

int N;

int main() {
  scanf("%d", &N);
  int i, total;
  total = 0;
  for(i=0;i<N;++i) {
    struct P p;
    scanf("%d %d", &p.t, &p.d);
    v.push_back(p);
    total += p.d;
  }

  sort(v.begin(), v.end(), cmp);  
  unsigned long long res = 0;
  for(i=0;i<N;++i) {
    total -= v[i].d;
    res += total * v[i].t * 2;
  }

  cout << res << endl;
  return 0;
}