Submission #1007302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007302		NeroZein	Closing Time (IOI23_closing)	C++17	9 / 100	1050 ms	480936 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std; 

const int N = 3003;
const long long INF = 1e18 + 18; 

using pli = pair<long long, int>; 

int n, x, y;
long long k; 
long long dist[2][N];
long long dp[N][N * 2][6]; 
vector<pair<int, int>> g[N];
 
void dijkstra(int ver, int src) {
  for (int i = 0; i < n; ++i) {
    dist[ver][i] = INF;
  }
  dist[ver][src] = 0;
  priority_queue<pli, vector<pli>, greater<pli>> pq; 
  pq.emplace(0, src); 
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    if (c != dist[ver][v]) {
      continue; 
    }
    for (auto [u, w] : g[v]) {
      if (c + w < dist[ver][u]) {
        dist[ver][u] = c + w; 
        pq.emplace(dist[ver][u], u); 
      }
    }
  }
}

void init() {
  for (int i = 0; i < n; ++i) {
    g[i].clear();
  }
}

int max_score(int N_, int X_, int Y_, long long K_, vector<int> U, vector<int> V, vector<int> W) {
  n = N_, x = X_, y = Y_, k = K_; 
  for (int i = 0; i < n - 1; ++i) {
    g[U[i]].emplace_back(V[i], W[i]);
    g[V[i]].emplace_back(U[i], W[i]);
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n * 2; ++j) {
      for (int l = 0; l < 6; ++l) {
        dp[i][j][l] = INF;
      }
    }
  }
  dijkstra(0, x);
  dijkstra(1, y);
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return min(dist[0][i], dist[1][i]) < min(dist[0][j], dist[1][j]);
  });
  int tmp = 0, sum = 0; 
  for (int i = 0; i < n; ++i) {
    if (sum + min(dist[0][ord[i]], dist[1][ord[i]]) <= k) {
      sum += min(dist[0][ord[i]], dist[1][ord[i]]);
      tmp++; 
    }
  }
  dp[0][0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int curans = 0; curans < n * 2; ++curans) {
      for (int f = 0; f < 5; ++f) {//0 nothing, 1 x, 2 xy, 3 y, 4 nothing
        dp[i][curans][f + 1] = min(dp[i][curans][f + 1], dp[i][curans][f]);
        if (i == x && f != 1 && f != 2) continue;
        if (i == y && f != 2 && f != 3) continue; 
        if (f == 2) {
          dp[i + 1][curans + 2][f] = min(dp[i + 1][curans + 2][f], dp[i][curans][f] + max(dist[0][i], dist[1][i]));
        } else if (f == 0 || f == 4) {
          dp[i + 1][curans][f] = min(dp[i + 1][curans][f], dp[i][curans][f]);
        } else {
          dp[i + 1][curans + 1][f] = min(dp[i + 1][curans + 1][f], dp[i][curans][f] + dist[f / 2][i]);
        }
      }
    }
  }
  int ans = 0; 
  for (int curans = 0; curans <= 2 * n; ++curans) {
    for (int j = 0; j <= 4; ++j) {
      if (dp[n][curans][j] <= k) {
        ans = max(ans, curans);
      }      
    }
  }
  ans = max(ans, tmp); 
  init();
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17