#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
namespace cardboard {
vector<pair<int, long long>> boxes;
long long K;
bool cmp(pair<int, int> p1, pair<int, int> p2) {
return boxes[p1.second].second - boxes[p1.first].second > boxes[p2.second].second - boxes[p2.first].second;
}
namespace whole {
struct half {
set<int> ids;
set<pair<long long, int>> ones;
set<pair<long long, int>> twos;
long long sum = 0;
int side;
half(int _side): side(_side) {};
void clear() {
ids.clear();
ones.clear();
twos.clear();
sum = 0;
}
void add(int id) {
if (side == 1) {
sum += boxes[id].second;
}
ids.insert(id);
if (boxes[id].first == 1) {
ones.emplace(boxes[id].second, id);
}
else {
twos.emplace(boxes[id].second, id);
}
}
void rem(int id) {
if (side == 1) {
sum -= boxes[id].second;
}
ids.erase(id);
if (boxes[id].first == 1) {
ones.erase({boxes[id].second, id});
}
else {
twos.erase({boxes[id].second, id});
}
}
} left_half(1), right_half(2);
set<int> ids;
void fix() {
left_half.clear();
right_half.clear();
bool flag = false;
for (auto id: ids) {
if (!flag && left_half.sum + boxes[id].second <= K) {
left_half.add(id);
}
else {
flag = true;
right_half.add(id);
}
}
}
void add(int id) {
ids.insert(id);
fix();
}
void rem(int id) {
ids.erase(id);
fix();
}
int get() {
vector<long long> cur_dp = {0};
for (auto id: ids) {
vector<long long> nxt_dp = cur_dp;
nxt_dp.push_back(inf);
for (int j = 0; j < (int)cur_dp.size(); j++) {
nxt_dp[j + boxes[id].first] = min(nxt_dp[j + boxes[id].first], cur_dp[j] + boxes[id].second);
}
cur_dp.swap(nxt_dp);
}
for (int i = (int)ids.size(); i >= 0; i--) {
if (cur_dp[i] <= K) {
return i;
}
}
return 0;
/* int res = left_half.ids.size();
if (!right_half.ones.empty() && left_half.sum + right_half.ones.begin()->first <= K) {
res++;
}
else if (!left_half.ones.empty() && !right_half.twos.empty() && left_half.sum - left_half.ones.rbegin()->first + right_half.twos.begin()->first <= K) {
res++;
}
return res;*/
}
}
int solve(int N, long long _K, vector<pair<long long, long long>> costs) {
K = _K;
vector<pair<long long, int>> order(N << 1);
for (int i = 0; i < N; i++) {
order[i << 1] = {costs[i].first << 1, i << 1};
order[i << 1 | 1] = {costs[i].second, i << 1 | 1};
}
sort(order.begin(), order.end());
vector<pair<int, int>> ids(N);
boxes.resize(N << 1);
for (int i = 0; i < (N << 1); i++) {
if (order[i].second & 1) {
boxes[i] = {2, order[i].first};
ids[order[i].second >> 1].second = i;
}
else {
boxes[i] = {1, order[i].first >> 1};
ids[order[i].second >> 1].first = i;
}
}
sort(ids.begin(), ids.end(), cmp);
for (int i = 0; i < N; i++) {
whole::add(ids[i].second);
}
int res = whole::get();
for (int i = 0; i < N; i++) {
whole::add(ids[i].first);
whole::rem(ids[i].second);
res = max(res, whole::get());
}
return res;
}
}
namespace tree {
vector<vector<pair<int, int>>> adj;
void init(int N) {
adj.resize(N);
for (int i = 0; i < N; i++) {
adj[i].clear();
}
}
void add_edge(int u, int v, int w) {
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
void dfs(int u, int p, vector<long long> &dist) {
for (auto [v, w]: adj[u]) {
if (v != p) {
dist[v] = dist[u] + w;
dfs(v, u, dist);
}
}
}
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
tree::init(N);
for (int i = 0; i < N - 1; i++) {
tree::add_edge(U[i], V[i], W[i]);
}
vector<long long> distX(N), distY(N);
tree::dfs(X, -1, distX);
tree::dfs(Y, -1, distY);
vector<long long> dists(distX.begin(), distX.end());
dists.insert(dists.end(), distY.begin(), distY.end());
sort(dists.begin(), dists.end());
int res = 0;
long long sum = 0;
for (auto d: dists) {
if (sum + d <= K) {
sum += d;
res++;
}
else {
break;
}
}
int cnt = 0;
vector<pair<long long, long long>> costs(N);
for (int i = 0; i < N; i++) {
if (distX[i] + distY[i] == distX[Y]) {
cnt++;
K -= min(distX[i], distY[i]);
costs[i] = {max(distX[i], distY[i]) - min(distX[i], distY[i]), inf};
}
else {
costs[i] = {min(distX[i], distY[i]), max(distX[i], distY[i])};
}
}
if (K >= 0) {
res = max(res, cnt + cardboard::solve(N, K, costs));
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
30796 KB |
Output is correct |
| 2 |
Correct |
130 ms |
35128 KB |
Output is correct |
| 3 |
Correct |
69 ms |
2936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
