| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 659595 |
2022-11-18T17:38:35 Z |
peijar |
Catfish Farm (IOI22_fish) |
C++17 |
|
1000 ms |
826380 KB |
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
const int MAXN = 1e5;
vector<pair<int, int>> dp[MAXN][2];
int eval(int i, int side, int h) {
auto it = upper_bound(dp[i][side].begin(), dp[i][side].end(), pair(h, INF));
assert(it != dp[i][side].begin());
--it;
return it->second;
}
int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y,
vector<signed> W) {
vector<vector<pair<int, int>>> onCol(N);
vector<vector<int>> prefSum(N);
for (int i = 0; i < M; ++i)
onCol[X[i]].emplace_back(Y[i] + 1, W[i]);
for (int i = 0; i < N; ++i) {
sort(onCol[i].begin(), onCol[i].end());
prefSum[i].resize(onCol[i].size() + 1);
for (int j = 0; j < (int)onCol[i].size(); ++j)
prefSum[i][j + 1] = prefSum[i][j] + onCol[i][j].second;
}
vector<vector<int>> interesting(N);
for (int i = 0; i < N; ++i) {
interesting[i].push_back(0);
for (auto [y, w] : onCol[i])
interesting[i].push_back(y);
if (i)
for (auto [y, w] : onCol[i - 1])
interesting[i].push_back(y);
if (i + 1 < N)
for (auto [y, w] : onCol[i + 1])
interesting[i].push_back(y);
interesting[i].push_back(N);
sort(interesting[i].begin(), interesting[i].end());
interesting[i].resize(unique(interesting[i].begin(), interesting[i].end()) -
interesting[i].begin());
}
dp[0][0].emplace_back(0, 0);
dp[0][1].emplace_back(0, 0);
auto getSum = [&](int i, int h1, int h2) -> int {
int lo = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h1, INF)) -
onCol[i].begin();
int up = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h2, INF)) -
onCol[i].begin();
return prefSum[i][up] - prefSum[i][lo];
};
int sol = 0;
for (int i = 1; i < N; ++i) {
int nbInteressants = interesting[i].size();
for (int iHauteur = 0; iHauteur < nbInteressants; ++iHauteur) {
int h = interesting[i][iHauteur];
// 1
int v1 = 0;
for (int jHauteur = iHauteur + 1; jHauteur < nbInteressants; ++jHauteur) {
int oldH = interesting[i][jHauteur];
v1 = max(v1, getSum(i, h, oldH) + eval(i - 1, 1, oldH));
}
// 0
int v0 = 0;
for (int jHauteur = 0; jHauteur < nbInteressants; ++jHauteur) {
int oldH = interesting[i][jHauteur];
if (jHauteur >= iHauteur)
v0 = max(v0, eval(i - 1, 1, oldH));
else {
v0 = max(v0, getSum(i - 1, oldH, h) + eval(i - 1, 0, oldH));
}
v1 = max(v1, v0);
sol = max(sol, v1);
dp[i][0].emplace_back(h, v0);
dp[i][1].emplace_back(h, v1);
// cout << i << ' ' << h << ' ' << v0 << ' ' << v1 << endl;
}
}
}
return sol;
/*for (int i = 1; i < N; ++i)
for (int h = 0; h <= N; ++h) {
// 1
for (int oldH = h + 1; oldH <= N; ++oldH) {
int lo = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h, INF)) -
onCol[i].begin();
int up =
upper_bound(onCol[i].begin(), onCol[i].end(), pair(oldH, INF)) -
onCol[i].begin();
dp[i][h][1] =
max(dp[i][h][1], prefSum[i][up] - prefSum[i][lo] +
max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
}
// 0
for (int oldH = 0; oldH <= N; ++oldH) {
if (oldH >= h)
dp[i][h][0] =
max(dp[i][h][0], max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
else {
int lo = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
pair(oldH, INF)) -
onCol[i - 1].begin();
int up = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
pair(h, INF)) -
onCol[i - 1].begin();
dp[i][h][0] =
max(dp[i][h][0],
dp[i - 1][oldH][0] + prefSum[i - 1][up] - prefSum[i - 1][lo]);
}
}
sol = max({sol, dp[i][h][0], dp[i][h][1]});
}
return sol;*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1136 ms |
826380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
33868 KB |
Output is correct |
| 2 |
Correct |
51 ms |
33868 KB |
Output is correct |
| 3 |
Correct |
103 ms |
58564 KB |
Output is correct |
| 4 |
Correct |
87 ms |
54860 KB |
Output is correct |
| 5 |
Correct |
144 ms |
82528 KB |
Output is correct |
| 6 |
Correct |
138 ms |
82468 KB |
Output is correct |
| 7 |
Correct |
145 ms |
82420 KB |
Output is correct |
| 8 |
Correct |
145 ms |
82448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
33868 KB |
Output is correct |
| 2 |
Correct |
51 ms |
33868 KB |
Output is correct |
| 3 |
Correct |
103 ms |
58564 KB |
Output is correct |
| 4 |
Correct |
87 ms |
54860 KB |
Output is correct |
| 5 |
Correct |
144 ms |
82528 KB |
Output is correct |
| 6 |
Correct |
138 ms |
82468 KB |
Output is correct |
| 7 |
Correct |
145 ms |
82420 KB |
Output is correct |
| 8 |
Correct |
145 ms |
82448 KB |
Output is correct |
| 9 |
Incorrect |
214 ms |
131684 KB |
1st lines differ - on the 1st token, expected: '99999', found: '66666' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1136 ms |
826380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
