# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
626246 | 2022-08-11T10:28:24 Z | sword060 | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "fish.h" using namespace std; long long dp[100005],ar[100005]; long long rec(int i,bool f,int m){ if(i==m)return 0; if(~dp[i])return dp[i]; return dp[i]=max(rec(i+1,m)+ar[i+1],rec(i+1,m)+ar[i]); } long long max_weights(int x,int k,vector<int> a,vector<int> b,vector<int> c){ vector<pair<int,int>>l[2]; long long ans=0,cur=0,cur2=0; bool f=1; for(int i=0;i<k;i++){ l[a[i]%2].push_back({b[i],c[i]}); if(a[i]%2)cur+=c[i]; else cur2+=c[i]; f&=(b[i]==0); } if(f){ for(int i=0;i<x;i++)dp[i]=-1,ar[i]=0; for(int i=0;i<k;i++)ar[a[i]]+=c[i]; return rec(0,0,x); } sort(l[0].begin(),l[0].end()); sort(l[1].begin(),l[1].end()); ans=cur; if(x<=2){ return max(cur,cur2); } int j=0; for(int i=0;i<(int)l[0].size();i++){ cur+=l[0][i].second; while(j<(int)l[1].size()&&l[1][j].first<=l[0][i].first){ cur-=l[1][j].second; j++; } ans=max(ans,cur); } return ans; }