Submission #628879

#	Time	Username	Problem	Language	Result	Execution time	Memory
628879		dacin21	Catfish Farm (IOI22_fish)	C++17	100 / 100	240 ms	53188 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;
using ll = int64_t;

template<typename S, typename T>
void xmax(S&a, T const&b){
    if(b>a) a = b;
}

struct Fish{
    int y;
    ll w;
    ll left = 0, middle = 0, right = 0;
};
struct DP{
    vector<ll> up, down;
    ll zero_with = 0, zero_without = 0;
    ll next_zero_with = 0, next_zero_without = 0;
};

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<Fish> > ev(N+2);
    for(int i=0; i<M; ++i){
        ev[X[i]+1].push_back(Fish{Y[i], W[i]});
        ev[X[i]+1].push_back(Fish{Y[i]+1, 0});
    }
    for(auto &e : ev) {
        e.push_back(Fish{-1, 0});
        e.push_back(Fish{N+1, 0});
        sort(e.begin(), e.end(), [&](auto const&a, auto const&b){ return a.y < b.y; });
        e.erase(unique(e.begin(), e.end(), [&](auto &a, auto &b){
            if(a.y == b.y){
                a.w = b.w = a.w+b.w;
                return true;
            }
            return false;
        }), e.end());
        for(int i=1; i<(int)e.size(); ++i){
            e[i].middle = e[i-1].middle + e[i-1].w;
        }
    }
    for(int x=0; x<=N; ++x){
        auto &L = ev[x], &R = ev[x+1];
        int i = (int)L.size()-1, j = (int)R.size()-1;
        while(i >= 0 && j >= 0){
            auto &l = L[i], &r = R[j];
            if(l.y < r.y){
                r.left = l.middle;
                --j;
            } else if(l.y > r.y){
                l.right = r.middle;
                --i;
            } else {
                l.right = r.middle;
                r.left = l.middle;
                --i; --j;
            }
        }
    }
    DP prev;
    prev.up.assign(2, 0);
    prev.down.assign(2, 0);
    for(int x=1; x<=N+1; ++x){
        auto &you = ev[x-1];
        auto &me = ev[x];
        /* compute up: For each height
         *  - find best pred
         *  - add left
         *  - subtract me (due to next up)
         *  - check transform into down
         *
         * compute down: For each height
         *  - find best pred (or cur.up)
         *  - add right
         *  - subtract me (due to prev down)
         *  - check transform to zero.
         *
         */
        DP cur;
        cur.up.assign(me.size(), 0);
        cur.down.assign(me.size(), 0);
        /// compute up
        {
            int i = (int)you.size()-1, j = (int)me.size()-1;
            while(i >= 0 && j >= 0){
                if(you[i].y > me[j].y) --i;
                else {
                    cur.up[j] = prev.up[i];
                    --j;
                }
            }
        }
        // add left - middle
        // also consider the zero start
        for(int i=0; i<(int)me.size(); ++i){
            xmax(cur.up[i], prev.zero_without);
            cur.up[i] += me[i].left;
            xmax(cur.up[i], prev.zero_with);
            cur.up[i] -= me[i].middle;
        }
        /// update zeros
        cur.zero_with = prev.next_zero_with;
        cur.zero_without = prev.next_zero_without;
        /// compute down
        {
            // find best pred
            int i = 0, j = 0;
            while(i < (int)you.size() && j < (int)me.size()){
                if(you[i].y < me[j].y) ++i;
                else {
                    cur.down[j] = max(prev.down[i], cur.up[j] + 2*me[j].middle);
                    ++j;
                }
            }
        }
        // add right - middle
        // consider creating zeros
        for(int i = (int)me.size()-1; i > 0; --i){
            cur.down[i] -= me[i].middle;
            xmax(cur.next_zero_without, cur.down[i]);
            cur.down[i] += me[i].right;
            xmax(cur.next_zero_with, cur.down[i]);
        }
        /*cerr << "at: " << x << "\n";
        for(int i=0; i<(int)me.size(); ++i){
            auto &e = me[i];
            cerr << e.y << " " << e.w << " : " << e.left << " / " << e.middle << " / " << e.right << " : ";
            cerr << cur.up[i] << " | " << cur.down[i] << "\n";
        }*/
        /// turn values into prefix / suffic maxima
        // move up
        for(int i=1; i<(int)me.size(); ++i){
            xmax(cur.up[i], cur.up[i-1]);
        }
        // move down
        for(int i = (int)me.size()-1; i > 0; --i){
            xmax(cur.down[i-1], cur.down[i]);
        }
        prev = move(cur);
    }
    return max(prev.zero_with, prev.up[0]);
}

• 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