#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;
unordered_set<ll> fish[maxn];
map<vector<ll>, ll> weights;
ll dp[8][8][maxn];
unordered_set<ll> temppos[maxn];
vector<ll> possibles[maxn];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
FOR(i,0,8){
FOR(j,0,8){
FOR(k,0,maxn){
dp[i][j][k] = 0;
}
}
}
FOR(i,0,maxn) temppos[i].insert(0);
FOR(i,0,M){
Y[i]++;
fish[X[i]].insert(Y[i]);
weights[{X[i], Y[i]}] = W[i];
if (X[i] > 0) temppos[X[i]-1].insert(Y[i]);
temppos[X[i]+1].insert(Y[i]);
temppos[X[i]].insert(Y[i]);
}
FOR(i,0,maxn){
for (auto&k : temppos[i]) possibles[i].push_back(k);
}
FOR(k,0,N){
FOR(X,0,8){
FOR(Y,0,8){
ll i=0,j=0;
if (k>=2 && possibles[k-2].size() <= X) continue;
else if (k>=2) i = possibles[k-2][X];
if (k>=1 && possibles[k-1].size() <= Y) continue;
else if (k>=1) j = possibles[k-1][Y];
ll temp = 0;
FOR(Z, 0, 8){
if (possibles[k].size() <= Z) continue;
ll height = possibles[k][Z];
if (fish[k+1].count(height)) temp += weights[{k+1, height}];
if (fish[k].count(height) && j>=height) temp -= weights[{k, height}];
if (k>0 && fish[k-1].count(height) && i < height && j<height) temp += weights[{k-1, height}];
dp[Y][Z][k+1] = max(dp[Y][Z][k+1], dp[X][Y][k] + temp);
}
}
}
}
ll ans = 0;
FOR(i,0,8){
FOR(j,0,8){
FOR(k,0,N+1){
ans = max(ans, dp[i][j][k]);
//if (dp[i][j][k]==11) cout << i << " " << j << " " << k << endl;
}
}
}
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:51:51: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
51 | if (k>=2 && possibles[k-2].size() <= X) continue;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:53:51: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
53 | if (k>=1 && possibles[k-1].size() <= Y) continue;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~
fish.cpp:60:45: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
60 | if (possibles[k].size() <= Z) continue;
| ~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
102656 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '3547320742' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
81236 KB |
1st lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
80980 KB |
Output is correct |
| 2 |
Correct |
83 ms |
80976 KB |
Output is correct |
| 3 |
Incorrect |
169 ms |
97376 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '53445416092380' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
80900 KB |
1st lines differ - on the 1st token, expected: '3', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
80900 KB |
1st lines differ - on the 1st token, expected: '3', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
80900 KB |
1st lines differ - on the 1st token, expected: '3', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
80980 KB |
Output is correct |
| 2 |
Correct |
83 ms |
80976 KB |
Output is correct |
| 3 |
Incorrect |
169 ms |
97376 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '53445416092380' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
102656 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '3547320742' |
| 2 |
Halted |
0 ms |
0 KB |
- |
