oj.uz

Submission #796679

# Submission time Handle Problem Language Result Execution time Memory
796679 2023-07-28T15:37:36 Z adrilen Catfish Farm (IOI22_fish) C++17
35 / 100
 108 ms 10028 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
using arr = array<ll, 2>;
constexpr int maxn = 305, maxm = 3e5;
int n, m;


ll fish[maxn][maxn] = { 0 };
ll dp[maxn][3][maxn] = { 0 };

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    n = N, m = M;


    for (int i = 0; i < m; i++)
    {
        fish[X[i] + 1][Y[i] + 1] += W[i];
    }

    
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++)
        {
            fish[x][y] += fish[x][y - 1];
        }
    }


    // Case 0: du er på bunnen
    // Case 1: stigende

    ll output = 0;

    for (int x = 2; x <= n + 1; x++)
    {
        for (int y = 0; y <= n; y++)
        {
            /*
            Case 0
            */

            // Case 0, 0 (y er her forrige i stedet for kommende)
            for (int y = 0; y <= n; y++)
            {
                dp[x][0][0] = max(dp[x][0][0], dp[x - 1][0][y]);
            }

            dp[x][0][y] = max(
                dp[x - 1][1][y],
                dp[x - 1][2][y]
            ) + fish[x][y]; 


            /*
            Case 1
            Stigende
            */

            for (int a = 1; a <= y; a++)
            {
                dp[x][1][y] = max(
                    dp[x][1][y], 
                    dp[x - 1][1][a] + 
                    fish[x - 1][y] - fish[x - 1][a]
                );
            }

            for (int a = 0; a <= n; a++) {
                dp[x][1][y] = max(
                    dp[x][1][y], 
                    dp[x - 1][0][a] + 
                    max(fish[x - 1][y] - fish[x - 1][a], 0ll)
                );
            }


            /*
            Case 2
            Fallende
            */

            for (int a = y + 1; a <= n; a++)
            {
                dp[x][2][y] = max(
                    dp[x][2][y],
                    max(dp[x - 1][1][a], dp[x - 1][2][a]) +
                    fish[x][a] - fish[x][y]
                );
            }

        }



    }

    // for (int x = 0; x <= n + 1; x++)
    // {   
    //     cout << "x: " << x << "\n";
    //     for (int y = 0; y < 3; y++)
    //     {
    //         for (int c = 0; c <= n; c++) cout << dp[x][y][c] << " ";
    //         cout << "\n";
    //     }
    //     cout << "\n";
    // }


    for (int i = 0; i <= n; i++) output = max(output, dp[n + 1][0][i]);

    return output;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 6104 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 340 KB Output is correct
2 Runtime error 56 ms 10028 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 2 ms 1876 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 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 13 ms 1720 KB Output is correct
10 Correct 91 ms 3252 KB Output is correct
11 Correct 14 ms 1748 KB Output is correct
12 Correct 92 ms 3204 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 87 ms 3084 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 13 ms 1720 KB Output is correct
10 Correct 91 ms 3252 KB Output is correct
11 Correct 14 ms 1748 KB Output is correct
12 Correct 92 ms 3204 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 87 ms 3084 KB Output is correct
15 Correct 90 ms 3092 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 102 ms 4648 KB Output is correct
18 Correct 96 ms 4976 KB Output is correct
19 Correct 98 ms 4940 KB Output is correct
20 Correct 104 ms 4916 KB Output is correct
21 Correct 101 ms 4924 KB Output is correct
22 Correct 108 ms 6968 KB Output is correct
23 Correct 89 ms 3488 KB Output is correct
24 Correct 92 ms 4340 KB Output is correct
25 Correct 90 ms 3196 KB Output is correct
26 Correct 89 ms 3484 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 13 ms 1720 KB Output is correct
10 Correct 91 ms 3252 KB Output is correct
11 Correct 14 ms 1748 KB Output is correct
12 Correct 92 ms 3204 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 87 ms 3084 KB Output is correct
15 Correct 90 ms 3092 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 102 ms 4648 KB Output is correct
18 Correct 96 ms 4976 KB Output is correct
19 Correct 98 ms 4940 KB Output is correct
20 Correct 104 ms 4916 KB Output is correct
21 Correct 101 ms 4924 KB Output is correct
22 Correct 108 ms 6968 KB Output is correct
23 Correct 89 ms 3488 KB Output is correct
24 Correct 92 ms 4340 KB Output is correct
25 Correct 90 ms 3196 KB Output is correct
26 Correct 89 ms 3484 KB Output is correct
27 Runtime error 2 ms 524 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 2 ms 1876 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 29 ms 6104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -