Submission #625702

#	Time	Username	Problem	Language	Result	Execution time	Memory
625702		Clan328	Catfish Farm (IOI22_fish)	C++17	9 / 100	776 ms	2097152 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define int long long

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll MOD = 1e9 + 7;

void settings()__attribute__((constructor));

void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
    for (auto elem : v) 
        stream << elem << " ";
    return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
        stream >> elem;
   return stream;
}

void settings() {
    #ifdef LOCAL
        freopen("io/input.txt", "r", stdin);
        freopen("io/output.txt", "w", stdout);
    #endif

    ios::sync_with_stdio(0);
    cin.tie(0);
}

long long max_weights(signed N, signed M, std::vector<signed> X, std::vector<signed> Y,
                      std::vector<signed> W) {
    int NY = Y[0];
    for (int i = 1; i < M; i++) {
        NY = max(NY, (ll)Y[i]);
    }
    NY++;

    vvi a(N, vi(NY)), sum(N, vi(NY+1));
    for (int i = 0; i < M; i++) {
        a[X[i]][Y[i]] = W[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= NY; j++) sum[i][j] = sum[i][j-1]+a[i][j-1];
    }

    vvi dp(N, vi(NY+1)), aux(N, vi(NY+1));
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < NY+1; j++) {
            for (int k = 0; k < NY+1; k++) {
                if (j <= k) {
                    int tmp = dp[i-1][k] + sum[i][k]-sum[i][j];
                    if (dp[i][j] < tmp) {
                        dp[i][j] = tmp;
                        aux[i][j] = sum[i][k]-sum[i][j];
                    }
                } else {
                    int tmp = dp[i-1][k] + max(0LL, sum[i-1][j]-sum[i-1][k]-aux[i-1][k]);
                    if (dp[i][j] <= tmp) {
                        dp[i][j] = tmp;
                        aux[i][j] = 0;
                    }
                }

                if (i-2 < 0) continue;
                int tmp = dp[i-2][k] + max(sum[i-1][k], sum[i-1][j]);
                if (dp[i][j] <= tmp) {
                    dp[i][j] = tmp;
                    aux[i][j] = 0;
                }

                if (i-3 < 0) continue;
                tmp = dp[i-3][k] + sum[i-2][k] + sum[i-1][j];
                if (dp[i][j] <= tmp) {
                    dp[i][j] = tmp;
                    aux[i][j] = 0;
                }
            }
        }
    }

    // for (int i = 0; i <N; i++) cout << a[i] << nL;
    // for (int i = 0; i <N; i++) cout << dp[i] << nL;

    ll res = 0;
    for (int i = 0; i < NY+1; i++) {
        res = max(res, dp[N-1][i]);
    }

  return res;
}

• 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: 0 / 14
• Subtask 8: 0 / 16