Submission #831536

#TimeUsernameProblemLanguageResultExecution timeMemory
831536MrDebooCatfish Farm (IOI22_fish)C++17
23 / 100
1092 ms167324 KiB
#include "fish.h" #include "bits/stdc++.h" #define int long long using namespace std; map<pair<int,pair<int,int>>,int>dp; map<int,int>vct[200000]; vector<int>v[200000]; int N; int slv(int a,int b,int c){ if(a==N)return 0; if(dp.count({a,{b,c}}))return dp[{a,{b,c}}]; // cerr<<a<<' '<<b<<endl; int mx=0; int tot=0; for(auto &i:v[a]){ if(i<=b&&vct[a].count(i))tot-=vct[a][i]; if(i>max(b,c)&&vct[a-1].count(i))tot+=vct[a-1][i]; if(vct[a+1].count(i))tot+=vct[a+1][i]; mx=max(mx,slv(a+1,i,b)+tot); } return dp[{a,{b,c}}]=mx; } long long max_weights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y, std::vector<int32_t> w) { N=n; for(int i=0;i<=n;i++)v[i].push_back(0); for(int i=0;i<m;i++){ vct[x[i]][y[i]+1]=w[i]; if(x[i])v[x[i]-1].push_back(y[i]+1); v[x[i]].push_back(y[i]+1); v[x[i]+1].push_back(y[i]+1); } for(int i=0;i<=n;i++)sort(v[i].begin(),v[i].end()); for(int i=0;i<=n;i++)v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin()); return slv(0,0,0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...