Submission #936208

#	Time	Username	Problem	Language	Result	Execution time	Memory
936208		weakweakweak	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	1409 ms	20568 KiB

Main

//貪心(排序b，枚舉有i個b，後面就拿k-i個a)想一想發現是假的，然後就想不到了，所以看解了
#include <bits/stdc++.h>
using namespace std;

#define ld long double
#define pii pair<int, int>
#define fs first
#define sc second

int n, k, inf = 1e8, suma[1010][1010];
pii pla[1010];
ld dp[1010][1010] = {0}, infd = 1e15;

int main () {
    for (int i = 0; i <= 1005; i++) for (int j = 0; j <= 1005; j++) suma[i][j] = inf;
    for (int i = 0; i <= 1005; i++) suma[i][0] = 0;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &pla[i].sc, &pla[i].fs);
        if (pla[i].fs == -1) pla[i].fs = inf;
    }
    sort(pla + 1, pla + n + 1);

    //預處理i~n中拿j個a最小的，O(n^2 log n)
    for (int i = 1; i <= n; i++) {
        vector <int> v;
        for (int j = i; j <= n; j++) v.push_back(pla[j].sc);
        sort(v.begin(), v.end());
        int sum = 0;
        for (int j = 0; j < v.size(); j++) sum += v[j], suma[i][j + 1] = sum;
    }

    //要另外枚舉有幾個助手，因為b最小的幾個城市中，如果選擇不講到b，只講到a，那他也該是除"最後的總助手量"而非目前的助手量
    ld ans = suma[1][k];
    for (int bc = 0; bc <= k; bc++) {
        for (int i = 0; i <= 1005; i++) for (int j = 0; j <= 1005; j++) dp[i][j] = infd;
        dp[0][0] = 0;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j <= min(i, bc); j++) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + (ld)pla[i].sc / (bc + 1) );
                if (j and pla[i].fs != inf) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (ld)pla[i].fs / j ); 
                if (j == bc) ans = min(ans, dp[i][j] + (ld)suma[i + 1][k - i] / (bc + 1));
            }
        }
    }

    printf("%.9Lf\n", ans);
return 0;}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int j = 0; j < v.size(); j++) sum += v[j], suma[i][j + 1] = sum;
      |                         ~~^~~~~~~~~~
Main.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%d %d", &pla[i].sc, &pla[i].fs);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23