# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1037831 |
2024-07-29T08:59:33 Z |
fv3 |
Closing Time (IOI23_closing) |
C++17 |
|
1000 ms |
10440 KB |
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1ll << 60ll;
int max_score(int N, int X, int Y, ll K,
vector<int> U, vector<int> V, vector<int> W)
{
// Subtask 4:
// Find optimal distance X should move to the right
// O(N²)
int best = 0;
for (int r = X; r < N; r++)
{
vector<ll> closingTime(N);
int res = 0;
ll k_sum = 0;
for (int i = X + 1; i <= r; i++)
{
closingTime[i] = closingTime[i-1] + W[i-1];
k_sum += closingTime[i];
res++;
}
if (k_sum > K)
break;
for (int l = Y; l >= 0; l--)
{
int score = res;
ll sum = k_sum;
vector<ll> ct = closingTime;
best = max(best, res);
vector<ll> dist(N);
for (int i = Y - 1; i >= l; i--)
{
dist[i] = dist[i+1] + W[i];
sum += max(0ll, dist[i] - ct[i]);
ct[i] = max(ct[i], dist[i+1] + W[i]);
score++;
}
if (sum > K)
break;
priority_queue<pair<ll, int>> q;
q.push({0, X});
q.push({0, Y});
dist[X] = 0;
dist[Y] = 0;
while (!q.empty())
{
int s = q.top().second;
if (sum - q.top().first > K)
break;
sum -= q.top().first;
score++;
q.pop();
if (s <= X && s)
{
// Go left as X
dist[s-1] = dist[s] + W[s-1];
q.push({-max(0ll, dist[s-1] - ct[s-1]), s-1});
}
else if (s >= Y && s < N - 1)
{
// Go right as Y
dist[s+1] = dist[s] + W[s];
q.push({-max(0ll, dist[s+1] - ct[s+1]), s+1});
}
}
//cerr << ": " << r << " " << l << " = " << score << " (" << sum << ")\n";
best = max(best, score);
}
}
return best;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1059 ms |
10440 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
600 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
4 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
212 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
452 ms |
440 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
30 ms |
348 KB |
Output is correct |
24 |
Correct |
28 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
600 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
4 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
212 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
452 ms |
440 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
30 ms |
348 KB |
Output is correct |
24 |
Correct |
28 ms |
348 KB |
Output is correct |
25 |
Correct |
31 ms |
348 KB |
Output is correct |
26 |
Execution timed out |
1075 ms |
604 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
2 |
Halted |
0 ms |
0 KB |
- |