oj.uz

Submission #625406

# Submission time Handle Problem Language Result Execution time Memory
625406 2022-08-10T11:28:16 Z model_code Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 12188 KB 
#include "fish.h"

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

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

long long psum[kMaxN][kMaxN+1];
long long dp[kMaxN][kMaxN+1][2];
int N;

long long solve(int col, int y_bef, int mode) {
  if (col >= N) {
    return 0;
  }
  long long &ret = dp[col][y_bef][mode];
  if (ret != -1) {
    return ret;
  }

  ret = -kInf;
  
  for (int i = 1 ; i <= N ; i++) {
    long long add = 0;
    if (col+1 < N) add += psum[col+1][i];
    if (col > 0) add -= psum[col][min(i, y_bef)];
    if (col > 0 && i > y_bef) add += (psum[col-1][i] - psum[col-1][y_bef]);

    if (mode == kUp) {
      ret = max(ret, add + solve(col+1, i, i >= y_bef ? kUp : kDown));
    }
    if (mode == kDown) {
      if (i <= y_bef) ret = max(ret, add + solve(col+1, i, kDown));
      else break;
    }
  }

  // if we turn this into 0
  ret = max(ret, solve(col+2, 0, kUp));
  if (y_bef == 0) {
    ret = max(ret, solve(col+1, 0, kUp));
  }
  if (col+2 <= N) {
    // set for col+1
    for (int i = 1 ; i <= N ; i++) {
      long long add = 0;
      if (col+2 < N) add += psum[col+2][i];
      if (col+1 < N) add += (psum[col][max(i, y_bef)] - psum[col][y_bef]);
      ret = max(ret, add + solve(col+2, i, kUp));
    }
  }

  return ret;
}

long long max_weights(int _N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  N = _N;
  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];
    }
  }

  memset(dp, -1, sizeof dp);
  long long ret = solve(0, 0, kUp);
  return ret;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 6984 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 2 ms 1620 KB Output is correct
2 Runtime error 77 ms 12188 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 1748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 124 ms 2080 KB Output is correct
10 Execution timed out 1008 ms 2536 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 124 ms 2080 KB Output is correct
10 Execution timed out 1008 ms 2536 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 124 ms 2080 KB Output is correct
10 Execution timed out 1008 ms 2536 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1748 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 32 ms 6984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -