제출 #908678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
908678		vjudge1	메기 농장 (IOI22_fish)	C++17	100 / 100	181 ms	41844 KiB

fish

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

enum {
    UP = 0,
    DOWN = 1
};

ll max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<vector<pl>> fishes(N);
    F(i, 0, M) fishes[X[i]].push_back(make_pair(Y[i], i));
    vector<pl> up, down; // stores [ypos, dpvalue] of prev state
    vector<vl> dp(M, vl(2)); // dp[fish index][type]

    ll largest = 0; // arbitrary transition to previous state if far back enough??? [idk yet]

    F(x, 0, N) {
        if (x > 0) { 
            sort(A(fishes[x]), greater());
            ll max_down = 0, prev = 0;
            for (auto [y, i]: fishes[x]) {
                while (down.size() && down.back().K > y) {
                    max_down = max(max_down, down.back().V);
                    down.pop_back();
                }
                dp[i][DOWN] = max({largest, max_down, prev}) + W[i];
                prev = max(prev, dp[i][DOWN]);
            }
        }

        // i don't get why we have to do this here specifically?? 
        if (x >= 1) for (auto [y, i] : fishes[x - 1]) largest = max(largest, dp[i][DOWN]);

        if (x + 1 < N) {
            sort(A(fishes[x]));
            ll max_up = 0, prev = 0;
            for (auto [y, i]: fishes[x]) {
                while (up.size() && up.back().K < y) {
                    max_up = max(max_up, up.back().V);
                    up.pop_back();
                }
                dp[i][UP] = max({largest, max_up, prev}) + W[i];
                prev = max(prev, dp[i][UP]);
            }
        }

        if (x >= 1) for (auto [y, i] : fishes[x - 1]) largest = max(largest, dp[i][UP]);

        down.clear();
        sort(A(fishes[x]));
        for (auto [y, i]: fishes[x]) down.emplace_back(y, dp[i][DOWN]);

        up.clear();
        sort(A(fishes[x]), greater());
        for (auto [y, i]: fishes[x]) up.emplace_back(y, dp[i][UP]);
    }

    ll answer = 0;
    for (auto &x: dp) answer = max(*max_element(A(x)), answer);
    return answer;
}

• 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