oj.uz

Submission #625410

# Submission time Handle Problem Language Result Execution time Memory
625410 2022-08-10T11:28:32 Z model_code Catfish Farm (IOI22_fish) C++17
23 / 100
 896 ms 85028 KB 
#include "fish.h"

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

const int kMaxN = 100'000;
const int kMaxY = 8;
const long long kInf = 4e18;

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

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

  ret = -kInf;
  for (int y = 0 ; y <= kMaxY ; y++) {
    long long add = 0;

    if (col > 0) add -= psum[col][min(y, y_bef)];
    if (col > 0) {
      int covered = max(y_bef2, y_bef);
      covered = min(covered, y);
      add += (psum[col-1][y] - psum[col-1][covered]);
    }
    if (col+1 < N) add += psum[col+1][y];

    ret = max(ret, add + solve(col+1, y_bef, y));
  }

  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 <= kMaxY ; j++) {
      psum[i][j] += psum[i][j-1];
    }
  }

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 755 ms 81800 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 40 ms 63656 KB Output is correct
2 Incorrect 716 ms 83728 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '48976405912959'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 81684 KB Output is correct
2 Correct 701 ms 81692 KB Output is correct
3 Correct 809 ms 82108 KB Output is correct
4 Correct 758 ms 82952 KB Output is correct
5 Correct 830 ms 84212 KB Output is correct
6 Correct 878 ms 85028 KB Output is correct
7 Correct 742 ms 84052 KB Output is correct
8 Correct 896 ms 84052 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63676 KB Output is correct
2 Correct 43 ms 63676 KB Output is correct
3 Correct 56 ms 63604 KB Output is correct
4 Correct 37 ms 63700 KB Output is correct
5 Correct 31 ms 63656 KB Output is correct
6 Correct 36 ms 63700 KB Output is correct
7 Correct 34 ms 63576 KB Output is correct
8 Correct 37 ms 63696 KB Output is correct
9 Correct 40 ms 63680 KB Output is correct
10 Correct 37 ms 63796 KB Output is correct
11 Correct 32 ms 63744 KB Output is correct
12 Correct 28 ms 63692 KB Output is correct
13 Correct 26 ms 63676 KB Output is correct
14 Correct 28 ms 63676 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63676 KB Output is correct
2 Correct 43 ms 63676 KB Output is correct
3 Correct 56 ms 63604 KB Output is correct
4 Correct 37 ms 63700 KB Output is correct
5 Correct 31 ms 63656 KB Output is correct
6 Correct 36 ms 63700 KB Output is correct
7 Correct 34 ms 63576 KB Output is correct
8 Correct 37 ms 63696 KB Output is correct
9 Correct 40 ms 63680 KB Output is correct
10 Correct 37 ms 63796 KB Output is correct
11 Correct 32 ms 63744 KB Output is correct
12 Correct 28 ms 63692 KB Output is correct
13 Correct 26 ms 63676 KB Output is correct
14 Correct 28 ms 63676 KB Output is correct
15 Incorrect 41 ms 63676 KB 1st lines differ - on the 1st token, expected: '299', found: '240'
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63676 KB Output is correct
2 Correct 43 ms 63676 KB Output is correct
3 Correct 56 ms 63604 KB Output is correct
4 Correct 37 ms 63700 KB Output is correct
5 Correct 31 ms 63656 KB Output is correct
6 Correct 36 ms 63700 KB Output is correct
7 Correct 34 ms 63576 KB Output is correct
8 Correct 37 ms 63696 KB Output is correct
9 Correct 40 ms 63680 KB Output is correct
10 Correct 37 ms 63796 KB Output is correct
11 Correct 32 ms 63744 KB Output is correct
12 Correct 28 ms 63692 KB Output is correct
13 Correct 26 ms 63676 KB Output is correct
14 Correct 28 ms 63676 KB Output is correct
15 Incorrect 41 ms 63676 KB 1st lines differ - on the 1st token, expected: '299', found: '240'
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 81684 KB Output is correct
2 Correct 701 ms 81692 KB Output is correct
3 Correct 809 ms 82108 KB Output is correct
4 Correct 758 ms 82952 KB Output is correct
5 Correct 830 ms 84212 KB Output is correct
6 Correct 878 ms 85028 KB Output is correct
7 Correct 742 ms 84052 KB Output is correct
8 Correct 896 ms 84052 KB Output is correct
9 Runtime error 43 ms 5276 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 755 ms 81800 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '24919943721621'
2 Halted 0 ms 0 KB -