제출 #1241424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241424		sano	메기 농장 (IOI22_fish)	C++20	23 / 100	175 ms	57928 KiB

fish

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

ll max_weights(int n2, int m2, vec<int> x, vec<int> y, vec<int> w1) {
    ll n = n2, m = m2;
    vec<vec<pii>> f(n);
    For(i, m) {
        f[x[i]].push_back({ y[i], i });
    }
    For(i, n) {
        f[i].resize(2, { NEK, m });
        sort(all(f[i]));
    }
    vec<vec<ll>> s(n);
    For(i, n) {
        s[i].resize(5, NEK);
        if (i != 0) {
            s[i][0] = f[i - 1][0].ff;
            s[i][1] = f[i - 1][1].ff;
        }
        if (i != (n - 1)) {
            s[i][2] = f[i + 1][0].ff;
            s[i][3] = f[i + 1][1].ff;
        }
        s[i][4] = -1;
    }
    vec<vec<vec<ll>>> dp(n + 1, vec<vec<ll>>(5, vec<ll>(5, 0)));
    For(j, 5) {
        if (s[n - 2][j] == NEK) continue;
        For(k, 5) {
            if (s[n - 1][k] == NEK) continue;
            int v1 = s[n - 2][j];
            int v0 = s[n - 1][k];
            int plus = 0;
            if (f[n - 1][0].ff > v0 && f[n - 1][0].ff <= v1) {
                plus += w1[f[n - 1][0].ss];
            }
            if (f[n - 1][1].ff > v0 && f[n - 1][1].ff <= v1) {
                plus += w1[f[n - 1][1].ss];
            }
            dp[n][j][k] = plus;
        }
    }
    rffor(i, 2, (n-1)) {
        For(j, 5) {
            if (s[i - 2][j] == NEK) continue;
            For(k, 5) {
                if (s[i - 1][k] == NEK) continue;
                For(l, 5) {
                    if (s[i][l] == NEK) continue;
                    ll v2 = s[i - 2][j];
                    ll v1 = s[i - 1][k];
                    ll v0 = s[i][l];
                    ll plus = 0;
                    if (f[i - 1][0].ff > v1 && f[i - 1][0].ff <= max(v0, v2)) {
                        plus += w1[f[i - 1][0].ss];
                    }
                    if (f[i - 1][1].ff > v1 && f[i - 1][1].ff <= max(v0, v2)) {
                        plus += w1[f[i - 1][1].ss];
                    }
                    dp[i][j][k] = max(dp[i][j][k], dp[i + 1][k][l] + plus);
                }
            }
        }
    }
    ll maxi = 0;
    For(j, 5) {
        if (s[0][j] == NEK) continue;
        For(k, 5) {
            if (s[1][k] == NEK) continue;
            int v0 = s[0][j];
            int v1 = s[1][k];
            int plus = 0;
            if (f[0][0].ff > v0 && f[0][0].ff <= v1) {
                plus += w1[f[0][0].ss];
            }
            if (f[0][1].ff > v0 && f[0][1].ff <= v1) {
                plus += w1[f[0][1].ss];
            }
            maxi = max(maxi, plus + dp[2][j][k]);
        }
    }
    return maxi;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vec<int> x(m), y(m), w(m);
    For(i, m) {
        cin >> x[i] >> y[i] >> w[i];
    }
    cout << max_weights(n, m, x, y, w) << '\n';
    return 0;
}*/

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