Submission #837876

#	Time	Username	Problem	Language	Result	Execution time	Memory
837876		Dremix10	Catfish Farm (IOI22_fish)	C++17	58 / 100	1082 ms	32376 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define pv(x) {}
#endif



long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    /// pier optimal options are below each fish in each column or full column
    /// dp[i][j][k], I am at column i with the following status:
    /// at column (i-1) the pier was built below fish j and above that the fish caught were k

    int i,j,k;

    vector<vector<pi> > col(n,vector<pi>());
    //p(1)
    for(i=0;i<m;i++){
        col[x[i]].push_back({y[i],w[i]});
    }

    for(i=0;i<n;i++){
        sort(all(col[i]));
    }

    vector<vector<ll> > best(n,vector<ll>()),eaten(n,vector<ll>());
    vector<ll> ans(n,-INF);
    //p(2)

    for(i=0;i<n;i++){
        //p(i) 
        int sz = col[i].size();
        best[i].assign(sz+1,-INF);
        eaten[i].assign(sz+1,-INF);
            
    }

    /// starting at i = 0 (base case)

    int sz = col[0].size();
    //p(3)
    ans[0] = 0;
    for(j=0;j<=sz;j++){

        best[0][j] = 0;
        eaten[0][j] = 0;
    }
    //p(4)
    p("go")
    for(i=1;i<n;i++){
        /// at column i with sz fish
        int sz = col[i].size();
        int sz1 = col[i-1].size();
        
        ll tot = 0;
        int p1 = 0;
        ans[i] = max(ans[i],ans[i-1]);

        for(j=0;j<sz;j++){
            p(j)
            int h = col[i][j].F-1;
            /// build pier up to h

            /// 2 cases: 

            /// (i-1) catches my fish

            int idx = j;
            ll sum = 0;
            best[i][j] = max(best[i][j],ans[i-1]);
            eaten[i][j] = max(eaten[i][j],ans[i-1]);
            

            for(k=0;k<sz1;k++){
                while(idx < sz && col[i][idx].F <= col[i-1][k].F-1){
                    sum += col[i][idx].S;
                    idx++;
                }
                ll temp = best[i-1][k] + sum;
                //p(temp)
                best[i][j] = max(best[i][j],temp);
                eaten[i][idx] = max(eaten[i][idx],temp);
                ans[i] = max(ans[i],temp);
            }

            /// case of full col
            while(idx < sz){
                sum += col[i][idx].S;
                idx++;
            }
            ll temp = best[i-1][k] + sum;
            best[i][j] = max(best[i][j],temp);
            eaten[i][idx] = max(eaten[i][idx],temp);
            ans[i] = max(ans[i],temp);


            /// I catch fish from (i-1)
            while(p1 < sz1 && col[i-1][p1].F <= h){
                tot += col[i-1][p1].S;
                p1++;
            }

            // I can get up to fish (p1-1)
            ll temp2 = tot;
            //p(j)

            for(k=0;k<p1;k++){
                /// I will get fish from {k,p1-1} (temp)

                /// i need best dp[i-1][o][oo] with o+oo == k
                //p(k)
                //p(temp2)
                ll temp = eaten[i-1][k] + temp2;
                //p(temp)
                best[i][j] = max(best[i][j],temp);
                eaten[i][j] = max(eaten[i][j],temp);
                ans[i] = max(ans[i],temp);

                temp2 -= col[i-1][k].S;
            }

        }

        /// case of full col
            
            /// build pier up to h
            best[i][j] = max(best[i][j],ans[i-1]);
            eaten[i][j] = max(eaten[i][j],ans[i-1]);
            /// 2 cases
            /// I catch fish from (i-1)
            while(p1 < sz1){
                tot += col[i-1][p1].S;
                p1++;
            }

            // I can get up to fish (p1-1)
            ll temp2 = tot;
            //p(temp2)
            //p(p1)
            for(k=0;k<p1;k++){
                /// I will get fish from {k,p1-1} (temp)

                /// i need best dp[i-1][o][oo] with o+oo == k
                
                ll temp = eaten[i-1][k] + temp2;
                //p(temp)
                best[i][j] = max(best[i][j],temp);
                eaten[i][j] = max(eaten[i][j],temp);
                ans[i] = max(ans[i],temp);

                temp2 -= col[i-1][k].S;
            }
        pv(best[i])
        pv(eaten[i])

    }

    // from last col
    pv(ans)

    return ans[n-1];
}

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