#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;
// dp[i][0][k] == no wall at i
for(int i=1;i<n;i++)
{
// ll pre0[n+1],pre1[n+1];
// for(int j=n;j>=0;j--)
// pre0[j]=dp[i-1][j][0],pre1[j]=dp[i-1][j][1];
// for(int j=n-1;j>=0;j--)
// pre0[j]=max(pre0[j],pre0[j+1]),pre1[j]=max(pre1[j],pre1[j+1]);
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);
}
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]);
}
}
}
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:65:16: warning: unused variable 'ans' [-Wunused-variable]
65 | ll n=N,m=M,ans=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
997 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
974 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1002 ms |
2097152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
9 ms |
1116 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '166240603529' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
9 ms |
1116 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '166240603529' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
9 ms |
1116 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '166240603529' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1002 ms |
2097152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
997 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
