#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define all(x) begin(x),end(x)
ll solve(ll&n,ll&m,vll&x,vll&y,vll&w)
{
ll ans=0;
ll val[n+1][n+1];
for(int i=0;i<n;i++)for(int j=0;j<=n;j++)val[i][j]=0;
for(int j=0;j<m;j++)val[x[j]][y[j]+1]+=w[j];
ll dp[n+1][n+1][3];
for(int i=0;i<n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<2;k++)
dp[i][j][k]=0;
for(int i=1;i<n;i++)
{
ll sum=0;
for(int h=0;h<=n;h++)
{
sum+=val[i-1][h];
ll aux=0;
for(int nh=h+1;nh<=n;nh++)
{
aux+=val[i][nh];
dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][0]);
dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][1]);
dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][0]);
dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][1]+aux);
}
ll og=sum;
for(int nh=0;nh<=h;nh++)
{
sum-=val[i][nh];
dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][0]+sum);
dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][1]);
dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][0]+sum);
dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][1]);
}
sum=og;
}
}
for(int i=0;i<n;i++)
{
for(int h=0;h<=n;h++)
{
// cout<<"For: "<<i<<' '<<h<<' '<<dp[i][h][0]<<' '<<dp[i][h][1]<<endl;
ans=max(ans,dp[i][h][0]);
ans=max(ans,dp[i][h][1]);
}
}
return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W)
{
ll n=N,m=M,ans=0;
vector<ll> x(all(X)),y(all(Y)),w(all(W));
return solve(n,m,x,y,w);
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:61:16: warning: unused variable 'ans' [-Wunused-variable]
61 | ll n=N,m=M,ans=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
961 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
979 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
993 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
436 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
440 KB |
Output is correct |
| 9 |
Incorrect |
10 ms |
1116 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '217950211616' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
436 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
440 KB |
Output is correct |
| 9 |
Incorrect |
10 ms |
1116 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '217950211616' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
436 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
440 KB |
Output is correct |
| 9 |
Incorrect |
10 ms |
1116 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '217950211616' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
993 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
961 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
