답안 #697614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697614	2023-02-10T15:06:11 Z	peijar	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	1101 ms	340 KB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 501;
const double INF = 1e18;

double dp[2][MAXN];

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbEtats, nbVoulus;
  cin >> nbEtats >> nbVoulus;

  vector<pair<int, int>> etats(nbEtats);
  int cnt = 0;
  for (auto &[b, a] : etats) {
    cin >> a >> b;
    if (b == -1)
      b = INF;
    else
      cnt++;
  }
  sort(etats.begin(), etats.end());

  double sol = INF;

  for (int c = 0; c <= cnt and c <= nbVoulus; ++c) {
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < MAXN; ++j)
        dp[i][j] = INF;

    dp[0][0] = 0;
    double s = INF;
    for (int nbVus = 0; nbVus < nbEtats; ++nbVus) {
      int cur = nbVus % 2;
      int nxt = cur ^ 1;
      for (int i = 0; i < MAXN; ++i)
        dp[nxt][i] = INF;
      auto [b, a] = etats[nbVus];
      for (int prisA = 0; prisA <= nbVus; ++prisA) {
        int prisB = nbVus - prisA;
        if (prisB > c)
          continue;
        double v = dp[cur][prisA];
        if (prisB == c) {
          vector<int> restants;
          for (int i = nbVus; i < nbEtats; ++i)
            restants.push_back(etats[i].second);
          sort(restants.begin(), restants.end());
          for (int i = 0; i < nbVoulus - nbVus; ++i)
            v += restants[i] / (double)(c + 1);
          s = min(s, v);
        } else {
          // on prend en A
          dp[nxt][prisA + 1] = min(dp[nxt][prisA + 1], v + a / (double)(c + 1));
          // on prend en b
          dp[nxt][prisA] = min(dp[nxt][prisA], v + b / (double)(prisB + 1));
        }
      }
    }
    sol = min(sol, s);
  }

  cout << setprecision(15) << fixed << sol << endl;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	324 KB	Output is correct
10	Correct	2 ms	324 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	324 KB	Output is correct
10	Correct	2 ms	324 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	198 ms	340 KB	Output is correct
13	Correct	296 ms	328 KB	Output is correct
14	Correct	172 ms	340 KB	Output is correct
15	Correct	386 ms	328 KB	Output is correct
16	Correct	459 ms	340 KB	Output is correct
17	Correct	195 ms	340 KB	Output is correct
18	Correct	526 ms	340 KB	Output is correct
19	Correct	522 ms	340 KB	Output is correct
20	Correct	205 ms	340 KB	Output is correct

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	280 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	324 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Incorrect	1 ms	212 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	280 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	324 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Incorrect	1 ms	212 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	280 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	324 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Incorrect	1 ms	212 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1101 ms	340 KB	Output is correct
2	Correct	1068 ms	340 KB	Output is correct
3	Correct	1036 ms	340 KB	Output is correct
4	Incorrect	1034 ms	324 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	324 KB	Output is correct
10	Correct	2 ms	324 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	198 ms	340 KB	Output is correct
13	Correct	296 ms	328 KB	Output is correct
14	Correct	172 ms	340 KB	Output is correct
15	Correct	386 ms	328 KB	Output is correct
16	Correct	459 ms	340 KB	Output is correct
17	Correct	195 ms	340 KB	Output is correct
18	Correct	526 ms	340 KB	Output is correct
19	Correct	522 ms	340 KB	Output is correct
20	Correct	205 ms	340 KB	Output is correct
21	Correct	1 ms	320 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	320 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	280 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	324 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Incorrect	1 ms	212 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #697614

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 11.0

Subtask #4 0 / 12.0

Subtask #5 0 / 33.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 11.0

Subtask #4
0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0