#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> fish[maxn];
map<vector<ll>, ll> weights;
ll dp[7][7][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,7){
FOR(j,0,7){
FOR(k,0,maxn){
dp[i][j][k] = 0;
}
}
}
FOR(i,0,maxn) possibles[i].push_back(0);
FOR(i,0,M){
Y[i]++;
fish[X[i]].insert(Y[i]);
weights[{X[i], Y[i]}] = W[i];
if (X[i] > 0) possibles[X[i]-1].push_back(Y[i]);
possibles[X[i]+1].push_back(Y[i]);
possibles[X[i]].push_back(Y[i]);
}
FOR(i,0,maxn){
sort(possibles[i].begin(), possibles[i].end());
}
FOR(k,0,N){
FOR(X,0,7){
FOR(Y,0,7){
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, 7){
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,7){
FOR(j,0,7){
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 |
113 ms |
66108 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '2335128467' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
48984 KB |
Output is correct |
| 2 |
Incorrect |
205 ms |
84152 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '6208775216' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
48976 KB |
Output is correct |
| 2 |
Correct |
34 ms |
48732 KB |
Output is correct |
| 3 |
Incorrect |
318 ms |
60500 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '60087315441923' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
23 ms |
48728 KB |
Output is correct |
| 3 |
Correct |
21 ms |
48728 KB |
Output is correct |
| 4 |
Correct |
20 ms |
48732 KB |
Output is correct |
| 5 |
Correct |
22 ms |
48732 KB |
Output is correct |
| 6 |
Correct |
24 ms |
48732 KB |
Output is correct |
| 7 |
Correct |
22 ms |
48976 KB |
Output is correct |
| 8 |
Correct |
22 ms |
48728 KB |
Output is correct |
| 9 |
Incorrect |
25 ms |
48988 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '338618736309' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
23 ms |
48728 KB |
Output is correct |
| 3 |
Correct |
21 ms |
48728 KB |
Output is correct |
| 4 |
Correct |
20 ms |
48732 KB |
Output is correct |
| 5 |
Correct |
22 ms |
48732 KB |
Output is correct |
| 6 |
Correct |
24 ms |
48732 KB |
Output is correct |
| 7 |
Correct |
22 ms |
48976 KB |
Output is correct |
| 8 |
Correct |
22 ms |
48728 KB |
Output is correct |
| 9 |
Incorrect |
25 ms |
48988 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '338618736309' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
23 ms |
48728 KB |
Output is correct |
| 3 |
Correct |
21 ms |
48728 KB |
Output is correct |
| 4 |
Correct |
20 ms |
48732 KB |
Output is correct |
| 5 |
Correct |
22 ms |
48732 KB |
Output is correct |
| 6 |
Correct |
24 ms |
48732 KB |
Output is correct |
| 7 |
Correct |
22 ms |
48976 KB |
Output is correct |
| 8 |
Correct |
22 ms |
48728 KB |
Output is correct |
| 9 |
Incorrect |
25 ms |
48988 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '338618736309' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
48976 KB |
Output is correct |
| 2 |
Correct |
34 ms |
48732 KB |
Output is correct |
| 3 |
Incorrect |
318 ms |
60500 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '60087315441923' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
66108 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '2335128467' |
| 2 |
Halted |
0 ms |
0 KB |
- |
