oj.uz

Submission #766276

# Submission time Handle Problem Language Result Execution time Memory
766276 2023-06-25T12:36:54 Z jakobrs Catfish Farm (IOI22_fish) C++17
23 / 100
 165 ms 74720 KB 
#include "fish.h"

#include <vector>
#include <cstdint>

#include <iostream>

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  int h = 8 + 1;
  int64_t sum_up_to[N][h];
  for (int x = 0; x < N; x++) {
    for (int y = 0; y < h; y++) {
      sum_up_to[x][y] = 0;
    }
  }
  for (int i = 0; i < M; i++) {
    sum_up_to[X[i]][Y[i] + 1] = W[i];
  }
  for (int x = 0; x < N; x++) {
    int64_t accum = 0;
    sum_up_to[x][0] = accum;
    for (int y = 1; y < h; y++) {
      accum += sum_up_to[x][y];
      sum_up_to[x][y] = accum;
    }
  }

  int64_t dp[N][h][h];
  for (int i = 0; i < N; i++) {
    for (int x = 0; x < h; x++) {
      for (int y = 0; y < h; y++) {
        dp[i][x][y] = INT64_MIN;
      }
    }
  }

  for (int x = 0; x < h; x++) {
    dp[0][x][0] = 0;
  }

  for (int i = 1; i < N; i++) {
    for (int x = 0; x < h; x++) {
      for (int y = 0; y < h; y++) {
        if (x == y) {
          dp[i][x][y] = 0;
          for (int z = 0; z < h; z++) {
            dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
          }
        } else if (x > y) {
          dp[i][x][y] = 0;
          for (int z = 0; z < h; z++) {
            if (x > y && x > z) {
              dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z] + sum_up_to[i - 1][x] - sum_up_to[i - 1][std::max(y, z)]);
            } else {
              dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
            }
          }
        } else {
          dp[i][x][y] = 0;
          {
            for (int z = 0; z < h; z++) {
              dp[i][x][y] = std::max(dp[i][x][y], dp[i - 1][y][z]);
            }
          }
          dp[i][x][y] += sum_up_to[i][y] - sum_up_to[i][x];
        }
      }
    }

    // std::cout << dp[i][0][0] << ' ' << dp[i][0][1] << ' ' << dp[i][1][0] << ' ' << dp[i][1][1] << '\n';
  }

  int64_t best = 0;
  for (int x = 0; x < h; x++) {
    for (int y = 0; y < h; y++) {
      best = std::max(best, dp[N - 1][x][y]);
    }
  }
  
  return best;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 66988 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '24919943721621'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 135 ms 70324 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '27140523777613'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 70724 KB Output is correct
2 Correct 107 ms 70724 KB Output is correct
3 Correct 122 ms 65792 KB Output is correct
4 Correct 165 ms 72232 KB Output is correct
5 Correct 163 ms 74720 KB Output is correct
6 Correct 160 ms 74056 KB Output is correct
7 Correct 137 ms 74572 KB Output is correct
8 Correct 133 ms 74596 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 436 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 436 KB Output is correct
15 Runtime error 1 ms 812 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 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 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 436 KB Output is correct
15 Runtime error 1 ms 812 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 70724 KB Output is correct
2 Correct 107 ms 70724 KB Output is correct
3 Correct 122 ms 65792 KB Output is correct
4 Correct 165 ms 72232 KB Output is correct
5 Correct 163 ms 74720 KB Output is correct
6 Correct 160 ms 74056 KB Output is correct
7 Correct 137 ms 74572 KB Output is correct
8 Correct 133 ms 74596 KB Output is correct
9 Runtime error 40 ms 20680 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 66988 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '24919943721621'
2 Halted 0 ms 0 KB -