#include<bits/stdc++.h>
#define MAXN 100007
#define MAXM 300007
using namespace std;
int n,m;
int x[MAXM],y[MAXM],w[MAXM];
vector< pair<int,long long> > poss[MAXN],all[MAXN];
vector<long long> dp[MAXN][2][2];
vector<bool> li[MAXN][2][2];
long long ff(int n,int flag,int flag2,int last){
if(n==-1)return 0;
if(li[n][flag][flag2][last])return dp[n][flag][flag2][last];
li[n][flag][flag2][last]=true;
dp[n][flag][flag2][last]=-1000000000000000;
long long sum=0,sum2=0;
int pt=0,from=0;
if(flag==0){
for(int i=0;i<poss[n].size();i++){
if(poss[n][i].first<=all[n+1][last].first){
sum+=poss[n][i].second;
}else break;
}
if(n>=1)dp[n][flag][flag2][last]=max( ff(n-1,0,0,0)+sum , ff(n-1,1,1,last) );
else dp[n][flag][flag2][last]=ff(n-1,0,0,0)+sum;
for(int i=0;i<all[n].size() and all[n][i].first<=all[n+1][last].first;i++){
while(pt<poss[n].size() and poss[n][pt].first<=all[n][i].first){
sum-=poss[n][i].second; pt++;
}
dp[n][flag][flag2][last]=max(dp[n][flag][flag2][last],ff(n-1,0,0,i)+sum);
}
}else{
while(from<all[n].size() and all[n][from].first<all[n+1][last].first)from++;
if(flag2==1){
for(int i=0;i<poss[n+1].size();i++){
if(poss[n+1][i].first<all[n+2][last].first)sum2+=poss[n+1][i].first;
}
}
for(int i=from;i<all[n].size();i++){
while(pt<poss[n+1].size() and poss[n+1][pt].first<=all[n][i].first){
if(poss[n+1][pt].first>all[n+1][last].first)sum+=poss[n+1][pt].second;
pt++;
}
if(flag2==0){
dp[n][flag][flag2][last]=max(ff(n-1,1,0,i)+sum,ff(n-1,0,0,i)+sum);
}else{
dp[n][flag][flag2][last]=max(ff(n-1,1,0,i)+max(sum,sum2),ff(n-1,0,0,i)+max(sum,sum2));
}
}
}
return dp[n][flag][flag2][last];
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n=N; m=M;
for(int i=0;i<m;i++){
x[i+1]=X[i]; y[i+1]=Y[i]; w[i+1]=W[i];
}
for(int i=1;i<=m;i++){
poss[x[i]].push_back({y[i],w[i]});
//if(x[i]-1>=0)all[x[i]-1].push_back({y[i],w[i]});
//if(x[i]+1<n)all[x[i]+1].push_back({y[i],w[i]});
}
for(int i=0;i<n;i++){
for(int f=0;f<n;f++){
all[i].push_back({f,0});
}
}
for(int i=0;i<n;i++){
for(int f=0;f<2;f++){
for(int k=0;k<n;k++){
for(int p=0;p<n;p++){
dp[i][f][k].push_back(0);
li[i][f][k].push_back(false);
}
}
}
}
for(int i=0;i<n;i++){
poss[i].push_back({-1,0});
all[i].push_back({-1,0});
sort(poss[i].begin(),poss[i].end());
sort(all[i].begin(),all[i].end());
}
all[n].push_back({-1,0});
return max(ff(n-1,1,0,0),ff(n-1,0,0,0));
}
/*
int main(){
cout<<max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3})<<"\n";
return 0;
}
*/
Compilation message
fish.cpp: In function 'long long int ff(int, int, int, int)':
fish.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i=0;i<poss[n].size();i++){
| ~^~~~~~~~~~~~~~~
fish.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i=0;i<all[n].size() and all[n][i].first<=all[n+1][last].first;i++){
| ~^~~~~~~~~~~~~~
fish.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | while(pt<poss[n].size() and poss[n][pt].first<=all[n][i].first){
| ~~^~~~~~~~~~~~~~~
fish.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(from<all[n].size() and all[n][from].first<all[n+1][last].first)from++;
| ~~~~^~~~~~~~~~~~~~
fish.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<poss[n+1].size();i++){
| ~^~~~~~~~~~~~~~~~~
fish.cpp:47:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=from;i<all[n].size();i++){
| ~^~~~~~~~~~~~~~
fish.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | while(pt<poss[n+1].size() and poss[n+1][pt].first<=all[n][i].first){
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1140 ms |
765384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
30036 KB |
Output is correct |
| 2 |
Execution timed out |
1129 ms |
798296 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1136 ms |
912876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
30036 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
30040 KB |
1st lines differ - on the 1st token, expected: '7', found: '11' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
30036 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
30040 KB |
1st lines differ - on the 1st token, expected: '7', found: '11' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
30036 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
30040 KB |
1st lines differ - on the 1st token, expected: '7', found: '11' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1136 ms |
912876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1140 ms |
765384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
