Submission #1211411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211411		nerrrmin	Catfish Farm (IOI22_fish)	C++20	18 / 100	1100 ms	134052 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
#define pb push_back
#include <vector>
using namespace std;
const int maxn = 3005;
int n, m;
vector < pair < int, int > > g[200000];
long long dp[maxn][maxn][10];
long long best[maxn];
long long pref[maxn][maxn], a[maxn][maxn];
long long get(int col, int l, int r)
{
    if(r < l)return 0;
    if(col > n)return 0;
    long long val = pref[col][r];
    if(l)val -= pref[col][l-1];
    return val;
}
long long p[4][200000];
long long get_p(long long col, long long l, long long r)
{
    if(r < l)return 0;
    if(col > n)return 0;
    long long val = p[col][r];
    if(l)val -= p[col][l-1];
    return val;
}
long long val[200000], d[200000][2][2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n = N;
    m = M;
    long long sum = 0, group1 = 1, group2 = 1, group3 = 1;
    for (int i = 0; i < m; ++ i)
    {
        if(X[i] % 2 == 1)group1 = 0;
        if(X[i] > 1)group2 = 0;
        if(Y[i] > 0)group3 = 0;

        X[i] ++;
        Y[i] ++;
        g[X[i]].pb(make_pair(Y[i], W[i]));
        sum += W[i];
        if(n <= 3000)a[X[i]][Y[i]] = W[i];

        if(X[i] <= 2)p[X[i]][Y[i]] += W[i];
        if(Y[i] == 1)val[X[i]] += W[i];
    }
    if(group1)return sum;
    if(group2)
    {

        long long sum1 = 0, sum2 = 0;
        for (auto &[y, w]: g[1])
            sum1 += w;
        for (auto &[y, w]: g[2])
            sum2 += w;
            long long ans = max(sum1, sum2);
        if(n > 2)
        {
            for (int i = 1; i <= 2; ++ i)
            {
                for (int j = 1; j <= n; ++ j)
                    p[i][j] += p[i][j-1];
            }
            for (int i = 0; i <= n; ++ i)
            {
                long long curr = get_p(1, 1, i) + get_p(2, i+1, n);
                ans = max(ans, curr);
            }
        }
        return ans;
    }
    if(group3)
    {
        d[1][0][0] = 0;
        d[1][0][1] = 0;

        long long ans = 0;
        if(n > 1)ans = val[2];

        for (int i = 2; i <= n; ++ i)
        {
            /// 0
            d[i][0][0] = max(d[i-1][0][0], d[i-1][1][0]);
            d[i][1][0] = max(d[i-1][0][1], d[i-1][1][1]) + val[i];

            /// 1
            d[i][0][1] = max(d[i-1][0][0] + val[i-1], d[i-1][1][0]);
            d[i][1][1] = max(d[i-1][0][1], d[i-1][1][1]);
            ans = max(ans, max(d[i][0][1], d[i][1][1]) + val[i+1]);
        }
        return ans;
    }

    for (int i = 0; i <= n; ++ i)
    {
        pref[i][0] = a[i][0];
        for (int j = 1; j <= n; ++ j)
            pref[i][j] = pref[i][j-1] + a[i][j];
    }
    long long ans = 0;
    for (int j = 0; j <= n; ++ j)
    {
        if(n >= 2)
        {
            ans = max(ans, get(2, 1, j));
            best[1] = ans;
        }
    }

    for (int i = 2; i <= n; ++ i)
    {
        dp[i][0][0] = best[i-1];
        dp[i][0][1] = best[i-1];
        for (int j = 1; j <= n; ++ j)
        {
            for (int pre = 1; pre <= j; ++ pre)
            {
                dp[i][j][0] = max(dp[i][j][0], dp[i-1][pre][0] + get(i-1, pre + 1, j));
            }
            for (int pre = j; pre <= n; ++ pre)
            {
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][pre][1] + get(i, j+1, pre));
            }
            /// start new
            for (int pre = 1; pre <= n; ++ pre)
            {
                long long curr = max(dp[i-2][pre][0], dp[i-2][pre][1]) + get(i-1, 1, max(pre, j));
                dp[i][j][0] = max(dp[i][j][0], curr);
                dp[i][j][1] = max(dp[i][j][1], curr);
            }
            if(i >= 3)
            {
                long long curr = best[i-3] + get(i-1, 1, j);
                dp[i][j][0] = max(dp[i][j][0], curr);
                dp[i][j][1] = max(dp[i][j][1], curr);
            }

            ans = max(ans, max(dp[i][j][0], dp[i][j][1]) + get(i+1, 1, j));
        }
        best[i] = ans;
    }
  return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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