Submission #1277705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277705		baotoan655	메기 농장 (IOI22_fish)	C++20	100 / 100	108 ms	32096 KiB

fish

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

//#ifdef ONLINE_JUDGE
#include "fish.h"
//#endif // ONLINE_JUDGE

const long long INF = 1e16;

long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<pair<int, int>>> f(n);
    vector<int> sz(n);
    vector<vector<long long>> dp_up(n), dp_down(n);
    for(int i = 0; i < n; ++i) f[i].emplace_back(0, 0);
    for(int i = 0; i < m; ++i) f[X[i]].emplace_back(Y[i], W[i]);
    for(int i = 0; i < n; ++i) f[i].emplace_back(n, 0);
    for(int i = 0; i < n; i++) {
        sort(f[i].begin(), f[i].end());
        sz[i] = f[i].size();
        dp_down[i].assign(sz[i], 0);
        dp_up[i].assign(sz[i], 0);
    }
    long long ans = 0;
    for(int i = 1; i < n; i++) {
        long long mx = 0;
        for(long long x : dp_up[i - 1]) {
            mx = max(mx, x);
        }
        for(long long x : dp_down[i - 1]) {
            mx = max(mx, x);
        }
        long long val_up = 0;
        int k = 0;
        for(int j = 0; j < sz[i]; j++) {
            while(k < sz[i - 1] && f[i - 1][k].first < f[i][j].first) {
                val_up = max(val_up, dp_up[i - 1][k]);
                val_up += f[i - 1][k].second;
                k++;
            }
            dp_up[i][j] = max(dp_up[i][j], max(mx, val_up));
        }
        long long val_down = 0;
        k = sz[i - 1] - 1;
        for(int j = sz[i] - 1; j >= 0; j--) {
            while(k >= 0 && f[i - 1][k].first > f[i][j].first) {
                val_down = max(val_down, dp_up[i - 1][k]);
                val_down = max(val_down, dp_down[i - 1][k]);
                k--;
            }
            val_down += f[i][j].second;
            dp_down[i][j] = max(dp_down[i][j], max(mx, val_down));
        }
    }
    for(long long j = 0; j < sz[n - 1]; j++) {
        ans = max({ans, dp_up[n - 1][j], dp_down[n - 1][j]});
    }
    return ans;
}

//#ifndef ONLINE_JUDGE
//
//int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0), cout.tie(0);
//
////    file("A") else file("task");
//    cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << '\n';
//    return 0;
//}
//
//#endif

• 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