#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int>fishies[3002];
ll FIS2;
ll dp[3010][2][3010],fishiess[3010][3010];
ll first[3010][3010];
ll sec[3010][301],third[3010][3010],overal[3010][3010];
inline ll ones(int col,int len){
return fishiess[col][len];
}
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
for(int i=0;i<M;i++)
fishies[X[i]+1].insert(Y[i]+1),
fishiess[X[i]+1][Y[i]+1]=W[i];
for(int i=1;i<=N;i++)
for(int j=1;j<=N+1;j++)
fishiess[i][j]+=fishiess[i][j-1];
for(int i=1;i<=N;i++)
fishies[i].insert(1),
fishies[i].insert(N+1);
fishies[N+1].insert(0);
for(auto i:fishies[1])
dp[1][1][i-1]=ones(2,i-1);
for(int j=0;j<=N;j++){
overal[1][j]=first[1][j]=max(dp[1][0][j],dp[1][1][j]);
first[1][j]-=ones(2,j);sec[1][j]=dp[1][0][j];
third[1][j]=dp[1][1][j]-ones(1,j)-ones(2,j);
}
for(int j=N;j--;)
overal[1][j]=max(overal[1][j],overal[1][j+1]),
sec[1][j]=max(sec[1][j],sec[1][j+1]);
for(int j=1;j<=N;j++)
first[1][j]=max(first[1][j],first[1][j-1]),
third[1][j]=max(third[1][j],third[1][j-1]);
for(int i=2;i<=N;i++){
for(auto rw:fishies[i]) {
ll cons=ones(i+1,rw-1)+ones(i-1,rw-1);
dp[i][1][rw-1]=cons+max(first[i-2][rw-1],overal[i-2][rw]-ones(i-1,rw-1));
}
for(auto rw2:fishies[i]){
ll cons=ones(i+1,rw2-1)+ones(i-1,rw2-1);
dp[i][1][rw2-1]=max(dp[i][1][rw2-1],third[i-1][rw2-1]+cons);
dp[i][0][rw2-1]=overal[i-1][rw2]-ones(i,rw2-1)-ones(i-1,rw2-1)+cons;
}
for(auto rw2:fishies[i])
dp[i][0][rw2-1]=max(dp[i][0][rw2-1],ones(i+1,rw2-1)-ones(i,rw2-1)+sec[i-1][rw2-1]);
for(int j=0;j<=N;j++){
overal[i][j]=first[i][j]=max(dp[i][0][j],dp[i][1][j]);
first[i][j]-=ones(i+1,j);sec[i][j]=dp[i][0][j];
third[i][j]=dp[i][1][j]-ones(i,j)-ones(i+1,j);
}
for(int j=N;j--;)
overal[i][j]=max(overal[i][j],overal[i][j+1]),
sec[i][j]=max(sec[i][j],sec[i][j+1]);
for(int j=1;j<=N;j++)
first[i][j]=max(first[i][j],first[i][j-1]),
third[i][j]=max(third[i][j],third[i][j-1]);
}
return overal[N][0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
557 ms |
445268 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Runtime error |
597 ms |
458284 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
575 ms |
432464 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Correct |
1 ms |
12892 KB |
Output is correct |
3 |
Correct |
1 ms |
10844 KB |
Output is correct |
4 |
Correct |
1 ms |
10844 KB |
Output is correct |
5 |
Correct |
1 ms |
10844 KB |
Output is correct |
6 |
Correct |
1 ms |
10844 KB |
Output is correct |
7 |
Correct |
1 ms |
10844 KB |
Output is correct |
8 |
Correct |
1 ms |
10844 KB |
Output is correct |
9 |
Correct |
3 ms |
33424 KB |
Output is correct |
10 |
Correct |
5 ms |
42384 KB |
Output is correct |
11 |
Correct |
3 ms |
33372 KB |
Output is correct |
12 |
Correct |
5 ms |
42264 KB |
Output is correct |
13 |
Correct |
2 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
42332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Correct |
1 ms |
12892 KB |
Output is correct |
3 |
Correct |
1 ms |
10844 KB |
Output is correct |
4 |
Correct |
1 ms |
10844 KB |
Output is correct |
5 |
Correct |
1 ms |
10844 KB |
Output is correct |
6 |
Correct |
1 ms |
10844 KB |
Output is correct |
7 |
Correct |
1 ms |
10844 KB |
Output is correct |
8 |
Correct |
1 ms |
10844 KB |
Output is correct |
9 |
Correct |
3 ms |
33424 KB |
Output is correct |
10 |
Correct |
5 ms |
42384 KB |
Output is correct |
11 |
Correct |
3 ms |
33372 KB |
Output is correct |
12 |
Correct |
5 ms |
42264 KB |
Output is correct |
13 |
Correct |
2 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
42332 KB |
Output is correct |
15 |
Correct |
5 ms |
42164 KB |
Output is correct |
16 |
Correct |
3 ms |
21084 KB |
Output is correct |
17 |
Correct |
20 ms |
46172 KB |
Output is correct |
18 |
Correct |
20 ms |
46172 KB |
Output is correct |
19 |
Correct |
19 ms |
46168 KB |
Output is correct |
20 |
Correct |
19 ms |
46172 KB |
Output is correct |
21 |
Correct |
19 ms |
46172 KB |
Output is correct |
22 |
Correct |
37 ms |
50004 KB |
Output is correct |
23 |
Correct |
7 ms |
42840 KB |
Output is correct |
24 |
Correct |
14 ms |
44892 KB |
Output is correct |
25 |
Correct |
5 ms |
42332 KB |
Output is correct |
26 |
Correct |
6 ms |
42972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
10840 KB |
Output is correct |
2 |
Correct |
1 ms |
12892 KB |
Output is correct |
3 |
Correct |
1 ms |
10844 KB |
Output is correct |
4 |
Correct |
1 ms |
10844 KB |
Output is correct |
5 |
Correct |
1 ms |
10844 KB |
Output is correct |
6 |
Correct |
1 ms |
10844 KB |
Output is correct |
7 |
Correct |
1 ms |
10844 KB |
Output is correct |
8 |
Correct |
1 ms |
10844 KB |
Output is correct |
9 |
Correct |
3 ms |
33424 KB |
Output is correct |
10 |
Correct |
5 ms |
42384 KB |
Output is correct |
11 |
Correct |
3 ms |
33372 KB |
Output is correct |
12 |
Correct |
5 ms |
42264 KB |
Output is correct |
13 |
Correct |
2 ms |
21084 KB |
Output is correct |
14 |
Correct |
4 ms |
42332 KB |
Output is correct |
15 |
Correct |
5 ms |
42164 KB |
Output is correct |
16 |
Correct |
3 ms |
21084 KB |
Output is correct |
17 |
Correct |
20 ms |
46172 KB |
Output is correct |
18 |
Correct |
20 ms |
46172 KB |
Output is correct |
19 |
Correct |
19 ms |
46168 KB |
Output is correct |
20 |
Correct |
19 ms |
46172 KB |
Output is correct |
21 |
Correct |
19 ms |
46172 KB |
Output is correct |
22 |
Correct |
37 ms |
50004 KB |
Output is correct |
23 |
Correct |
7 ms |
42840 KB |
Output is correct |
24 |
Correct |
14 ms |
44892 KB |
Output is correct |
25 |
Correct |
5 ms |
42332 KB |
Output is correct |
26 |
Correct |
6 ms |
42972 KB |
Output is correct |
27 |
Correct |
142 ms |
335700 KB |
Output is correct |
28 |
Correct |
107 ms |
88148 KB |
Output is correct |
29 |
Correct |
286 ms |
347008 KB |
Output is correct |
30 |
Correct |
291 ms |
412288 KB |
Output is correct |
31 |
Correct |
286 ms |
412244 KB |
Output is correct |
32 |
Correct |
149 ms |
81748 KB |
Output is correct |
33 |
Correct |
294 ms |
458576 KB |
Output is correct |
34 |
Correct |
296 ms |
458832 KB |
Output is correct |
35 |
Correct |
173 ms |
332180 KB |
Output is correct |
36 |
Correct |
299 ms |
365396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
575 ms |
432464 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
557 ms |
445268 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |