oj.uz

Submission #861453

# Submission time Handle Problem Language Result Execution time Memory
861453 2023-10-16T08:17:54 Z hocky Catfish Farm (IOI22_fish) C++17
52 / 100
 1000 ms 224836 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

const int kMaxN = 3000;
const int kUp = 0, kDown = 1;
const long long kInf = 4e18;

long long dp[kMaxN+2][kMaxN+2][2];
long long psum[kMaxN+2][kMaxN+2];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  for (int i = 0 ; i < M ; i++) {
    psum[X[i]][Y[i]+1] += W[i]; // increment y by one to ease our life
  }
  for (int i = 0 ; i < N ; i++) {
    for (int j = 1 ; j <= N ; j++) {
      psum[i][j] += psum[i][j-1];
    }
  }

  for (int col = N; col <= N+1 ; col++) {
    for (int i = 0 ; i <= N ; i++) {
      dp[col][i][kUp] = 0;
      dp[col][i][kDown] = 0;
    }
  }

  for (int col = N-1 ; col >= 0 ; col--) {
    for (int i = 0 ; i <= N ; i++) {
      dp[col][i][kUp] = dp[col][i][kDown] = -kInf;
    }
    
    // prefix max
    long long prefix_max = -kInf;
    for (int i = 1 ; i <= N ; i++) {
      long long val = psum[col+1][i];
      if (col > 0) val -= psum[col][i];
      prefix_max = max(prefix_max, val + dp[col+1][i][kDown]);

      dp[col][i][kDown] = max(dp[col][i][kDown], prefix_max);
      dp[col][i][kUp] = max(dp[col][i][kUp], prefix_max);
      dp[col][i][kUp] = max(dp[col][i][kUp], val + dp[col+1][i][kUp]);
    }

    // suffix max
    long long suffix_max = -kInf;
    for (int i = N ; i >= 0 ; i--) {
      if (i > 0) {
        long long val = psum[col+1][i];
        if (col > 0) val += psum[col-1][i];
        val += dp[col+1][i][kUp];
        suffix_max = max(suffix_max, val);
      }

      long long nval = suffix_max;
      if (col > 0) nval -= (psum[col][i] + psum[col-1][i]);
      dp[col][i][kUp] = max(dp[col][i][kUp], nval);
    }

    // if we turn current col to 0

    for (int i = 1 ; i <= N ; i++) {
      dp[col][i][kUp] = max(dp[col][i][kUp], dp[col+2][0][kUp]);
      dp[col][i][kDown] = max(dp[col][i][kDown], dp[col+2][0][kUp]);
    }
    dp[col][0][kUp] = max(dp[col][0][kUp], dp[col+1][0][kUp]);

    prefix_max = -kInf;
    for (int i = 1 ; i <= N ; i++) {
      prefix_max = max(prefix_max, psum[col+2][i] + dp[col+2][i][kUp]);

      dp[col][i][kUp] = max(dp[col][i][kUp], prefix_max);
      dp[col][i][kDown] = max(dp[col][i][kDown], prefix_max);
    }

    if (col+2 <= N) {
      suffix_max = -kInf;
      for (int i = N ; i >= 0 ; i--) {
        if (i > 0) {
          long long val = psum[col+2][i] + dp[col+2][i][kUp];
          val += psum[col][i];
          suffix_max = max(suffix_max, val);
        }

        long long nval = suffix_max - psum[col][i];
        dp[col][i][kUp] = max(dp[col][i][kUp], nval);
        dp[col][i][kDown] = max(dp[col][i][kDown], nval);      
      }
    }
  }

  long long ret = dp[0][0][kUp];
  return ret;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 125924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Execution timed out 1027 ms 125436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 117356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 5 ms 25180 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 4 ms 24924 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 5 ms 25180 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 4 ms 24924 KB Output is correct
15 Correct 4 ms 24920 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 13 ms 26932 KB Output is correct
18 Correct 15 ms 26716 KB Output is correct
19 Correct 13 ms 26716 KB Output is correct
20 Correct 13 ms 26716 KB Output is correct
21 Correct 13 ms 26828 KB Output is correct
22 Correct 22 ms 28692 KB Output is correct
23 Correct 7 ms 25436 KB Output is correct
24 Correct 13 ms 26292 KB Output is correct
25 Correct 4 ms 24920 KB Output is correct
26 Correct 6 ms 25436 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 5 ms 25180 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 4 ms 24924 KB Output is correct
15 Correct 4 ms 24920 KB Output is correct
16 Correct 2 ms 8536 KB Output is correct
17 Correct 13 ms 26932 KB Output is correct
18 Correct 15 ms 26716 KB Output is correct
19 Correct 13 ms 26716 KB Output is correct
20 Correct 13 ms 26716 KB Output is correct
21 Correct 13 ms 26828 KB Output is correct
22 Correct 22 ms 28692 KB Output is correct
23 Correct 7 ms 25436 KB Output is correct
24 Correct 13 ms 26292 KB Output is correct
25 Correct 4 ms 24920 KB Output is correct
26 Correct 6 ms 25436 KB Output is correct
27 Correct 146 ms 212080 KB Output is correct
28 Correct 58 ms 63312 KB Output is correct
29 Correct 213 ms 224836 KB Output is correct
30 Correct 210 ms 224492 KB Output is correct
31 Correct 210 ms 224592 KB Output is correct
32 Correct 70 ms 53600 KB Output is correct
33 Correct 235 ms 224604 KB Output is correct
34 Correct 218 ms 224588 KB Output is correct
35 Correct 199 ms 216708 KB Output is correct
36 Correct 209 ms 224452 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 117356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 125924 KB Time limit exceeded
2 Halted 0 ms 0 KB -