Submission #1277854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277854		danglayloi1	메기 농장 (IOI22_fish)	C++20	0 / 100	1097 ms	10676 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 1e18
using namespace std;
using ll = long long;
const ll mod=1e9+7;
struct segtree
{
    vector<ll> nod;
    void init(int n)
    {
        nod.assign(4*n+5, -inf);
    }
    void update(int id, int l, int r, int p, ll val)
    {
        if(l>p || r<p) return;
        if(l==r) return void(nod[id]=max(nod[id], val));
        int mid=(l+r)>>1;
        update(id<<1, l, mid, p, val);
        update(id<<1|1, mid+1, r, p, val);
        nod[id]=max(nod[id<<1], nod[id<<1|1]);
    }
    ll get(int id, int l, int r, int u, int v)
    {
        if(l>=u && r<=v) return nod[id];
        int mid=(l+r)>>1;
        if(v<=mid) return get(id<<1, l, mid, u, v);
        if(u>mid) return get(id<<1|1, mid+1, r, u, v);
        return max(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
    }
};
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
    vector<vector<ii>> ve;
    ve.assign(n, {});
    for(int i = 0; i < m; i++)
        ve[x[i]].emplace_back(y[i], w[i]);
    segtree seg_up, seg_down;
    seg_up.init(n+1);
    seg_down.init(n+1);
    ll zero=0;
    for(int i = 0; i < n; i++)
    {
        sort(ve[i].begin(), ve[i].end());
        vector<ll> dp_up, dp_down;
        for(auto it:ve[i])
        {
            dp_up.emplace_back(seg_up.get(1, 0, n, 0, it.fi-1)+it.se);
            dp_down.emplace_back(seg_down.get(1, 0, n, it.fi+1, n)+it.se);
        }
        seg_down.update(1, 0, n, n, max(seg_up.nod[1], zero));
        ll sum=0;
        for(int j = 0; j < dp_up.size(); j++)
        {
            sum+=ve[i][j].se;
            dp_up[j]=max(dp_up[j], zero+sum);
        }
        for(int j = 1; j < dp_up.size(); j++)
            dp_up[j]=max(dp_up[j], dp_up[j-1]+ve[i][j].se);
        sum=0;
        for(int j = 0; j < dp_up.size(); j++)
        {
            dp_up[j]=max(dp_up[j], dp_down[j]+sum);
            zero=max(zero, dp_down[j]+sum);
            sum+=ve[i][j].se;
        }
        for(int j = (int)dp_down.size()-2; j >= 0; j--)
            dp_down[j]=max(dp_down[j], dp_down[j+1]+ve[i][j].se);
        for(int j = 0; j < dp_up.size(); j++)
        {
            seg_up.update(1, 0, n, ve[i][j].fi, dp_up[j]);
            seg_down.update(1, 0, n, ve[i][j].fi, dp_down[j]);
        }
    }
    return max(zero, seg_down.nod[1]);
}
// int main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     cout<<max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3})<<'\n';
//     cout<<max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3});
// }

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