Submission #674902

#	Time	Username	Problem	Language	Result	Execution time	Memory
674902		PoonYaPat	Catfish Farm (IOI22_fish)	C++17	84 / 100	1044 ms	64272 KiB

fish

#include "fish.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

vector<pii> fish[100001]; //row,value
vector<pii> pos; //find find -> x,y
ll sum_in[600010],sum_left[600010],sum_right[600010],dp[600010][2],mmax[100001]; //0-decreasing, 1-increasing
multiset<ll, greater<ll>> pre1_high, pre1_low, pre2_high, pre2_low;
int start_col[100001],end_col[100001];

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {

    memset(start_col,-1,sizeof(start_col));
    memset(end_col,-1,sizeof(end_col));

    for (int i=0; i<m; ++i) {
        fish[X[i]].push_back(pii(Y[i],W[i]));
        if (X[i]) pos.push_back(pii(X[i]-1,Y[i]));
        if (X[i]<n-1) pos.push_back(pii(X[i]+1,Y[i]));
    }

    for (int i=0; i<n; ++i) {
        sort(fish[i].begin(),fish[i].end());
        for (int j=1; j<fish[i].size(); ++j) fish[i][j].second=fish[i][j].second+fish[i][j-1].second;
    }

    sort(pos.begin(),pos.end());
    int k=pos.size(),pre_col=-1;
    for (int i=0; i<k; ++i) {
        if (pos[i].first!=pre_col) {
            start_col[pos[i].first]=i;
            pre_col=pos[i].first;
        }
        end_col[pos[i].first]=i;
    }

    for (int i=0; i<k; ++i) {
        int x=pos[i].first, y=pos[i].second;

        //sum_in
        auto it=upper_bound(fish[x].begin(),fish[x].end(),pii(y,LLONG_MAX));
        if (it==fish[x].begin()) sum_in[i]=0;
        else sum_in[i]=(*(--it)).second;

        //sum_left
        if (x) {
            it=upper_bound(fish[x-1].begin(),fish[x-1].end(),pii(y,LLONG_MAX));
            if (it==fish[x-1].begin()) sum_left[i]=0;
            else sum_left[i]=(*(--it)).second;
        } else sum_left[i]=0;

        //sum_right
        if (x<n-1) {
            it=upper_bound(fish[x+1].begin(),fish[x+1].end(),pii(y,LLONG_MAX));
            if (it==fish[x+1].begin()) sum_right[i]=0;
            else sum_right[i]=(*(--it)).second;
        } else sum_right[i]=0;
    }

    for (int i=0; i<n; ++i) {
        if (start_col[i]!=-1) {
            //reset
            pre1_high.clear();
            pre2_high.clear();
            pre1_low.clear();
            pre2_low.clear();

            int idx1,idx2;

            if (i>0 && start_col[i-1]!=-1) {
                for (int j=start_col[i-1]; j<=end_col[i-1]; ++j) {
                    pre1_high.insert(dp[j][0]);
                    pre1_high.insert(dp[j][1]);
                }
                idx1=start_col[i-1];
            } else idx1=INT_MAX;

            if (i>1 && start_col[i-2]!=-1) {
                for (int j=start_col[i-2]; j<=end_col[i-2]; ++j) {
                    pre2_high.insert(dp[j][0]);
                    pre2_high.insert(dp[j][1]);
                }
                idx2=start_col[i-2];
            } else idx2=INT_MAX;

            for (int idx=start_col[i]; idx<=end_col[i]; ++idx) {
                    //find dp[idx][0], dp[idx][1]
                if (i>=3) {
                    dp[idx][0]=sum_left[idx]+sum_right[idx]+mmax[i-3];
                    dp[idx][1]=sum_left[idx]+sum_right[idx]+mmax[i-3];
                } else {
                    dp[idx][0]=sum_left[idx]+sum_right[idx];
                    dp[idx][1]=sum_left[idx]+sum_right[idx];
                }

                while (idx1<=end_col[i-1] && pos[idx1].second<=pos[idx].second) { //go to lower
                    pre1_high.erase(pre1_high.find(dp[idx1][0]));
                    pre1_high.erase(pre1_high.find(dp[idx1][1]));
                    pre1_low.insert(dp[idx1][1]-sum_in[idx1]-sum_right[idx1]);
                    ++idx1;
                }

                while (idx2<=end_col[i-2] && pos[idx2].second<=pos[idx].second) { //go to lower
                    pre2_high.erase(pre2_high.find(dp[idx2][0]));
                    pre2_high.erase(pre2_high.find(dp[idx2][1]));
                    pre2_low.insert(dp[idx2][0]-sum_right[idx2]);
                    pre2_low.insert(dp[idx2][1]-sum_right[idx2]);
                    ++idx2;
                }

                if (pre1_high.size()) {
                    dp[idx][0]=max(dp[idx][0],*(pre1_high.begin())-sum_in[idx]+sum_right[idx]);
                }

                if (pre1_low.size()) {
                    dp[idx][1]=max(dp[idx][1],*(pre1_low.begin())+sum_left[idx]+sum_right[idx]);
                }

                if (pre2_high.size()) {
                    dp[idx][0]=max(dp[idx][0],*(pre2_high.begin())+sum_right[idx]);
                    dp[idx][1]=max(dp[idx][1],*(pre2_high.begin())+sum_right[idx]);
                }

                if (pre2_low.size()) {
                    dp[idx][0]=max(dp[idx][0],*(pre2_low.begin())+sum_left[idx]+sum_right[idx]);
                    dp[idx][1]=max(dp[idx][1],*(pre2_low.begin())+sum_left[idx]+sum_right[idx]);
                }

                mmax[i]=max({mmax[i],dp[idx][0],dp[idx][1]});

            }
        }
        mmax[i]=max(mmax[i],mmax[i-1]);
    }
    return mmax[n-1];
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:27:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int j=1; j<fish[i].size(); ++j) fish[i][j].second=fish[i][j].second+fish[i][j-1].second;
      |                       ~^~~~~~~~~~~~~~~

• 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: 0 / 16