This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100105;
vector<pair<int, int>> fish[mx];
ll bests[mx];
ll maxs[mx];
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for(int i = 0; i < M; i++) {
fish[X[i] + 10].push_back({Y[i], W[i]});
}
for(int i = 10; i < N + 10; i++) {
sort(fish[i].begin(), fish[i].end());
fish[i].push_back({N + 10, 0});
if(i < 10) continue;
int cur = i;
//if(i > 3)
//bests[i - 3] = max(bests[i - 3], bests[i - 4]);
//bests[i - 2] = max(bests[i - 2], bests[i - 3]);
/* double dock */
if(i != 10) {
/* i am full */
{
ll cur_sum = 0;
for(auto [pos, val] : fish[i - 1]) cur_sum += val;
for(auto [pos, val] : fish[i + 1]) cur_sum += val;
ll best_sum = cur_sum;
int pp_idx = 0;
int p_idx = 0;
while(p_idx != fish[cur - 1].size()) {
while(pp_idx != fish[cur - 2].size() && fish[cur - 2][pp_idx].first < fish[cur - 1][p_idx].first) {
cur_sum += fish[cur - 2][pp_idx].second;
best_sum = max(best_sum, cur_sum);
pp_idx++;
}
cur_sum -= fish[cur - 1][p_idx].second;
p_idx++;
}
//cout << i - 10 << ",1: " << cur_sum << endl;
bests[i] = max(bests[i], maxs[i - 4] + best_sum);
}
//cout << bests[i] << " ";
/* prev is full */
{
ll cur_sum = 0;
for(auto [pos, val] : fish[i - 2]) cur_sum += val;
for(auto [pos, val] : fish[i]) cur_sum += val;
ll best_sum = cur_sum;
int c_idx = 0;
int n_idx = 0;
while(c_idx != fish[cur].size()) {
while(n_idx != fish[cur + 1].size() && fish[cur + 1][n_idx].first < fish[cur][c_idx].first) {
cur_sum += fish[cur + 1][n_idx].second;
best_sum = max(best_sum, cur_sum);
n_idx++;
}
cur_sum -= fish[cur][c_idx].second;
c_idx++;
}
//cout << i - 10 << ",2: " << cur_sum << endl;
bests[i] = max(bests[i], maxs[i - 4] + best_sum);
}
//cout << bests[i] << " ";
}
/* single dock */
{
ll cur_sum = 0;
for(auto [pos, val] : fish[i + 1]) cur_sum += val;
bests[i] = max(bests[i], maxs[i - 2] + cur_sum);
for(auto [pos, val] : fish[i - 1]) cur_sum += val;
bests[i] = max(bests[i], maxs[i - 3] + cur_sum);
//cout << i - 10 << ",3: " << cur_sum << endl;
}
//cout << bests[i] << endl;
maxs[i] = max(bests[i], maxs[i - 1]);
}
//for(int i = 10; i < N + 10; i++) cout << bests[i] << " ";
return bests[N + 9];
}
Compilation message (stderr)
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | while(p_idx != fish[cur - 1].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | while(pp_idx != fish[cur - 2].size() && fish[cur - 2][pp_idx].first < fish[cur - 1][p_idx].first) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while(c_idx != fish[cur].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while(n_idx != fish[cur + 1].size() && fish[cur + 1][n_idx].first < fish[cur][c_idx].first) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |