#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mx;
ll dp[100009][3][2];
ll dp2[309][309][2];
vector<int>g[100009],f[300009];
ll sum[3009][3009];
ll go5(int x,int lst,int u)
{
if(x==mx)return 0;
if(dp2[x][lst][u]!=-1)return dp2[x][lst][u];
for(int i=0;i<=mx;i++)
{
ll d=0;
if(u==0 && i>lst) d=sum[x-1][i]-sum[x-1][lst];
dp2[x][lst][u]=max(dp2[x][lst][u],d+go5(x+1,i,0));
if(i<lst)d+=sum[x][lst]-sum[x][i];
dp2[x][lst][u]=max(dp2[x][lst][u],d+go5(x+1,i,1));
}
return dp2[x][lst][u];
}
ll max_weights5(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
mx=N;
for(int i=0;i<M;i++)sum[X[i]][Y[i]+1]+=W[i];
for(int i=0;i<N;i++)
for(int j=1;j<=N;j++)sum[i][j]+=sum[i][j-1];
memset(dp,-1,sizeof dp);
ll ans=0;
for(int i=0;i<=N;i++)
ans=max(ans,go5(1,i,0));
return ans;
}
ll go7(int x,int lst,int u)
{
if(x==mx)return 0;
if(dp[x][lst][u]!=-1)return dp[x][lst][u];
for(int i=0;i<g[x].size();i++)
{
ll d=0;
if((u==0) && g[x][i]>g[x-1][lst])
{
for(int j=0;j<g[x-1].size();j++)
if(g[x-1][j]>=g[x-1][lst] && g[x-1][j]<g[x][i])d+=f[x-1][j];
}
dp[x][lst][u]=max(dp[x][lst][u],d+go7(x+1,i,0));
for(int j=0;j<g[x].size();j++)
if(g[x][j]<g[x-1][lst] && g[x][j]>=g[x][i])d+=f[x][j];
dp[x][lst][u]=max(dp[x][lst][u],d+go7(x+1,i,1));
}
return dp[x][lst][u];
}
ll max_weights7(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
mx=N;
for(int i=0;i<M;i++)
{
g[X[i]].push_back(Y[i]+1);
f[X[i]].push_back(W[i]);
}
for(int i=0;i<N;i++)
{
g[i].push_back(N+1);f[i].push_back(0);
}
memset(dp,-1,sizeof dp);
ll ans=0;
for(int i=0;i<g[0].size();i++)
ans=max(ans,go7(1,i,0));
return ans;
}
ll max_weights1(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
ll ans=0;
for(int i=0;i<M;i++)ans+=W[i];
return ans;
}
ll max_weights2(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
ll ans1=0,ans2=0;
for(int i=0;i<M;i++)
if(X[i]==0)ans1+=W[i];
else ans2+=W[i];
return max(ans1,ans2);
}
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
if(N<=300)return max_weights5(N,M,X,Y,W);
bool bl1=true,bl2=true;
for(int i=0;i<M;i++)
{if(X[i]%2)bl1=false;
if(X[i]>1)bl2=false;}
if(bl1)return max_weights1(N,M,X,Y,W);
if(bl2)return max_weights2(N,M,X,Y,W);
return max_weights7(N,M,X,Y,W);
}
Compilation message
fish.cpp: In function 'll max_weights5(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:31:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
31 | for(int i=0;i<=N;i++)
| ^~~
fish.cpp:33:8: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
33 | return ans;
| ^~~~~~
fish.cpp: In function 'll go7(int, int, int)':
fish.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<g[x].size();i++)
| ~^~~~~~~~~~~~
fish.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int j=0;j<g[x-1].size();j++)
| ~^~~~~~~~~~~~~~
fish.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int j=0;j<g[x].size();j++)
| ~^~~~~~~~~~~~
fish.cpp: In function 'll max_weights7(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0;i<g[0].size();i++)
| ~^~~~~~~~~~~~
fish.cpp:71:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
71 | for(int i=0;i<g[0].size();i++)
| ^~~
fish.cpp:73:8: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
73 | return ans;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
35 ms |
13312 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
94 ms |
20144 KB |
Output is correct |
| 6 |
Correct |
95 ms |
20172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14376 KB |
1st lines differ - on the 1st token, expected: '2', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
25 ms |
31572 KB |
Output is correct |
| 3 |
Correct |
70 ms |
31692 KB |
Output is correct |
| 4 |
Correct |
47 ms |
32852 KB |
Output is correct |
| 5 |
Correct |
88 ms |
35080 KB |
Output is correct |
| 6 |
Correct |
85 ms |
35116 KB |
Output is correct |
| 7 |
Correct |
97 ms |
35020 KB |
Output is correct |
| 8 |
Correct |
101 ms |
35048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
25 ms |
31572 KB |
Output is correct |
| 3 |
Correct |
70 ms |
31692 KB |
Output is correct |
| 4 |
Correct |
47 ms |
32852 KB |
Output is correct |
| 5 |
Correct |
88 ms |
35080 KB |
Output is correct |
| 6 |
Correct |
85 ms |
35116 KB |
Output is correct |
| 7 |
Correct |
97 ms |
35020 KB |
Output is correct |
| 8 |
Correct |
101 ms |
35048 KB |
Output is correct |
| 9 |
Correct |
90 ms |
35144 KB |
Output is correct |
| 10 |
Correct |
70 ms |
26484 KB |
Output is correct |
| 11 |
Correct |
181 ms |
38804 KB |
Output is correct |
| 12 |
Incorrect |
7 ms |
14292 KB |
1st lines differ - on the 1st token, expected: '4044', found: '0' |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
35 ms |
13312 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
94 ms |
20144 KB |
Output is correct |
| 6 |
Correct |
95 ms |
20172 KB |
Output is correct |
| 7 |
Incorrect |
7 ms |
14376 KB |
1st lines differ - on the 1st token, expected: '2', found: '0' |
| 8 |
Halted |
0 ms |
0 KB |
- |
