Kvar_ispw17's blog
0%

NWPU寒假训练题解 I - 贪心算法

Posted on Edited on In

题目链接: https://vjudge.net/contest/418600

A 校门外的树

直接模拟染色的过程即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e4 + 5;
int co[N];
int L, M;

int main() {
	read(L);
	read(M);
	while (M--) {
		int l, r;
		read(l);
		read(r);
		for (int i = l; i <= r; i++) {
			co[i]++;
		}
	}
	int cnt = 0;
	for (int i = 0; i <= L; i++) {
		if (!co[i]) cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

B 铺地毯

从后往前遍历地毯，找到的第一个即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e7 + 5;

class carpet {
  public:
	int id, a, b, x, y;
	carpet(int _id, int _a, int _b, int _x, int _y) {
		id = _id;
		a = _a;
		b = _b;
		x = _x;
		y = _y;
	}
};

vector<carpet> c;

int n;

int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		int a, b, x, y;
		read(a), read(b), read(x), read(y);
		c.push_back(carpet(i, a, b, x, y));
	}
	int X, Y;
	read(X), read(Y);
	vector<carpet>::reverse_iterator it;
	for (it = c.rbegin(); it != c.rend(); it++) {
		carpet o = *it;
		// printf("GET %d %d %d %d\n", o.a, o.b, o.x, o.y);
		if (X >= o.a && X <= o.a + o.x && Y >= o.b && Y <= o.b + o.y) {
			printf("%d\n", o.id);
			return 0;
		}
	}
	puts("-1");
	return 0;
}

C 低买高卖

维护一个小根堆，每一个元素表示前 \(i-1\) 天中可以和当前第 \(i\) 天进行一次购买售出操作的股票。设 \(a[i]\) 表示股票价格，当堆顶小于当前价格时，贪心使用堆顶的股票低买高卖；若堆顶大于当前价格，则把今日的股票插入堆中两次。为什么要放两次？因为实际上在某一天什么都不做，相当于买入一股又立马卖出一股，其不会改变收入，但买入和卖出的股票由于不存在标识，完全可以认为是不同的股票。刚才插入的两股，第一股如果在未来被使用，则可认为其做了一次“中间股票”；第二股则是传统意义上的，该股票在未来的某一天被对应卖出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 200000 + 5;
int a[N], n;

priority_queue<int, vector<int>, greater<int>> p;

int main() {
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]);
	p.push(a[1]);
	int ans = 0;
	for (int i = 2; i <= n; i++) {
		int x = a[i];
		if (x < p.top()) {
			p.push(x);
		} else {
			ans += x - p.top();
			p.pop();
			p.push(x);
			p.push(x);
		}
	}
	printf("%d\n", ans);
	return 0;
}

D IP地址转换

使用位运算模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int main() {
	char c = 0;
	int a = 0;
	while (c != '-') {
		c = getchar();
		if (c == '.') {
			// printf("PRINT a = %d\n", a);
			for (int i = 7; i >= 0; i--) {
				int b = (a >> i) & 1;
				printf("%d", b);
			}
			a = 0;
			continue;
		}
		if (c == '\n') {
			for (int i = 7; i >= 0; i--) {
				int b = (a >> i) & 1;
				printf("%d", b);
			}
			a = 0;
			printf("\n");
			continue;
		}
		a = a * 10 + c - '0';
	}
	return 0;
}

E 明明的随机数

sort()与unique()函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 100 + 5;

int n, a[N];

int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
	}
	sort(a + 1, a + n + 1);
	int m = unique(a + 1, a + n + 1) - (a + 1);
	printf("%d\n", m);
	for (int i = 1; i <= m; i++) {
		printf("%d ", a[i]);
	}
	puts("");
	return 0;
}

F 拼数

观察了一下样例，发现这不就是字典序嘛，果断WA了。后来发现 \(432\) 字典序比 \(43\) 大，但是实际上却应该是 \(43432\) ，把字典序比较换成了 \(a+b\lt b+a\) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

string s[2500];
int n;

bool cmp(string a, string b) {
	return a + b > b + a;
}

int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	sort(s + 1, s + n + 1, cmp);
	for (int i = 1; i < n; i++) {
		string a = s[i];
		string b = s[i + 1];
	}
	for (int i = 1; i <= n; i++) {
		cout << s[i];
	}
	puts("");
	return 0;
}

G 今年暑假不AC

把线段按左端点排序，然后从右往左遍历排好的线段，贪心取不重叠的线段即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

class segment {
  public:
	int l, r;
	segment(int _l = 0, int _r = 0) {
		l = _l, r = _r;
	}
	bool operator < (const segment o) const {
		return l < o.l;
	}
};

int n;
segment a[105];

void init() {
	memset(a, 0, sizeof a);
}

int main() {
	while (scanf("%d", &n)) {
		if (n == 0) break;
		init();
		for (int i = 1; i <= n; i++) {
			int l, r;
			read(l), read(r);
			a[i] = segment(l, r);
		}
		sort(a + 1, a + n + 1);
#ifdef DEBUG
		for (int i = 1; i <= n; i++) {
			printf("[%d, %d]\n", a[i].l, a[i].r);
		}
#endif
		int ans = 1;
		segment x = a[n];
		for (int i = n - 1; i >= 1; i--) {
			if (a[i].r <= x.l) {
				ans++;
				x = a[i];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

H 排座椅

取桌子之间的间隙建立新网格，对行和列贪心取“串”起来最多的即可。(OOP大法好！)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int _N_ = 1000 + 5;
const int _D_ = 2000 + 5;

int a[_N_], b[_N_];
int M, N, K, L, D;

class data {
  public:
	int id, cnt;
	data() {
		id = cnt = -1;
	}
	data(int _id, int _cnt) {
		id = _id, cnt = _cnt;
	}
	bool operator < (const data o) const {
		return cnt > o.cnt;
	}
};

data A[_N_], B[_N_];

int main() {
	r(M), r(N), r(K), r(L), r(D);
	for (int i = 1; i <= D; i++) {
		int x1, y1, x2, y2;
		r(x1), r(y1), r(x2), r(y2);
		if (y1 == y2) {
			int x = min(x1, x2);
			a[x]++;
		}
		if (x1 == x2) {
			int y = min(y1, y2);
			b[y]++;
		}
	}
	int tot_A = 0, tot_B = 0;
	for (int i = 1; i < M; i++) {
		if (a[i]) {
			A[++tot_A] = data(i, a[i]);
		}
	}
	for (int i = 1; i < N; i++) {
		if (b[i]) {
			B[++tot_B] = data(i, b[i]);
		}
	}
	sort(A + 1, A + tot_A + 1);
	sort(B + 1, B + tot_B + 1);
	vector<int> v, _v;
	vector<int>::iterator it;
	for (int i = 1; i <= K; i++) {
		v.push_back(A[i].id);
	}
	sort(v.begin(), v.end());
	for (it = v.begin(); it != v.end(); it++) {
		int x = *it;
		printf("%d ", x);
	}
	puts("");
	for (int i = 1; i <= L; i++) {
		_v.push_back(B[i].id);
	}
	sort(_v.begin(), _v.end());
	for (it = _v.begin(); it != _v.end(); it++) {
		int x = *it;
		printf("%d ", x);
	}
	puts("");
	return 0;
}

I 回文日期

强行手写一个日期类，然后枚举判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

class date {
  public:
	int y, m, d;
	date(string s) {
		int _y = atoi(s.substr(0, 4).c_str());
		int _m = atoi(s.substr(4, 2).c_str());
		int _d = atoi(s.substr(6, 2).c_str());
		y = _y, m = _m, d = _d;
	}
	bool operator == (const date A) const {
		return A.y == y && A.m == m && A.d == d;
	}
	void print() {
		printf("YEAR=%d MONTH=%d DAY=%d\n", y, m, d);
	}
	string sprint() {
		char s[10];
		sprintf(s, "%d%02d%02d\n", y, m, d);
		string str = s;
		return str;
	}
	void update() {
		if (m == 1 ||
		        m == 3 ||
		        m == 5 ||
		        m == 7 ||
		        m == 8 ||
		        m == 10
		   ) {
			if (d == 31) {
				d = 1;
				m++;
			} else {
				d++;
			}
		} else if (m == 12) {
			if (d == 31) {
				d  = 1;
				m = 1;
				y++;
			} else {
				d++;
			}
		} else if (m == 2) {
			if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) {
				if (d == 29) {
					d = 1;
					m++;
				} else {
					d++;
				}
			} else {
				if (d == 28) {
					d = 1;
					m++;
				} else {
					d++;
				}
			}
		} else {
			if (d == 30) {
				d = 1;
				m++;
			} else {
				d++;
			}
		}
	}
};

string A, B;

bool good(string str) {
	// printf("\t---COMPARING");
	int len = 8;
	for (int i = 0; i < len / 2 + 1; i++) {
		int j = len - i - 1;
		// printf(" j = %d   %c <-> %c  \n", j, str[i], str[j]);
		if (str[i] != str[j]) return false;
	}
	return true;
}

int main() {
	cin >> A >> B;
	date a(A), b(B);
	b.update();
	int cnt = 0;
	for (date t = a; !(t == b); t.update()) {
		// printf("NOW AT DATE -> ");
		// cout << t.sprint();
		if (good(t.sprint())) cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

J Claris and XOR

（这题真是要了老命）

贪心从高到低构造 \(1\) ，考虑当前是第 \(i\) 位，若 \(x\) 和 \(y\) 在这一位的取法均为任意，则后面所有位一定都可以任意取，这时直接把答案的后面全取为 \(1\) 。如果两个数在这一位的取法受限，则贪心构造出答案 \(1\) 。如果贪心也不行则只能填上 \(0\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

ll a, b, c, d;
int T;

void print(ll x) {
	for (int i = 63; i >= 0; i--) {
		int p = x >> i & 1;
		printf("%d", p);
	}
}

int main() {
	read(T);
	while (T--) {
		read(a), read(b), read(c), read(d);
		ll ans = 0;
		ll ta, tb, tc, td;
		ta = a;
		tb = b;
		tc = c;
		td = d;
		for (int i = 62; i >= 0; i--) {
			ll t = 1LL << (i + 1);
			ll _t = 1LL << i;
			// printf("i = %d \t_t =\n", i); print(_t); puts(""), puts("---");
			int x0, x1, y0, y1;
			x0 = x1 = y0 = y1 = 0;
			if (ta <= _t - 1) x0 = 1;
			if (tb >= _t) x1 = 1;
			if (tc <= _t - 1) y0 = 1;
			if (td >= _t) y1 = 1;
			// printf("x0=%d  x1=%d  y0=%d  y1=%d\n", x0, x1, y0, y1);
			if (x0 && x1 && y0 && y1) {
				ans += t - 1;
				break;
			}
			if (x0 && y1) {
				ans += _t;
				tc -= _t;
				td -= _t;
				continue;
			}
			if (x1 && y0) {
				ans += _t;
				ta -= _t;
				tb -= _t;
				continue;
			}
			if ((!x0) && (!y0)) {
				ta -= _t;
				tb -= _t;
				tc -= _t;
				td -= _t;
			}
			// print(td), puts("");
			// print(tc), puts("");
			// print(tb), puts("");
			// print(ta), puts("");
			// puts("------------");
		}
		printf("%lld\n", ans);
	}
	return 0;
}

K Flip Game

注意到，翻片儿的顺序不会产生影响，则同一个地方最多翻一次即可，直接进行DFS记忆化搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void r(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int a[5][5];
int G1, G2, st[100000];

void print(int x[][5]) {
	puts("------\nPRINT\n------");
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			printf("%d", x[i][j]);
		}
		puts("");
	}
	puts("------\nEND PRINT\n------");
}

int trans(int x[][5]) {
	int ret = 0;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			ret = (ret << 1) | x[i][j];
		}
	}
	return ret;
}

int g1[5][5], g2[5][5];
bool vis[5][5];

void dfs(int x[][5], int cnt) {
	int sta = trans(x);
	if (st[sta] <= cnt) {
		return;
	}
	st[sta] = cnt;
	// printf("CURRENTLY AT -> cnt = %d\n", cnt);
	// print(x);
	if (sta == G1 || sta == G2) {
		return;
	}
	int t[5][5];
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			t[i][j] = x[i][j];
		}
	}
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			if (!vis[i][j]) {
				t[i][j] ^= 1;
				if (i - 1 >= 1) t[i - 1][j] ^= 1;
				if (i + 1 <= 4) t[i + 1][j] ^= 1;
				if (j - 1 >= 1) t[i][j - 1] ^= 1;
				if (j + 1 <= 4) t[i][j + 1] ^= 1;

				vis[i][j] = true;
				dfs(t, cnt + 1);
				vis[i][j] = false;

				t[i][j] ^= 1;
				if (i - 1 >= 1) t[i - 1][j] ^= 1;
				if (i + 1 <= 4) t[i + 1][j] ^= 1;
				if (j - 1 >= 1) t[i][j - 1] ^= 1;
				if (j + 1 <= 4) t[i][j + 1] ^= 1;
			}
		}
	}
}

int main() {
	memset(st, 0x7f7f7f7f, sizeof st);
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			g1[i][j] = 0;
			g2[i][j] = 1;
		}
	}
	G1 = trans(g1);
	G2 = trans(g2);
	for (int i = 1; i <= 4; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < 4; j++) {
			if (str[j] == 'b') {
				a[i][j + 1] = 1;
			} else {
				a[i][j + 1] = 0;
			}
		}
	}
	// print(a);
	// printf("G1 = %d, G2 = %d\n", G1, G2);
	dfs(a, 0);
	int ans  = min(st[G1], st[G2]);
	if (ans >= 0x7f7f7f7f) puts("Impossible");
	else printf("%d\n", ans);
	return 0;
}

M Unique Snowflakes

滑动窗口型问题，我好像写了一个st表加二分的方法……（离谱）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e6 + 5;
const int logN = 30;
int a[N], lst[N], f[N][logN];
int T, n;

map<int, int> c;

void init() {
	c.clear();
	memset(a, 0, sizeof a);
	memset(lst, 0, sizeof a);
	memset(f, 0, sizeof f);
}

int ask(int L, int R) {
	int k = log2(R - L + 1);
	return max(f[L][k], f[R - (1 << k) + 1][k]);
}

int main() {
	read(T);
	while (T--) {
		init();
		read(n);
		for (int i = 1; i <= n; i++) {
			read(a[i]);
			if (!c[a[i]]) {
				c[a[i]] = i;
			} else {
				lst[i] = c[a[i]];
				c[a[i]] = i;
			}
			f[i][0] = lst[i];
		}
		for (int j = 1; j <= 21; j++) {
			for (int i = 1; i + (1 << j) - 1 <= n; i++) {
				f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
			}
		}
		int ans = -1;
		for (int i = 1; i <= n; i++) {
			int L = i, R = n, mid;
			while (L <= R) {
				mid = (L + R) / 2;
				int mx = ask(i, mid);
				if (mx < i) L = mid + 1;
				else R = mid - 1;
			}
			int tmp = L - i;
			ans = max(ans, tmp);
		}
		printf("%d\n", ans);
	}
	return 0;
}

N Hero

一开始写了一个奇怪的贪心给WA了，实际上直接利用 \(\displaystyle\frac{\text{HP}_i}{\text{DPS}_i}\) 越小越好的贪心就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

#define INF 0x3f3f3f3f

class hero {
  public:
	int HP, DPS;
	hero(int _HP = -1, int _DPS = -1) {
		HP = _HP, DPS = _DPS;
	}
	bool operator < (const hero o) const {
		return HP * o.DPS < DPS * o.HP;
	}
};

hero a[25];
int n;
int sum_HP, sum_DPS;
bool vis[25];

void init() {
	sum_DPS = sum_HP = 0;
	memset(a, -1, sizeof a);
	memset(vis, 0, sizeof vis);
}

int main() {
	while (~scanf("%d", &n)) {
		init();
		int dps, hp;
		for (int i = 1; i <= n; i++) {
			read(dps), read(hp);
			a[i] = hero(hp, dps);
			sum_HP += hp;
			sum_DPS += dps;
		}
		int ans = 0;

#if 1
		sort(a + 1, a + n + 1);
		int ts = 0;
		for (int i = 1; i <= n; i++) {
			ans += a[i].HP * (sum_DPS - ts);
			ts += a[i].DPS;
		}
		printf("%d\n", ans);

#endif

#if 0

		for (int j = 1; j <= n; j++) {
			int good = -1, td = -INF;
			int tmp_s = 0;
			for (int i = 1; i <= n; i++) {
				if (!vis[i]) {
					tmp_s += a[i].DPS;
				}
			}
			for (int i = 1; i <= n; i++) {
				if (!vis[i]) {
					int st = a[i].HP * (tmp_s - a[i].DPS);
					if (st > td) {
						td = st;
						good = i;
					}
				}
			}
			// printf("j = %d  good = %d  td = %d\n", j, good, td);
			vis[good] = true;
			ans += td;
		}
		int oth = sum_HP * sum_DPS;
		ans = oth - ans;
		printf("%d\n", ans);

#endif

	}
	return 0;
}