제출 #1127015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127015		bruh	메기 농장 (IOI22_fish)	C++20	32 / 100	1134 ms	1592548 KiB

fish

#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()

using namespace std;
const ll maxn = 3e5 + 5;
ll n, m, ans;
array<ll, 3> a[maxn];

inline void MAX(ll &a, ll b)
{
    a = max(a, b);
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
    n = N;
    m = M;
    ll sub1 = 1, sub2 = 1, sub3 = 1;
    for (ll i = 1; i <= m; i++)
    {
//        cin >> a[i][0] >> a[i][1] >> a[i][2];
        a[i][0] = X[i - 1];
        a[i][1] = Y[i - 1];
        a[i][2] = W[i - 1];
        sub1 &= a[i][0] % 2 == 0;
        sub2 &= a[i][0] <= 1;
        sub3 &= a[i][1] == 0;
    }
    if (sub1)
    {
        ll ans = 0;
        for (ll i = 1; i <= m; i++)
            ans += a[i][2];
        return ans;
        cout << ans;
    } else if (sub2)
    {
        vector<pair<ll,ll>> val[2];
        for (ll i = 1; i <= m; i++)
            val[a[i][0]].emplace_back(a[i][1], a[i][2]);
        sort(all(val[0]));
        sort(all(val[1]));
        vector<ll> pf[2];
        pf[0].assign(n + 5, 0);
        pf[1].assign(n + 5, 0);
        for (ll i = 1; i <= val[0].size(); i++)
            pf[0][i] = pf[0][i - 1] + val[0][i - 1].second;
        for (ll i = 1; i <= val[1].size(); i++)
            pf[1][i] = pf[1][i - 1] + val[1][i - 1].second;
        ll ans = max(pf[0][val[0].size()], pf[1][val[1].size()]);
        for (ll i = 1, pt = -1; i <= val[1].size(); i++)
        {
            ll height = val[1][i - 1].first - 1;
            ll cur = (n > 2 ? pf[1][val[1].size()] - pf[1][i - 1] : 0);
            while (pt + 1 < val[0].size() && val[0][pt + 1].first <= height)
                pt++;
            cur += pf[0][pt + 1];
            ans = max(ans, cur);
        }
        for (ll i = 1, pt = -1; i <= val[0].size(); i++)
        {
            ll height = val[0][i - 1].first - 1;
            ll cur = 0;
            while (pt + 1 < val[1].size() && val[1][pt + 1].first <= height)
                pt++;
            cur += pf[1][pt + 1];
            ans = max(ans, cur);
        }
        return ans;
        cout << ans;
    } else if (sub3)
    {
        vector<ll> b(n + 10, 0), dp(n + 10, 0);
        for (ll i = 1; i <= m; i++)
            b[a[i][0] + 1] = a[i][2];
        ll ans = 0;
        for (ll i = 1; i <= n; i++)
        {
            /// choose i
            dp[i] = b[i - 1] + b[i + 1];
            for (ll j = 3; j <= 50; j++) if (i - j >= 1)
                dp[i] = max(dp[i], dp[i - j] + b[i + 1] + b[i - 1]);
            else break;
            if (i >= 2)
                dp[i] = max(dp[i], dp[i - 1] - b[i] + b[i + 1]);
            if (i >= 3)
                dp[i] = max(dp[i], dp[i - 2] + b[i + 1]);
            ans = max(ans, dp[i]);
        }
        return ans;
        cout << ans;
    } else
    {
        vector<vector<ll>> b(n + 10, vector<ll>(n + 10, 0));
        ll mx = 0;
        for (ll i = 1; i <= m; i++)
            b[a[i][0] + 1][a[i][1] + 1] = a[i][2],
            mx = max(mx, a[i][1] + 1);
        vector<vector<ll>> pf(n + 10, vector<ll>(mx + 2, 0));
        vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(mx + 1, vector<ll>(mx + 2, 0)));
        for (ll i = 1; i <= n; i++)
        {
            for (ll j = 1; j <= mx; j++)
                pf[i][j] = pf[i][j - 1] + b[i][j];
        }
        for (ll j = 0; j <= mx; j++) for (ll i = 0; i <= mx; i++)
            dp[0][i][j] = -1e18;
        dp[0][0][0] = 0;
        ll be = 0, cu = 1;
        for (ll i = 1; i <= n + 2; i++)
        {
            for (ll u = 0; u <= mx; u++) for (ll v = 0; v <= mx; v++)
                dp[cu][u][v] = -1e18;
            for (ll pre = 0; pre <= mx; pre++)
                for (ll now = 0; now <= mx; now++) if (dp[be][pre][now] != -1e18)
                    for (ll nxt = 0; nxt <= mx; nxt++)
                    {
                        if (now >= nxt)
                        {
                            MAX(dp[cu][now][nxt], dp[be][pre][now] + pf[i][now] - pf[i][nxt]);
                        } else
                        {
                            if (nxt >= max(pre, now))
                                MAX(dp[cu][now][nxt], dp[be][pre][now] + pf[i - 1][nxt] - pf[i - 1][max(pre, now)]);
                        }
                    }
            swap(be, cu);
//            for (ll u = 0; u <= n; u++) for (ll v = 0; v <= n; v++)
//                if (dp[be][u][v] != -1e18)
//                    cout << i << " " << u << " " << v << " " << dp[be][u][v] << " ?\n";
        }
        return dp[be][0][0];
        cout << dp[be][0][0];

    }
}

//signed main()
//{
//    ios_base::sync_with_stdio(false);
//    cin.tie(0); cout.tie(0);
////    freopen("CATFISH.inp", "r", stdin);
////    freopen("CATFISH.out", "w", stdout);
//
//}
//

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