[EOJ Monthly 2018.4] E. 小迷妹在哪儿

[EOJ Monthly 2018.4] E. 小迷妹在哪儿

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

ultmaster 男神和小迷妹们玩起了捉迷藏的游戏。

小迷妹们都希望自己被 ultmaster 男神发现，因此她们都把自己位置告诉了 ultmaster 男神，因此 ultmaster 男神知道了自己去找每个小迷妹所要花的时间。

已知发现第 i 小迷妹得到的分数为 ai⋅tr（tr 为游戏剩余时间）。ultmaster 想知道他最多能拿多少分。

Input

第一行两个整数 n,T (1≤n≤105,1≤T≤300) 分别表示小迷妹数量，游戏总时间。

接下去 n 行，每行两个整数 ai,ti (1≤ai≤100,1≤ti≤300) 分别表示发现小迷妹的分数以及 ultmaster 男神发现小迷妹所需时间。

Output

一个整数，表示 ultmaster 在游戏中最多拿多少分。

Examples

2 10
2 5
1 6

10

3 5
5 4
1 1
10 6

5

Note

样例一：找到小迷妹一，找到后得分 2×(10−5)=10 分。
样例二：找到小迷妹一，找到后得分 5×(5−4)=5 分，之后再找到小迷妹二得分也是 0，所以最高得分 5 分。

题解：尽可能先找到性价比高的小迷妹，所以按性价比排个序，然后就是个裸的背包。
证明：交换任意两个小迷妹的顺序可以列不等式证明性价比高的先找更优。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;const int maxn = 1e5+7;int n, T;typedef struct node {int a, t;
};node m[maxn];bool cmp(node a, node b) {return a.a*1.0/a.t > b.a*1.0/b.t;
}
ll dp[maxn];int main()
{ll maxl = 0;scanf("%d%d",&n, &T);memset(dp, 0, sizeof(dp));for(int i = 0; i < n; i++) scanf("%d%d", &m[i].a, &m[i].t);sort(m, m+n, cmp);for(int i = 0; i < n; i++)for(int j = T; j >= m[i].t; j--){dp[j] = max(dp[j], (dp[j - m[i].t] + (m[i].a*(T - j))));maxl = max(maxl, dp[j]);}printf("%lldn", maxl);return 0;
}