#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int n, x, y, ch[202020], ans;
ll k, lt[202020], rt[202020], d[202020];
vector<pll> adj[202020];
priority_queue<pll> pq;
int greedy(int s1, int s2) {
int ret = 0;
if (0 <= s1 && s1 < n) pq.push({-0, s1});
if (0 <= s2 && s2 < n) pq.push({-0, s2});
while (!pq.empty()) {
int v = pq.top().second; ll w = -pq.top().first;
pq.pop();
//cout << v << " " << w << "\n";
if (k - w >= 0) {
ret++;
k -= w;
}
else break;
ch[v] = 1;
for (int i = 0; i < (int)adj[v].size(); i++) {
if (ch[adj[v][i].first] == 1) continue;
pq.push({-w-adj[v][i].second, adj[v][i].first});
}
}
return ret;
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
n = N, x = X, y = Y, k = K;
ans = 0;
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < (int)U.size(); i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
d[max(U[i], V[i])] = W[i];
}
for (int a = 0; a < n - x; a++) {
for (int b = 0; b <= y; b++) {
for (int i = 0; i < n; i++) lt[i] = rt[i] = 0;
k = K;
for (int i = x + 1; i <= x + a; i++) lt[i] = max(lt[i], lt[i - 1] + d[i]);
for (int i = y - 1; i >= y - b; i--) rt[i] = max(rt[i], rt[i + 1] + d[i + 1]);
for (int i = x; i <= y; i++) k -= max(lt[i], rt[i]);
if (k < 0) continue;
for (int i = 0; i < n; i++) ch[i] = 0;
ch[x + 1] = ch[y - 1] = 1;
while (!pq.empty()) pq.pop();
ans = max(ans, a + b + greedy(x, y));
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1067 ms |
25528 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '6', found: '9' |
2 |
Halted |
0 ms |
0 KB |
- |