Submission #1230592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230592		CELD_07	Catfish Farm (IOI22_fish)	C++20	53 / 100	171 ms	74740 KiB

fish

#include "fish.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) //cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w){
vector<vector<pair<ll, ll>>> v(n+1), dp(n+1), dp1;
vector<vector<ll>> dp2(n+1), dp3(n+1), dp4(n+1);
vector<ll> dp5(n+1, 0);
ll res2=0, res3=0;
for(int i=0; i<m; i++){
v[x[i]].push_back({y[i], w[i]});
res3+=w[i];
}
for(int i=0; i<n; i++){
if(i!=0){
for(auto& [x1, y1]: v[i-1])dp[i].push_back({x1, 0});
}
if(i!=n-1){
for(auto& [x1, y1]: v[i+1])dp[i].push_back({x1, 0});
}
}
for(int i=0; i<=n; i++){
if(!v[i].empty()){
sort(all(v[i]));
}
if(!dp[i].empty()){
sort(all(dp[i]));
dp[i].erase(unique(all(dp[i])), dp[i].end());
}
}

dp1=dp;
for(int i=0; i<n ;i++){
if(i!=0)dp5[i]=max(dp5[i], dp5[i-1]);
if(dp[i].empty())continue;
ll l=0, l1=0, l2=0, sum=0, sum1=0, sum2=0;
for(int j=0; j<dp[i].size(); j++){
while(l<v[i+1].size() && v[i+1][l].ft<=dp[i][j].ft){sum+=v[i+1][l].sd;l++;}
while(l1<v[i].size() && v[i][l1].ft<=dp[i][j].ft){sum1+=v[i][l1].sd;l1++;}
if(i!=0)while(l2<v[i-1].size() && v[i-1][l2].ft<=dp[i][j].ft){sum2+=v[i-1][l2].sd;l2++;}
dp2[i].push_back(sum);
dp3[i].push_back(sum1);
dp4[i].push_back(sum2);
}
for(int j=0; j<dp[i].size(); j++)dp5[i]=max(dp5[i], dp4[i][j]+dp2[i][j]);
if(i==0)continue;
//for(int k=0; k<dp[i].size(); k++){db(dp[i][k].sd)db(dp[i][k].ft) db(dp3[i][k])}
l=dp[i-1].size(), sum=0;
l--;
for(int j=dp[i].size()-1; j>=0; j--){
while(l>=0 && dp[i-1][l].ft>=dp[i][j].ft){
sum=max(sum, dp[i-1][l].sd+dp2[i-1][l]);
l--;
}
dp[i][j].sd=max(dp[i][j].sd, sum-dp3[i][j]);
dp[i][j].sd=max(dp[i][j].sd, dp4[i][j]);
dp1[i][j].sd=max(dp1[i][j].sd, dp4[i][j]);

}
l=0, sum=0;
for(int j=0; j<dp[i].size(); j++){
while(l<dp[i-1].size() && dp[i-1][l].ft<=dp[i][j].ft){
sum=max(sum, dp1[i-1][l].sd-dp3[i-1][l]);
l++;
}
dp1[i][j].sd=max(sum+dp4[i][j], dp1[i][j].sd);
//res2=max({res2, dp[i][j].sd+dp2[i][j], dp1[i][j].sd+dp2[i][j]});
}
if(i>=2){
    ll o=0;
    l=0;
    for(int j=0; j<dp[i].size(); j++){
    while(l<dp[i-2].size() && dp[i-2][l].ft<=dp[i][j].ft){o=max({o, dp[i-2][l].sd, dp1[i-2][l].sd});l++;}
    dp[i][j].sd=max(dp[i][j].sd, o+dp4[i][j]);
    dp1[i][j].sd=max(dp1[i][j].sd, o+dp4[i][j]);
    }
    l=dp[i-2].size();
    l--;
    o=0;
    for(int j=dp[i].size()-1; j>=0; j--){
    while(l>=0 && dp[i-2][l].ft>=dp[i][j].ft){o=max({o, dp[i-2][l].sd+dp2[i-2][l], dp1[i-2][l].sd+dp2[i-2][l]});l--;}
    dp[i][j].sd=max(dp[i][j].sd, o);
    dp1[i][j].sd=max(dp1[i][j].sd, o);
    //res2=max({res2, dp[i][j].sd+dp2[i][j], dp1[i][j].sd+dp2[i][j]});
    }
}
if(i>=3){
  ll o=0;
    o=dp5[i-3];
   // cout<<i<<" "<<o<<endl;
    for(int j=0; j<dp[i].size(); j++){
    dp[i][j].sd=max(dp[i][j].sd, o+dp4[i][j]);
    dp1[i][j].sd=max(dp1[i][j].sd, o+dp4[i][j]);
    }
}
for(int j=0; j<dp[i].size(); j++){
dp5[i]=max(dp5[i], max(dp[i][j].sd, dp1[i][j].sd)+dp2[i][j]);
}

//cout<<i<<" "<<dp5[i]<<endl;
}
for(int i=0; i<n; i++){
res2=max(res2, dp5[i]);
}
return res2;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16