TopCoder

abcabcabc
有人要寫 p6 嗎 > <

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

81.8% (9/11)

Tags

Description

巴已己最近當上了 IOIC 總召,並開始了忙碌的準備作業。他一共有 $N$ 個工作要做,其中第 $i$ 個工作有 $a_i$ 的消耗值與 $b_i$ 的喜好值。一開始巴已己的疲勞值為 0,由於巴已己是一個工作狂熱者,在他疲勞的時候做工作可以獲得更高的滿足感,具體來說,當他在疲勞值為 $x$ 時做了第 $i$ 個工作時,他會獲得 $x \times b_i$ 的滿足度,接著他的疲勞值會增加 $a_i$。請注意每個工作只能做一次。

雖然巴已己很喜歡身體疲勞的感覺,但是他的體力還是有上限,今天他最多只能做 $N - 1$ 個工作,身為 IOIC 的優秀學員,你能幫幫巴已己找到最好的那 $N-1$ 個工作,並為他安排進行這些工作的順序使得巴已己最後的滿足度越高越好嗎?

以下為提供的解法,請構造出一筆滿足題目條件的測資讓該程式碼 WA。

Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector <int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    vector <int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return a[i] * b[j] > b[i] * a[j];
    });

    vector <long long> pre(n + 1), suf(n + 1);
    vector <long long> sa(n + 1), sb(n + 1);
    for (int i = 0; i < n; ++i) {
        int id = ord[i];
        pre[i + 1] = pre[i] + sa[i] * b[id];
        sa[i + 1] = sa[i] + a[id];
    }
    for (int i = n - 1; ~i; --i) {
        int id = ord[i];
        suf[i] = suf[i + 1] + sb[i + 1] * a[id];
        sb[i] = sb[i + 1] + b[id];
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, pre[i] + suf[i + 1] + sa[i] * sb[i + 1]);
    }

    cout << ans << '\n';
}

Input Format

輸入第一行有一個正整數 $N$。

接下來 $N$ 行,第 $i$ 行會有兩個整數 $a_i, b_i$。

  • $1 \leq N \leq 10^ 5$
  • $0 \leq a_i, b_i \leq 10^ 4$

Output Format

輸出一個整數,代表巴已己的滿足度的最大值。

Sample Input 1

3
1 2
3 4
5 6

Sample Output 1

20

Hints

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料:

#include <stdio.h>
int main() {
    puts("3");
    puts("1 2");
    puts("3 4");
    puts("5 6");
}

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1