Submission #1058309

---

Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

void precalc() {
}

const int maxn = (int) 5e3 + 10;
int n;

int ls[maxn], rs[maxn];

int read() {
  if (scanf("%d", &n) < 1) {
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", ls + i, rs + i);
  }
  return 1;
}

pair<int, int> tosort[maxn];

long long dp[2][maxn];

void solve() {
  for (int i = 0; i < n; ++i) {
    tosort[i] = mp(ls[i] + rs[i], i);
  }
  sort(tosort, tosort + n);
  reverse(tosort, tosort + n);

  dp[0][0] = 0;
  dp[1][0] = (long long) 1e18;

  for (int iter = 0; iter < n; ++iter) {
    dp[0][iter + 1] = dp[1][iter + 1] = (long long) 1e18;
    for (int type = 1; type >= 0; --type) {
      for (int tl = iter; tl >= 0; --tl) {
        auto cur = dp[type][tl];
        dp[type][tl + 1] = min(dp[type][tl + 1], cur + (long long) tl * tosort[iter].first + rs[tosort[iter].second]);
        if (!type && (n & 1)) {
          dp[1][tl] = min(dp[1][tl], cur + (long long) (n - 1) * tosort[iter].first / 2);
        }
        dp[type][tl] = cur + (long long) (iter - tl - type) * tosort[iter].first + ls[tosort[iter].second];
      }
    }
  }
  long long res = *min_element(dp[0], dp[0] + n + 1);
  if (n & 1) {
    res = min(res, dp[1][n / 2]);
  }
  printf("%lld\n", res);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:46:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", ls + i, rs + i);
                                  ^

Judge Result