oj.uz

Submission #626618

# Submission time Handle Problem Language Result Execution time Memory
626618 2022-08-11T15:10:02 Z dariasc Catfish Farm (IOI22_fish) C++17
0 / 100
 977 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector
#define ll long long

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

  ll fish[N][N];
  memset(fish, 0, sizeof fish);
  for (int i = 0; i < M; i++) {
    fish[X[i]][Y[i]] = W[i];
  }

  ll pfx[N][N+1][2];
  memset(pfx, 0, sizeof pfx);
  for (int x = 0; x < N; x++) {
    for (int y = 1; y <= N; y++) {
      ll l = 0;
      if (x > 0) {
        l = fish[x-1][y-1];
      }
      ll r = 0;
      if (x < N-1) {
        r = fish[x+1][y-1];
      }
      pfx[x][y][0] = pfx[x][y-1][0] + l;
      pfx[x][y][1] = pfx[x][y-1][1] + r;
    }
  }

  /*
  for (int x = 0; x <= N; x++) {
    for (int y = 0; y < N; y++) {
      cout << pfx[y][x][0] << ":" << pfx[y][x][1] << " ";
    }
    cout << endl;
  }
  */
  ll dp[N][N+1][3];
  memset(dp, 0, sizeof dp);
  for (int y = 1; y <= N; y++) {
    dp[0][y][0] = pfx[0][y][1];
    dp[0][y][1] = pfx[0][y][1];
    dp[0][y][2] = pfx[0][y][1];
  }
  for (int x = 1; x < N; x++) {
    for (int y = 0; y <= N; y++) {
      dp[x][y][0] = pfx[x][y][0] + pfx[x][y][1];
      dp[x][y][1] = dp[x][y][0];
      dp[x][y][2] = dp[x][y][0];
      for (int k = 0; k <= N; k++) {
        if (x > 2) {
          dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][0] + pfx[x][y][0] + pfx[x][y][1]);
          dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][1] + pfx[x][y][0] + pfx[x][y][1]);
          dp[x][y][0] = max(dp[x][y][0], dp[x-3][k][2] + pfx[x][y][0] + pfx[x][y][1]);
        }
        if (x > 1) {
          ll addend = 0;
          if (y > k) {
            addend = pfx[x][y][0] - pfx[x][k][0];
          }
          dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][0] + addend + pfx[x][y][1]);
          dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][1] + addend + pfx[x][y][1]);
          dp[x][y][1] = max(dp[x][y][1], dp[x-2][k][2] + addend + pfx[x][y][1]);

        }
        if (x > 0) {
          ll addend = 0;
          if (y > k) {
            addend = pfx[x][y][0] - pfx[x][k][0];
          }
          dp[x][y][2] = max(dp[x][y][2], dp[x-1][k][0] - pfx[x-1][min(k,y)][1] + addend + pfx[x][y][1]);
          dp[x][y][2] = max(dp[x][y][2], dp[x-1][k][1] - pfx[x-1][min(k,y)][1] + addend + pfx[x][y][1]);
        }
      }
    }
  }
  /*
  for (int x = 0; x <= N; x++) {
    for (int y = 0; y < N; y++) {
      cout << dp[y][x] << " ";
    }
    cout << endl;
  }*/
  ll best = 0;
  for (int x = 0; x < N; x++) {
    for (int y = 0; y <= N; y++) {
      best = max(dp[x][y][0], best);
      best = max(dp[x][y][1], best);
      best = max(dp[x][y][2], best);
    }
  }

  return best;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 977 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 844 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 789 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 789 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 977 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -