Submission #627119

#	Time	Username	Problem	Language	Result	Execution time	Memory
627119		CodePlatina	Catfish Farm (IOI22_fish)	C++17	6 / 100	303 ms	24716 KiB

fish

#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG

using namespace std;

const long long INF = (long long)1e18 + 7;

struct SEG
{
    int N;
    long long ind[202020];
    long long qry(int l, int r)
    {
        long long ret = 0;
        for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
        {
            if(x & 1) ret = max(ret, ind[x++]);
            if(y & 1) ret = max(ret, ind[--y]);
        }
        return ret;
    }
    void upd(int x, long long v)
    {
        x += N;
        ind[x] = max(ind[x], v);
        while(x >>= 1) ind[x] = max(ind[x << 1], ind[x << 1 | 1]);
    }
}dp[2];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
    vector<pii> A[N];
    for(int i = 0; i < M; ++i) A[X[i]].push_back({Y[i], W[i]});
    dp[0].N = dp[1].N = N + 1;
    for(int i = 0; i < N; ++i) sort(A[i].begin(), A[i].end());
    vector<pii> B[N];
    for(int i = 0; i < N; ++i) B[i] = A[i], reverse(B[i].begin(), B[i].end());

    for(int i = 1; i < N; ++i)
    {
        vector<pair<int, long long>> upd[2];
        long long ps = 0;
        for(auto [y, w] : A[i - 1])
        {
            ps = max(ps, dp[0].qry(0, y + 1)) + w;
            upd[0].push_back({y + 1, ps});
        }
        ps = 0;
        for(auto [y, w] : B[i])
        {
            ps = max(ps, dp[1].qry(y + 1, N + 1)) + w;
            upd[1].push_back({y, ps});
        }
        ps = 0;
        for(auto [y, w] : A[i])
        {
            ps += w;
            upd[0].push_back({y + 1, dp[1].qry(y + 1, N + 1) + ps});
        }
        upd[0].push_back({0, dp[1].qry(0, N + 1)});
        dp[1].upd(N, dp[0].qry(0, N + 1));
        for(auto [x, v] : upd[0]) dp[0].upd(x, v);
        for(auto [x, v] : upd[1]) dp[1].upd(x, v);

//        for(int i = 0; i <= N; ++i) cout << dp[0].qry(i, i + 1) << ' '; cout << endl;
//        for(int i = 0; i <= N; ++i) cout << dp[1].qry(i, i + 1) << ' '; cout << endl;
    }

    return max(dp[0].qry(0, N + 1), dp[1].qry(0, N + 1));
}

• Subtask 1: 0 / 3
• Subtask 2: 6 / 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