Submission #1335864

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--) 
#define Rep(i,a) for(int i = 0; i < a; i++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ab(x) ((x) < 0 ? -(x) : (x))
using namespace std;
typedef long long LL;
typedef map<int, int>::iterator mit;
typedef set<int>::iterator sit;
typedef pair<int, int> pii;
#define x first
#define y second
const int N = 5010;
const LL inf = 1LL << 60;
int n, l[N], r[N], id[N];
LL f[N][N], g[2][N];
inline bool cmp(const int &a, const int &b) { return l[a] + r[a] < l[b] + r[b]; }
int main() {
	scanf("%d",&n);
	rep(i,1,n) scanf("%d%d", l + i, r + i), swap(l[i], r[i]);
	rep(i,1,n) id[i] = i; sort(id + 1, id + n + 1, cmp);
	f[0][0] = 0; rep(j,1,n) f[0][j] = inf;
	int cl = n >> 1, cr = n >> 1;
	rep(i,1,n) {
		int x = id[i];
		rep(j,0,i) {
			f[i][j] = inf;
			if (j - 1 >= 0) 
				f[i][j] = min(f[i][j], f[i - 1][j - 1] + l[x] + 1LL * (l[x] + r[x]) * (cl - j));
			f[i][j] = min(f[i][j], f[i - 1][j] + r[x] + 1LL * (l[x] + r[x]) * (cr - (i - j)));
		}
		rep(j,i+1,n) f[i][j] = inf;
	}

	if (!(n & 1)) printf("%lld\n",f[n][n / 2]);
	else {
		LL ans = inf;
		g[(n+1)&1][0] = 0; rep(j,1,n) g[(n+1)&1][j] = inf;
		dep(i,n,1) {
			int x = id[i], cur = i & 1;
			rep(j,0,n - i + 1) {
				g[cur][j] = inf;
				if (j - 1 >= 0) g[cur][j] = min(g[cur][j], g[!cur][j - 1] + l[x] + 1LL * (l[x] + r[x]) * (j - 1));
				else g[cur][j] = min(g[cur][j], g[!cur][j] + r[x] + 1LL * (l[x] + r[x]) * ((n - i + 1) - j - 1));
			}
			rep(j,n-i+2,n) g[cur][j] = inf;
			int t = n >> 1;
			LL tot = 1LL * t * (l[x] + r[x]); 
			rep(j,0,t) ans = min(ans, tot + f[i - 1][j] + g[!cur][t - j]);
		}
		cout <<ans<<endl; 
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:30:58: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,1,n) scanf("%d%d", l + i, r + i), swap(l[i], r[i]);
                                                          ^

Judge Result