// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
const ll maxn = 100005;
set<ll> heights[maxn];
basic_string<ll> realheights[maxn];
unordered_map<ll,ll> weights;
basic_string<ll> p[maxn];
basic_string<array<ll,2>> dp[maxn];
basic_string<ll> pref[maxn][2];
basic_string<ll> pref2[maxn][2];
basic_string<ll> suff[maxn][2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
weights.reserve(524288);
FOR(i,0,M){
Y[i]++;
weights[X[i]*100000000+Y[i]] = W[i];
if (X[i] > 0) heights[X[i]-1].insert(Y[i]);
if (X[i] > 1) heights[X[i]-2].insert(Y[i]);
heights[X[i]].insert(Y[i]);
heights[X[i]+1].insert(Y[i]);
heights[X[i]+2].insert(Y[i]);
}
FOR(i,0,maxn) heights[i].insert(0);
FOR(i,0,maxn) heights[i].insert(maxn);
FOR(i,0,maxn){
FOR(k,0,2){
pref[i][k].resize(heights[i].size());
pref2[i][k].resize(heights[i].size());
suff[i][k].resize(heights[i].size());
}
p[i].resize(heights[i].size());
dp[i].resize(heights[i].size());
}
FOR(i,0,maxn){
for (auto k : heights[i]) realheights[i].push_back(k);
}
FOR(i,0,maxn){
p[i][0] = 0;
ll prev = 0;
FOR(j,1,heights[i].size()){
p[i][j] = p[i][j-1] + weights[i*100000000+realheights[i][j]];
}
}
FOR(i,1,N+1){
FOR(X,0,dp[i].size()){
ll j = realheights[i][X];
FOR(k,0,2){
if (i<2) continue;
ll temp = 0;
ll add = 0;
if (k==0){
if (X==dp[i].size()-1) continue;
ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
temp = max(temp, suff[i-1][0][down] - p[i-1][down]);
temp = max(temp, suff[i-1][1][down] - p[i-1][down]);
// FOR(p,j+1,N+1){
// if (fish[i-1][p]) add += weights[i-1][p];
// temp = max(temp, dp[i-1][p][0] + add);
// temp = max(temp, dp[i-1][p][1] + add);
// }
}else{
ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
ll down2 = upper_bound(realheights[i-2].begin(), realheights[i-2].end(), j) - realheights[i-2].begin() - 1;
temp = max(temp, pref[i-1][0][down]);
temp = max(temp, pref[i-1][1][down] + p[i-2][down2]);
// FOR(p,0,j+1) if (fish[i-2][p]) add += weights[i-2][p];
// FOR(p,0,j+1){
// if (fish[i-2][p]) add -= weights[i-2][p];
// temp = max(temp, dp[i-1][p][0]);
// temp = max(temp, dp[i-1][p][1] + add);
// }
}
dp[i][X][k] = temp;
}
}
ll sz = realheights[i].size();
FOR(k,0,2){
ll tempadd = 0;
ll tempadd2 = 0;
FOR(j,0,sz){
tempadd += weights[i*100000000+realheights[i][j]];
suff[i][k][j] = dp[i][j][k]+tempadd;
}
FOR(j,0,sz){
tempadd2 -= weights[(i-1)*100000000+realheights[i][j]];
pref[i][k][j] = dp[i][j][k] + tempadd2;
pref2[i][k][j] = dp[i][j][k];
}
ll prev = 0;
FOR(j,1,sz){
pref[i][k][j] = max(pref[i][k][j], pref[i][k][j-1]);
pref2[i][k][j] = max(pref2[i][k][j], pref2[i][k][j-1]);
}
FORNEG(j,sz-2,-1){
suff[i][k][j] = max(suff[i][k][j], suff[i][k][j+1]);
}
}
// cout << i << endl;
// cout << suff[2][2][0] << "FUCK" << endl;
}
// cout << dp[3][2][0] << endl;
ll ans = 0;
FOR(i,0,N+1){
FOR(j,0,dp[i].size()){
ans = max(dp[i][j][0], ans);
ans = max(dp[i][j][1], ans);
}
}
return ans;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:9:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
65 | FOR(j,1,heights[i].size()){
| ~~~~~~~~~~~~~~~~~~~~~
fish.cpp:65:13: note: in expansion of macro 'FOR'
65 | FOR(j,1,heights[i].size()){
| ^~~
fish.cpp:64:16: warning: unused variable 'prev' [-Wunused-variable]
64 | ll prev = 0;
| ^~~~
fish.cpp:9:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
74 | FOR(X,0,dp[i].size()){
| ~~~~~~~~~~~~~~~~
fish.cpp:74:13: note: in expansion of macro 'FOR'
74 | FOR(X,0,dp[i].size()){
| ^~~
fish.cpp:83:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if (X==dp[i].size()-1) continue;
| ~^~~~~~~~~~~~~~~~
fish.cpp:81:24: warning: unused variable 'add' [-Wunused-variable]
81 | ll add = 0;
| ^~~
fish.cpp:131:20: warning: unused variable 'prev' [-Wunused-variable]
131 | ll prev = 0;
| ^~~~
fish.cpp:9:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
158 | FOR(j,0,dp[i].size()){
| ~~~~~~~~~~~~~~~~
fish.cpp:158:13: note: in expansion of macro 'FOR'
158 | FOR(j,0,dp[i].size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
124096 KB |
Output is correct |
| 2 |
Correct |
311 ms |
133840 KB |
Output is correct |
| 3 |
Correct |
84 ms |
84564 KB |
Output is correct |
| 4 |
Correct |
87 ms |
84560 KB |
Output is correct |
| 5 |
Execution timed out |
1077 ms |
351832 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
81340 KB |
Output is correct |
| 2 |
Correct |
407 ms |
142476 KB |
Output is correct |
| 3 |
Correct |
570 ms |
159832 KB |
Output is correct |
| 4 |
Correct |
257 ms |
124100 KB |
Output is correct |
| 5 |
Correct |
326 ms |
134020 KB |
Output is correct |
| 6 |
Correct |
71 ms |
81488 KB |
Output is correct |
| 7 |
Correct |
63 ms |
81376 KB |
Output is correct |
| 8 |
Correct |
71 ms |
81488 KB |
Output is correct |
| 9 |
Correct |
68 ms |
81432 KB |
Output is correct |
| 10 |
Correct |
94 ms |
84488 KB |
Output is correct |
| 11 |
Correct |
88 ms |
84580 KB |
Output is correct |
| 12 |
Correct |
359 ms |
137328 KB |
Output is correct |
| 13 |
Correct |
384 ms |
157512 KB |
Output is correct |
| 14 |
Correct |
289 ms |
130504 KB |
Output is correct |
| 15 |
Correct |
239 ms |
117072 KB |
Output is correct |
| 16 |
Correct |
298 ms |
130764 KB |
Output is correct |
| 17 |
Correct |
338 ms |
136100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
84512 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
84456 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
81488 KB |
Output is correct |
| 2 |
Correct |
70 ms |
81492 KB |
Output is correct |
| 3 |
Correct |
68 ms |
81492 KB |
Output is correct |
| 4 |
Correct |
67 ms |
81436 KB |
Output is correct |
| 5 |
Correct |
66 ms |
81312 KB |
Output is correct |
| 6 |
Correct |
61 ms |
81488 KB |
Output is correct |
| 7 |
Correct |
64 ms |
81488 KB |
Output is correct |
| 8 |
Correct |
64 ms |
81488 KB |
Output is correct |
| 9 |
Incorrect |
72 ms |
81416 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '30688838905' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
81488 KB |
Output is correct |
| 2 |
Correct |
70 ms |
81492 KB |
Output is correct |
| 3 |
Correct |
68 ms |
81492 KB |
Output is correct |
| 4 |
Correct |
67 ms |
81436 KB |
Output is correct |
| 5 |
Correct |
66 ms |
81312 KB |
Output is correct |
| 6 |
Correct |
61 ms |
81488 KB |
Output is correct |
| 7 |
Correct |
64 ms |
81488 KB |
Output is correct |
| 8 |
Correct |
64 ms |
81488 KB |
Output is correct |
| 9 |
Incorrect |
72 ms |
81416 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '30688838905' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
81488 KB |
Output is correct |
| 2 |
Correct |
70 ms |
81492 KB |
Output is correct |
| 3 |
Correct |
68 ms |
81492 KB |
Output is correct |
| 4 |
Correct |
67 ms |
81436 KB |
Output is correct |
| 5 |
Correct |
66 ms |
81312 KB |
Output is correct |
| 6 |
Correct |
61 ms |
81488 KB |
Output is correct |
| 7 |
Correct |
64 ms |
81488 KB |
Output is correct |
| 8 |
Correct |
64 ms |
81488 KB |
Output is correct |
| 9 |
Incorrect |
72 ms |
81416 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '30688838905' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
84512 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
84456 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
124096 KB |
Output is correct |
| 2 |
Correct |
311 ms |
133840 KB |
Output is correct |
| 3 |
Correct |
84 ms |
84564 KB |
Output is correct |
| 4 |
Correct |
87 ms |
84560 KB |
Output is correct |
| 5 |
Execution timed out |
1077 ms |
351832 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
