oj.uz

Submission #625409

# Submission time Handle Problem Language Result Execution time Memory
625409 2022-08-10T11:28:28 Z model_code Catfish Farm (IOI22_fish) C++17
52 / 100
 1000 ms 224204 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 1061 ms 98400 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 340 KB Output is correct
2 Execution timed out 1095 ms 108508 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 1045 ms 88384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 2004 KB Output is correct
10 Correct 5 ms 4948 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 7 ms 4892 KB Output is correct
13 Correct 1 ms 944 KB Output is correct
14 Correct 6 ms 4800 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 2004 KB Output is correct
10 Correct 5 ms 4948 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 7 ms 4892 KB Output is correct
13 Correct 1 ms 944 KB Output is correct
14 Correct 6 ms 4800 KB Output is correct
15 Correct 5 ms 4820 KB Output is correct
16 Correct 2 ms 1128 KB Output is correct
17 Correct 24 ms 6716 KB Output is correct
18 Correct 26 ms 6596 KB Output is correct
19 Correct 26 ms 6568 KB Output is correct
20 Correct 16 ms 6592 KB Output is correct
21 Correct 21 ms 6536 KB Output is correct
22 Correct 42 ms 8384 KB Output is correct
23 Correct 9 ms 5228 KB Output is correct
24 Correct 13 ms 5796 KB Output is correct
25 Correct 5 ms 4820 KB Output is correct
26 Correct 10 ms 5204 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 2004 KB Output is correct
10 Correct 5 ms 4948 KB Output is correct
11 Correct 3 ms 2004 KB Output is correct
12 Correct 7 ms 4892 KB Output is correct
13 Correct 1 ms 944 KB Output is correct
14 Correct 6 ms 4800 KB Output is correct
15 Correct 5 ms 4820 KB Output is correct
16 Correct 2 ms 1128 KB Output is correct
17 Correct 24 ms 6716 KB Output is correct
18 Correct 26 ms 6596 KB Output is correct
19 Correct 26 ms 6568 KB Output is correct
20 Correct 16 ms 6592 KB Output is correct
21 Correct 21 ms 6536 KB Output is correct
22 Correct 42 ms 8384 KB Output is correct
23 Correct 9 ms 5228 KB Output is correct
24 Correct 13 ms 5796 KB Output is correct
25 Correct 5 ms 4820 KB Output is correct
26 Correct 10 ms 5204 KB Output is correct
27 Correct 263 ms 211920 KB Output is correct
28 Correct 104 ms 28356 KB Output is correct
29 Correct 360 ms 224204 KB Output is correct
30 Correct 435 ms 220436 KB Output is correct
31 Correct 355 ms 223080 KB Output is correct
32 Correct 130 ms 19320 KB Output is correct
33 Correct 464 ms 224088 KB Output is correct
34 Correct 479 ms 219420 KB Output is correct
35 Correct 334 ms 214992 KB Output is correct
36 Correct 466 ms 219052 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 88384 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 1061 ms 98400 KB Time limit exceeded
2 Halted 0 ms 0 KB -