Submission #684671

#	Time	Username	Problem	Language	Result	Execution time	Memory
684671		79brue	메기 농장 (IOI22_fish)	C++17	100 / 100	368 ms	40764 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    ll tree[400002];

    void init(int i, int l, int r){
        tree[i] = -1e18;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            tree[i] = max(tree[i], v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    ll query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return -1e18;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} treeL, treeR;

struct Point{
    int x, y;
    ll w;
    Point(){}
    Point(int x, int y, ll w): x(x), y(y), w(w){}
    bool operator<(const Point &r)const{
        if(x != r.x) return x < r.x;
        return y<r.y;
    }
};

int n, k;
ll DP[300002][2];
ll sum[100005];
vector<Point> vec[100005];
vector<Point> checkL[100005], checkR[100005];
ll ans;

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    n = N, k = M;
    for(int i=0; i<k; i++){
        vec[X[i]+1].push_back(Point(X[i]+1, Y[i]+1, W[i]));
        sum[X[i]+1] += W[i];
    }
    for(int i=0; i<=n; i++){
        sort(vec[i].begin(), vec[i].end());
        DP[i][0] = DP[i][1] = -1e18;
    }

    treeL.init(1, 0, n+1);
    treeR.init(1, 0, n+1);
    treeL.update(1, 0, n+1, 0, 0);

    for(int i=1; i<=n; i++){
        /// Checklist
        for(Point p: checkL[i]) treeL.update(1, 0, n+1, 0, p.w);
        for(Point p: checkR[i]) treeR.update(1, 0, n+1, n+1, p.w);

        /// DP[?][0] -> DP[i][1]
        {
            for(Point p: vec[i-1]){ /// max 계산
                treeL.update(1, 0, n+1, p.y, treeL.query(1, 0, n+1, 0, p.y-1) + p.w);
            }
            ll v = treeL.query(1, 0, n+1, 0, n+1);
            DP[i][1] = max(DP[i][1], v);
        }

        /// DP[?][1] -> DP[i][1] (with gap)
        if(i >= 3){
            ll v = DP[i-2][1] + sum[i-1];
            DP[i][1] = max(DP[i][1], v);
        }

        /// DP[?][1] -> DP[i][1] (with no gap)
        if(i >= 2){
            ll v = DP[i-1][1];
            DP[i][1] = max(DP[i][1], v);
        }

        /// DP[?][1] -> DP[i][0]
        {
            reverse(vec[i].begin(), vec[i].end());
            for(Point p: vec[i]){
                treeR.update(1, 0, n+1, p.y, treeR.query(1, 0, n+1, p.y+1, n+1) + p.w);
            }
            reverse(vec[i].begin(), vec[i].end());
            ll v = treeR.query(1, 0, n+1, 0, n+1);
            DP[i][0] = max(DP[i][0], v);
        }

        checkR[i+1].push_back(Point(i+1, n+1, DP[i][1]));
        checkL[i+2].push_back(Point(i+2, 0, DP[i][0]));
        ans = max({ans, DP[i][0], DP[i][1]});

//        printf("%d: %lld %lld\n", i, DP[i][0], DP[i][1]);
    }

    return ans;
}

• 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