| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 626193 |
2022-08-11T09:39:38 Z |
Eae02 |
Catfish Farm (IOI22_fish) |
C++17 |
|
1000 ms |
28676 KB |
#include "fish.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define all(x) begin(x),end(x)
vector<vector<pair<ll, ll>>> fishAtX;
vector<vector<pair<ll, ll>>> fishWeightSum;
ll weightSum(ll x, ll y) {
if (x < 0 || x >= (ll)fishWeightSum.size())
return 0;
ll w = 0;
for (auto [fy, fw] : fishAtX[x])
if (fy <= y)
w += fw;
return w;
//ll idx = lower_bound(all(fishWeightSum[x]), make_pair(y, LLONG_MIN)) - fishWeightSum[x].begin();
//if (fishWeightSum[x][idx].first > y)
// idx--;
//return fishWeightSum[x][idx].second;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
if (M == 0) return 0;
vector<pair<ll, ll>> piers;
vector<tuple<ll, ll, ll>> fish;
for (ll i = 0; i < M; i++) {
fish.emplace_back(X[i], Y[i], W[i]);
if (X[i] != 0)
piers.emplace_back(X[i] - 1, Y[i]);
if (X[i] != N - 1)
piers.emplace_back(X[i] + 1, Y[i]);
}
sort(all(piers));
piers.erase(unique(all(piers)), piers.end());
fishAtX.resize(N);
for (ll i = 0; i < M; i++)
fishAtX[X[i]].emplace_back(Y[i], W[i]);
sort(all(fish));
fishWeightSum.resize(N);
for (ll i = 0; i < N; i++) {
fishWeightSum[i].emplace_back(LLONG_MIN, 0);
}
for (auto [x, y, w] : fish) {
fishWeightSum[x].emplace_back(y, fishWeightSum[x].back().second + w);
}
for (ll i = 0; i < N; i++) {
fishWeightSum[i].emplace_back(LLONG_MAX, fishWeightSum[i].back().second);
}
vector<ll> dpv(piers.size() + 1);
ll* dp = &dpv[1];
for (ll lp = (ll)piers.size() - 1; lp >= -1; lp--) {
ll cx = lp == -1 ? -5 : piers[lp].first;
ll cy = lp == -1 ? -5 : piers[lp].second;
//ll x1ShortFirstIdx = lower_bound(all(piers), make_pair(cx + 1, LLONG_MIN)) - piers.begin();
//ll x1LongFirstIdx = lower_bound(all(piers), make_pair(cx + 1, cy)) - piers.begin();
//ll x2FirstIdx = lower_bound(all(piers), make_pair(cx + 2, LLONG_MIN)) - piers.begin();
ll ans = 0;
for (ll np = lp + 1; np < (ll)piers.size(); np++) {
auto [nx, ny] = piers[np];
if (nx == cx + 1) {
if (ny <= cy) {
ans = max(ans, dp[np]
+ weightSum(nx + 1, ny)
- weightSum(nx, ny)
);
} else {
ans = max(ans, dp[np]
+ weightSum(nx + 1, ny)
+ weightSum(nx - 1, ny)
- weightSum(cx, cy)
- weightSum(cx + 1, cy)
);
}
} else if (nx == cx + 2) {
if (ny <= cy) {
ans = max(ans, dp[np] + weightSum(nx + 1, ny));
} else {
ans = max(ans, dp[np]
+ weightSum(nx + 1, ny)
+ weightSum(nx - 1, ny)
- weightSum(cx + 1, cy)
);
}
} else if (nx > cx + 2) {
ans = max(ans, dp[np] + weightSum(nx + 1, ny) + weightSum(nx - 1, ny));
}
}
dp[lp] = ans;
}
return dp[-1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
16988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1073 ms |
28676 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9684 KB |
Output is correct |
| 3 |
Execution timed out |
1082 ms |
16840 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
340 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '254964121270' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
340 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '254964121270' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
340 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '254964121270' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9684 KB |
Output is correct |
| 3 |
Execution timed out |
1082 ms |
16840 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
16988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
