oj.uz

Submission #1056479

# Submission time Handle Problem Language Result Execution time Memory
1056479 2024-08-13T09:38:37 Z aykhn Catfish Farm (IOI22_fish) C++17
35 / 100
 102 ms 16948 KB 
#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

const int MXN = 3e2 + 5;

long long dp[2][MXN][MXN], val[MXN][MXN];
long long lft[MXN][MXN], rig[MXN][MXN], in[MXN][MXN];
long long mx[MXN];

/*
0 = len[i] < len[i + 1];
1 = len[i] > len[i + 1];
*/
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) 
{
    for (int i = 0; i < M; i++) val[X[i] + 1][Y[i] + 1] = 1LL * val[X[i] + 1][Y[i] + 1] + 1LL * W[i];
    for (int i = 1; i <= N; i++) 
    {
        for (int j = 1; j <= N; j++)
        {
            lft[i][j] = lft[i][j - 1] + val[i - 1][j];
            rig[i][j] = rig[i][j - 1] + val[i + 1][j];
            in[i][j] = in[i][j - 1] + val[i][j];
        }
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            dp[0][i][j] = dp[1][i][j] = lft[i][j] + rig[i][j];
            if (i <= 1) continue;
            for (int k = 1; k <= N; k++)
            {
                if (k <= j)
                {
                    long long res = (dp[0][i - 1][k] - rig[i - 1][k]) + ((lft[i][j] - in[i - 1][k]) + rig[i][j]);
                    dp[0][i][j] = max(dp[0][i][j], res);
                }
                if (k >= j)
                {
                    long long res = dp[1][i - 1][k] - in[i][j] + rig[i][j];
                    dp[1][i][j] = max(dp[1][i][j], res);
                }
            }
            if (i <= 2) continue;
            for (int k = 1; k <= N; k++)
            {
                long long res = max(dp[0][i - 2][k], dp[1][i - 2][k]) + lft[i][j] + rig[i][j];
                if (k <= j) res -= rig[i - 2][k];
                else res -= lft[i][j];
                dp[0][i][j] = max(dp[0][i][j], res);
                dp[1][i][j] = max(dp[1][i][j], res);
            }
            if (i <= 3) continue;
            dp[0][i][j] = max(dp[0][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
            dp[1][i][j] = max(dp[1][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
        }
        for (int j = 1; j <= N; j++) mx[i] = max({mx[i], dp[0][i][j], dp[1][i][j]});
    }
    long long ans = 0;
    for (int i = 1; i <= N; i++) 
    {
        for (int j = 1; j <= N; j++) 
        {
            ans = max({ans, dp[0][i][j], dp[1][i][j]});
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 12880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Runtime error 102 ms 16948 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 7764 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 11 ms 4696 KB Output is correct
10 Correct 85 ms 4880 KB Output is correct
11 Correct 11 ms 4700 KB Output is correct
12 Correct 84 ms 4748 KB Output is correct
13 Correct 2 ms 4700 KB Output is correct
14 Correct 84 ms 4736 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 11 ms 4696 KB Output is correct
10 Correct 85 ms 4880 KB Output is correct
11 Correct 11 ms 4700 KB Output is correct
12 Correct 84 ms 4748 KB Output is correct
13 Correct 2 ms 4700 KB Output is correct
14 Correct 84 ms 4736 KB Output is correct
15 Correct 86 ms 4696 KB Output is correct
16 Correct 2 ms 4700 KB Output is correct
17 Correct 91 ms 6484 KB Output is correct
18 Correct 92 ms 6464 KB Output is correct
19 Correct 92 ms 6492 KB Output is correct
20 Correct 98 ms 6516 KB Output is correct
21 Correct 93 ms 6540 KB Output is correct
22 Correct 97 ms 8280 KB Output is correct
23 Correct 86 ms 4956 KB Output is correct
24 Correct 89 ms 5972 KB Output is correct
25 Correct 88 ms 4764 KB Output is correct
26 Correct 87 ms 5052 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 11 ms 4696 KB Output is correct
10 Correct 85 ms 4880 KB Output is correct
11 Correct 11 ms 4700 KB Output is correct
12 Correct 84 ms 4748 KB Output is correct
13 Correct 2 ms 4700 KB Output is correct
14 Correct 84 ms 4736 KB Output is correct
15 Correct 86 ms 4696 KB Output is correct
16 Correct 2 ms 4700 KB Output is correct
17 Correct 91 ms 6484 KB Output is correct
18 Correct 92 ms 6464 KB Output is correct
19 Correct 92 ms 6492 KB Output is correct
20 Correct 98 ms 6516 KB Output is correct
21 Correct 93 ms 6540 KB Output is correct
22 Correct 97 ms 8280 KB Output is correct
23 Correct 86 ms 4956 KB Output is correct
24 Correct 89 ms 5972 KB Output is correct
25 Correct 88 ms 4764 KB Output is correct
26 Correct 87 ms 5052 KB Output is correct
27 Runtime error 2 ms 4700 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 7764 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 12880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -