Submission #720024

#	Time	Username	Problem	Language	Result	Execution time	Memory
720024		HaiHoang	메기 농장 (IOI22_fish)	C++17	32 / 100	87 ms	10860 KiB

fish

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()

#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
const int MAXN = 1e5 + 5;
namespace sub1 {
    bool check(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        REP(i, M) if(X[i] % 2 == 1) return false;
        return true;
    }
    long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        long long ans = 0;
        REP(i, M) ans += W[i];
        return ans;
    }
}
namespace sub2 {
    long long pre[2][MAXN];
    bool check(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        REP(i, M) if(X[i] > 1) return false;
        return true;
    }
    long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        long long ans = 0;
        REP(i, M) pre[X[i]][Y[i]] += W[i];
        FOR(i, 1, N - 1) {
            pre[0][i] += pre[0][i - 1];
            pre[1][i] += pre[1][i - 1];
        }
        ans = max(pre[0][N - 1], pre[1][N - 1]);
        if(N == 2) return ans;
        REP(i, N) {
            long long val = pre[1][N - 1] - pre[1][i];
            maximize(ans, val + pre[0][i]);
        }
        return ans;
    }
}
namespace sub3 {
    bool check (int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        REP(i, M) if(Y[i]) return false;
        return true;
    }
    long long dp[MAXN][2][2], a[MAXN];
    long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        long long ans = 0;
        REP(i, M) a[X[i] + 1] += W[i];
        FOR(i, 1, N) {
            dp[i][1][0] = max({dp[i - 1][0][0] + a[i - 1] + a[i + 1], dp[i - 1][0][1] + a[i + 1], dp[i - 1][1][0] - a[i] + a[i + 1]});
            dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][0][1]);
            dp[i][0][1] = dp[i - 1][1][0];
            maximize(ans, dp[i][1][0]);
            maximize(ans, dp[i][0][0]);
            maximize(ans, dp[i][0][1]);
            // cout << dp[i][1][0] << " \n"[i == N];
        }
        return ans;
    }
}
namespace sub4 {
    bool check (int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        if(N > 300) return false;
        REP(i, M) if(Y[i] > 8) return false;
        return true;
    }
    long long dp[MAXN][10][10], pre[MAXN][10];
    long long get(int x, int l, int r) { if(l > r) return 0; return pre[x][r] - pre[x][l - 1]; }
    long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
        long long ans = 0;
        int lim = min(9, N + 1);
        REP(i, M) pre[X[i] + 1][Y[i] + 1] += W[i];
        FOR(i, 1, N) FOR(j, 1, lim - 1) pre[i][j] += pre[i][j - 1];
        FOR(i, 2, N) REP(l1, lim) REP(l2, lim) REP(l3, lim) {
            long long val = 0, val2 = 0;
            if(l2 < l3) val = get(i - 1, l2 + 1, l3);
            else val = get(i, l3 + 1, l2);
            if(l1 > l2 && l2 < l3) {
                if(l1 < l3) maximize(dp[i][l2][l3], dp[i - 1][l1][l2] + get(i - 1, l1 + 1, l3));
                else maximize(dp[i][l2][l3], dp[i - 1][l1][l2]);
            }
            else maximize(dp[i][l2][l3], dp[i - 1][l1][l2] + val);
            maximize(ans, dp[i][l2][l3]);

        }
        // FOR(i, 1, N) FOR(j, 1, N) cout << pre[i][j] << " \n"[j == N];
        // cout << pre[1][3] << '\n';
        // cout << get(1, 1, 3) << '\n';
        // REP(l2, lim) REP(l3, lim) cout << dp[2][l2][l3] << " " << l2 << " " << l3 << '\n';
        // cout << dp[4][5][0] << '\n';
        return ans;
    }
}
long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
    if(sub1::check(N, M, X, Y, W)) return sub1::Main(N, M, X, Y, W);
    if(sub2::check(N, M, X, Y, W)) return sub2::Main(N, M, X, Y, W);
    if(sub3::check(N, M, X, Y, W)) return sub3::Main(N, M, X, Y, W);
    if(sub4::check(N, M, X, Y, W)) return sub4::Main(N, M, X, Y, W);
    return 0;
}

Compilation message (stderr)

fish.cpp: In function 'long long int sub4::Main(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:85:32: warning: unused variable 'val2' [-Wunused-variable]
   85 |             long long val = 0, val2 = 0;
      |                                ^~~~

• 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