#include "fish.h"
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
ll dp[3005][3005][2], sum[3005][3005];
long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W)
{
for(int i=0; i<m; i++)
sum[X[i]][Y[i]]=W[i];
for(int i=0; i<n; i++)
for(int j=1; j<n; j++)
sum[i][j]+=sum[i][j-1];
for(int i=1; i<n; i++)
{
for(int j=0; j<n; j++)
{
for(int l=j; l<n; l++)
{
dp[i][j][0]=max(dp[i][j][0], max(dp[i-1][l][0], dp[i-1][l][1])+(sum[i][l]-sum[i][j-1]));
if(i-2>=0) dp[i][j][1]=max(dp[i][j][1], max(dp[i-2][l][0], dp[i-2][l][1])+sum[i-1][l]);
}
for(int l=0; l<j; l++)
{
dp[i][j][1]=max(dp[i][j][1], dp[i-1][l][1]+(sum[i-1][j]-sum[i-1][l-1]));
if(i-2>=0) dp[i][j][1]=max(dp[i][j][1], max(dp[i-2][l][0], dp[i-2][l][1])+sum[i-1][j]);
}
}
}
ll ans=0;
for(int i=0; i<n; i++)
ans=max({ans, dp[n-1][i][0], dp[n-1][i][1]});
return ans;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1075 ms |
121200 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
1068 ms |
120108 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1076 ms |
108772 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
14 ms |
2040 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
14 ms |
2040 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
14 ms |
2040 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1076 ms |
108772 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1075 ms |
121200 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |