Submission #1313499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313499		kookeudas	Catfish Farm (IOI22_fish)	C++20	100 / 100	119 ms	38496 KiB

fish

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
int n,m;
vector<ll> d[100002][2];
ll d2[100002];
vector<pair<int,ll>> mv[100002];
int ii(int i, int x){
    return lower_bound(mv[i].begin(),mv[i].end(),make_pair(x,-(ll)1))-mv[i].begin();
}
int ii2(int i, int x){
    return lower_bound(mv[i].begin(),mv[i].end(),make_pair(x+1,-(ll)1))-mv[i].begin()-1;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
    n = N,m = M;
    for(int i=0;i<m;i++){
        X[i]++;
        Y[i]++;
        mv[X[i]].push_back({Y[i],W[i]});
    }
    for(int i=0;i<=n;i++)mv[i].push_back({0,0});
    for(int i=1;i<=n;i++)sort(mv[i].begin(),mv[i].end());
    for(int i=0;i<=n;i++)d2[i] = -1e18;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=mv[i].size();j++){
            d[i][0].push_back(-1e18);
            d[i][1].push_back(-1e18);
        }
    }
    d[0][0].push_back(-1e18);
    d[0][0].push_back(-1e18);
    d[0][1].push_back(-1e18);
    d[0][1].push_back(-1e18);
    //d[0][0][0] = 0;
    d[0][1][0] = 0;
    for(int i=1;i<=n;i++){
        d[i][0][(int)mv[i].size()-1] = max({d[i][0][(int)mv[i].size()-1],d2[i-1]+mv[i].back().second,d[i-1][0][ii(i-1,mv[i].back().first+1)]+mv[i].back().second});
        for(int j=(int)mv[i].size()-2;j>=0;j--){
            d[i][0][j] = max({d[i][0][j],d[i][0][j+1]+mv[i][j].second,d[i-1][0][ii(i-1,mv[i][j].first+1)]+mv[i][j].second});
        }
        d2[i] = max(d2[i-1],d[i-1][1][(int)mv[i-1].size()-1]);
        d[i][1][0] = max({d2[i-1],d[i-1][0][0]});
        for(int j=1;j<mv[i].size();j++){
            d[i][1][j] = max({d[i][1][j],d[i][1][j-1]+mv[i][j].second,d[i-1][1][ii2(i-1,mv[i][j].first-1)]+mv[i][j].second});
        }
    }
    ll ret = max({d2[n],d[n][0][0]});
    return ret;
}

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