| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 671272 |
2022-12-12T16:09:13 Z |
pls33 |
Catfish Farm (IOI22_fish) |
C++17 |
|
1000 ms |
2097152 KB |
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion
void update(int64_t val, p32 fish, vvi64 &vect)
{
vect[fish.first][fish.second] = max(vect[fish.first][fish.second], val);
}
int64_t weight_sum(int i, int j, vi64 &prefix)
{
if (i == -1)
{
return 0;
}
int64_t sum = prefix[j];
if (i)
{
sum -= prefix[i];
}
return sum;
}
int64_t new_weight(p32 lhs, p32 rhs, vvi64 &prefix)
{
int64_t left = rhs.first
? weight_sum(0, rhs.second, prefix[rhs.first - 1])
: 0;
int64_t right = (rhs.first + 1 < (int)prefix.size())
? weight_sum(0, rhs.second, prefix[rhs.first + 1])
: 0;
if (lhs.first == -1)
{
return left + right;
}
if (rhs.first - lhs.first > 2)
{
return left + right;
}
if (rhs.first - lhs.first == 2)
{
if (lhs.second >= rhs.second)
{
return right;
}
left -= weight_sum(0, lhs.second, prefix[rhs.first - 1]);
return left + right;
}
if (lhs.second > rhs.second)
{
left = -weight_sum(0, rhs.second, prefix[rhs.first]);
return left + right;
}
left -= weight_sum(0, lhs.second, prefix[rhs.first]) +
weight_sum(0, lhs.second, prefix[rhs.first - 1]);
return left + right;
}
long long max_weights(int N, int M,
std::vector<int> X,
std::vector<int> Y,
std::vector<int> W)
{
vp32 fish;
vvi64 prefix(N, vi64(N));
int max_y = 0;
for (int i = 0; i < M; i++)
{
max_y = max(max_y, Y[i]);
prefix[X[i]][Y[i]] = W[i];
if (X[i])
{
fish.push_back({X[i] - 1, Y[i]});
}
if (X[i] < N - 1)
{
fish.push_back({X[i] + 1, Y[i]});
}
}
max_y++;
for (auto &row : prefix)
{
for (int i = 1; i < (int)row.size(); i++)
{
row[i] += row[i - 1];
}
}
sort(fish.begin(), fish.end());
vvi64 decrease(N, vi64(max_y + 1));
vvi64 increase = decrease;
for (auto &f : fish)
{
update(new_weight(p32(-1, -1), f, prefix), f, increase);
update(new_weight(p32(-1, -1), f, prefix), f, decrease);
for (int i = 0; i < f.first; i++)
{
for (int j = 0; j < (int)increase[0].size(); j++)
{
if (i == f.first - 1 && j == f.second)
{
continue;
}
int64_t prev = max(increase[i][j], decrease[i][j]);
prev += new_weight(p32(i, j), f, prefix);
if (i == f.first - 1)
{
if (j < f.second)
{
update(prev, f, increase);
}
else
{
update(prev, f, decrease);
}
}
else
{
update(prev, f, increase);
update(prev, f, decrease);
}
}
}
}
int64_t res = 0;
for (int i = 0; i < (int)increase.size(); i++)
{
for (int j = 0; j < (int)increase[0].size(); j++)
{
res = max({res, increase[i][j], decrease[i][j]});
}
}
return res;
}
Compilation message
fish.cpp:4: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
4 | #pragma region dalykai
|
fish.cpp:27: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
27 | #pragma endregion
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1164 ms |
2037668 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 |
Runtime error |
900 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
769 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
296 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
300 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
468 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '254936754550' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
296 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
300 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
468 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '254936754550' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
296 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
300 KB |
Output is correct |
| 9 |
Incorrect |
3 ms |
468 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '254936754550' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
769 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1164 ms |
2037668 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
