fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define forin(i, a, b) for (int i = a; i <= b; i++)
  3. #define forde(i, a, b) for (int i = a; i >= b; i--)
  4. #define forv(a, b) for (auto& a : b)
  5. #define fi first
  6. #define se second
  7. #define ii pair<int, int>
  8. #define endl "\n"
  9. using namespace std;
  10. const int N = 5010;
  11. int dp[N][N], res, temp[N];
  12. vector<int> ke[N];
  13. int n, s[N];
  14. long long fo = 0;
  15. void dfs(int u, int par) {
  16.   int white = 0;
  17.   if (ke[u].size() == 1) s[u]++;
  18.   forv(v, ke[u]) if (v != par) {
  19.     dfs(v, u);
  20.     s[u] += s[v];
  21.     int tmp = 0;
  22.     forin(j, 1, s[v]) tmp = max(tmp, j + dp[v][j]);
  23.     white += tmp;
  24.   }
  25.   for (int j = 1; j <= s[u]; j++) dp[u][j] = -1e9;
  26.   forv(v, ke[u]) if (v != par) {
  27.     for (int k = s[u]; k > 0; k--) temp[k] = -1e9;
  28.     temp[0] = 0;
  29.     for (int j = 1; j <= s[v]; j++) {
  30.       for (int k = s[u]; k >= j; k--) {
  31.         ++fo;
  32.         temp[k] = max(temp[k], dp[u][k - j] + dp[v][j] + j * (k - j));
  33.       }
  34.     }
  35.     for (int k = 1; k <= s[u]; k++) dp[u][k] = max(dp[u][k], temp[k]);
  36.   }
  37.   dp[u][1] = max(dp[u][1], white);
  38.   for (int j = 1; j <= s[u]; j++) res = max(res, dp[u][j]);
  39. }
  40. void solve() {
  41.   srand(time(NULL));
  42.   // cin >> n;
  43.   n = 5000;
  44.   res = 0;
  45.   forin(i, 2, 2) {
  46.     int x = 1, y = i;
  47.     ke[x].push_back(y);
  48.     ke[y].push_back(x);
  49.   }
  50.   forin(i, 3, 5000) {
  51.     int x = i, y = 2;
  52.     ke[x].push_back(y);
  53.     ke[y].push_back(x);
  54.   }
  55.   // forin(i, 1, n - 1) {
  56.   //   int x, y;
  57.   //   cin >> x >> y;
  58.   //   ke[x].push_back(y);
  59.   //   ke[y].push_back(x);
  60.   // }
  61.   dfs(1, 0);
  62.   cout << res;
  63.   // cerr << fo << endl;
  64.   // fo = 0;
  65.   for (int i = 1; i <= n; i++) ke[i].clear(), s[i] = 0;
  66. }
  67. int main() {
  68. #define task "a"
  69.   cin.tie(0)->sync_with_stdio(0);
  70.   if (fopen("task.inp", "r")) {
  71.     freopen("task.inp", "r", stdin);
  72.     freopen("task.out", "w", stdout);
  73.   }
  74.   if (fopen(task ".inp", "r")) {
  75.     freopen(task ".inp", "r", stdin);
  76.     freopen(task ".out", "w", stdout);
  77.   }
  78.   int t = 10;
  79.   // cin >> t;
  80.   while (t--) {
  81.     solve();
  82.     cout << endl;
  83.   }
  84.   cout << fo;
  85. }
  86.  
Success #stdin #stdout 1.29s 100516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
12492501
12492501
12492501
12492501
12492501
12492501
12492501
12492501
12492501
12492501
374775030
https://ideone.com/6ekWTU
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!