제출 #1240587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240587		sano	메기 농장 (IOI22_fish)	C++20	12 / 100	1010 ms	2162688 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<long double, long double>
#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;

    bool zle = 0;
    For(i, m) {
        if ((x[i] % 2) == 1) {
            zle = 1;
            break;
        }
    }
    if (!zle) {
        ll odp = 0;
        For(i, m) {
            odp += w1[i];
        }
        return odp;
    }
    zle = 0;
    For(i, m) {
        if (x[i] > 1) {
            zle = 1;
            break;
        }
    }
    if (!zle) {
        if (n == 2) {
            vec<ll>h(2, 0);
            For(i, m) {
                h[x[i]] += (ll)w1[i];
            }
            return max(h[0], h[1]);
        }
        else {
            vec<ll>h(2, 0);
            For(i, m) {
                h[x[i]] += (ll)w1[i];
            }
            ll roz = 0;
            vec<pii> p0, p1;
            For(i, m) {
                if (x[i] == 0) p0.push_back({ y[i], (ll)w1[i] });
                if (x[i] == 1) p1.push_back({ y[i], (ll)w1[i] });
            }
            sort(all(p0)); sort(all(p1));
            int som = 0;
            ll maxi = 0;
            For(i, p1.size()) {
                while (som < p0.size() && p0[som].ff <= p1[i].ff) {
                    roz += p0[som].ss;
                    som++;
                }
                roz -= p1[i].ss;
                maxi = max(maxi, roz);
            }
            return maxi + h[1];
        }
    }
    zle = 0;
    For(i, m) {
        if (y[i] != 0) {
            zle = 1;
            break;
        }
    }
    if (!zle) {
        vec<ll> dp1(n + 1, 0), dp2(n+1, 0);
        vec<ll> w(n);
        For(i, m) {
            w[x[i]] = w1[i];
        }
        rfor(i, n-1) {
            dp1[i] = max(dp1[i + 1], dp2[i+1] + w[i]);
            dp2[i] = max(dp1[i + 1], dp2[i+1]);
            if ((i + 2) <= n) {
                dp2[i] = max(dp2[i], dp1[i + 2] + w[i]);
            }
        }
        return dp2[0];
    }
    vec<vec<ll>> dp(n, vec<ll>(n));
    vec<vec<ll>> dp2(n, vec<ll>(n));
    vec<vec<ll>> w(n, vec<ll>(n, 0));
    For(i, m) {
        w[x[i]][y[i]] = w1[i];
    }
    vec<vec<ll>> dp_d(n, vec<ll>(n));
    For(k, n) {
        rfor(i, k) {
            For(j, n) {
                dp_d[i][j] = 0;
                //som v policku i, j chcem ist do stlpca k
                if (i == k) {
                    if (j == 0) {
                        dp_d[i][j] = w[i][j];
                        continue;
                    }
                    dp_d[i][j] = w[i][j] + dp_d[i][j - 1];
                    continue;
                }
                if (j == 0) {
                    dp_d[i][j] = dp_d[i + 1][j];
                    continue;
                }
                dp_d[i][j] = max(w[i][j] + dp_d[i][j - 1], dp_d[i + 1][j]);
            }
            dp[i][k] = dp_d[i][n - 1];
        }
    }

    For(k, n) {
        rfor(i, k) {
            rfor(j, n-1) {
                dp_d[i][j] = 0;
                //som v policku i, j chcem ist do stlpca k
                if (i == k) {
                    if (i != 0) {
                        dp_d[i][j] = w[i - 1][n - 1];
                        continue;
                    }
                    dp_d[i][j] = 0;
                    continue;
                }
                if ((j+1) == n) {
                    dp_d[i][j] = dp_d[i + 1][j];
                    continue;
                }
                dp_d[i][j] = max(w[i][j] + dp_d[i][j + 1], dp_d[i + 1][j]);    
            }
            dp2[i][k] = dp_d[i][0];
        }
    }
    vec<ll> ndp0(n + 1, 0), ndp1(n + 1, 0);
    rfor(i, n - 2) {
        //som na stlpci i, stlpce po i-1 su vybavane s tym ze stlpec i musi byt 0 pre ndp0, a  n pre ndp1;
        //posuniem sa hned na to dalsie policko
        ndp1[i] = max(ndp1[i], ndp1[i + 2] + dp[i + 1][i + 1]);
        for (ll j = i + 1; j < n; j++) {
            ndp1[i] = max(ndp1[i], ndp0[j + 1] + dp[i + 1][j]);
        }
        for (ll j = i + 1; j < n; j++) {
            ndp0[i] = max(ndp0[i], ndp1[j] + dp2[i][j]);
        }
    }
    return max(ndp1[0], ndp0[0]);
}
/*
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: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16