이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 100001;
struct state
{
int32_t s, l, z;
};
vector<state> f[N];
vector<int32_t> p[N];
vector<uint32_t> coords[N];
size_t ind(size_t x, int y)
{
return lower_bound(coords[x].begin(), coords[x].end(), y) - coords[x].begin();
}
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
for (size_t i = 0; i < m; ++i)
{
coords[x[i]].push_back(y[i] + 1);
if (x[i])
coords[x[i] - 1].push_back(y[i] + 1);
if (x[i] + 1 < n)
coords[x[i] + 1].push_back(y[i] + 1);
}
for (size_t i = 0; i < n; ++i)
{
coords[i].push_back(0);
sort(coords[i].begin(), coords[i].end());
coords[i].resize(unique(coords[i].begin(), coords[i].end()) - coords[i].begin());
f[i].resize(coords[i].size());
p[i].resize(coords[i].size());
}
for (size_t i = 1; i < n; ++i)
for (size_t j = 0; j < f[i].size(); ++j)
f[i][j].s = f[i][j].l = f[i][j].z = INT64_MIN / 2;
for (size_t i = 0; i < m; ++i)
p[x[i]][ind(x[i], y[i] + 1)] = w[i];
for (size_t i = 0; i < n; ++i)
for (size_t j = 1; j < p[i].size(); ++j)
p[i][j] += p[i][j - 1];
for (size_t i = 1; i < n; ++i)
{
// Update s
int32_t h = f[i - 1][0].s;
size_t k = 0;
for (size_t j = 1; j < coords[i].size(); ++j)
{
while (k < coords[i - 1].size() && coords[i - 1][k] < coords[i][j])
{
f[i][j].s = max(f[i][j].s, h + p[i - 1][k]);
h = max(h, max(f[i - 1][k].s, f[i - 1][k].z) - p[i - 1][k]);
++k;
}
if (k != coords[i - 1].size())
{
f[i][j].s = max(f[i][j].s, h + p[i - 1][k]);
h = max(h, max(f[i - 1][k].s, f[i - 1][k].z) - p[i - 1][k]);
}
}
h = INT32_MIN;
k = coords[i - 1].size() - 1;
for (size_t j = coords[i].size() - 1; j <= coords[i].size(); --j)
{
while (k != SIZE_MAX && coords[i - 1][k] > coords[i][j])
{
h = max(h, f[i - 1][k].z);
f[i][j].s = max(f[i][j].s, h);
--k;
}
if (k != SIZE_MAX)
{
h = max(h, f[i - 1][k].z);
f[i][j].s = max(f[i][j].s, h);
}
}
// Update l
int32_t g = 0; // max f_i-1,k,s f_i-1,k-l + p_ik over all k >= j
k = coords[i - 1].size() - 1;
for (size_t j = coords[i].size() - 1; j < coords[i].size(); --j)
{
while (k != SIZE_MAX && coords[i - 1][k] > coords[i][j])
{
g = max(g, max(f[i - 1][k].l, f[i - 1][k].s) + p[i][j]);
f[i][j].l = max(f[i][j].l, g - p[i][j]);
--k;
}
if (k != SIZE_MAX)
{
g = max(g, max(f[i - 1][k].l, f[i - 1][k].s) + p[i][j]);
f[i][j].l = max(f[i][j].l, g - p[i][j]);
}
}
// Update z
k = 0;
for (size_t j = 0; j < coords[i].size(); ++j)
{
while (k < coords[i - 1].size() && coords[i - 1][k] < coords[i][j])
{
f[i][j].z = max(f[i - 1][k].s, f[i - 1][k].l) + p[i][j];
++k;
}
if (k != coords[i - 1].size())
f[i][j].z = max(f[i - 1][k].s, f[i - 1][k].l) + p[i][j];
if (!j)
{
for (size_t k = 0; k < coords[i - 1].size(); ++k)
f[i][j].z = max(f[i][j].z, f[i - 1][k].z);
}
}
}
int32_t ans = 0;
for (size_t j = 0; j < f[n - 1].size(); ++j)
ans = max(ans, max(f[n - 1][j].s, max(f[n - 1][j].l, f[n - 1][j].z)));
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:24:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
24 | for (size_t i = 0; i < m; ++i)
| ~~^~~
fish.cpp:33:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
33 | for (size_t i = 0; i < n; ++i)
| ~~^~~
fish.cpp:42:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | for (size_t i = 1; i < n; ++i)
| ~~^~~
fish.cpp:44:59: warning: overflow in conversion from 'long int' to 'int32_t' {aka 'int'} changes value from '-4611686018427387904' to '0' [-Woverflow]
44 | f[i][j].s = f[i][j].l = f[i][j].z = INT64_MIN / 2;
| ^
fish.cpp:46:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | for (size_t i = 0; i < m; ++i)
| ~~^~~
fish.cpp:48:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | for (size_t i = 0; i < n; ++i)
| ~~^~~
fish.cpp:52:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
52 | for (size_t i = 1; i < n; ++i)
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |