oj.uz

Submission #830646

# Submission time Handle Problem Language Result Execution time Memory
830646 2023-08-19T08:51:59 Z NeroZein Catfish Farm (IOI22_fish) C++17
17 / 100
 110 ms 220684 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 302;
int n; 
int a[N][N]; 
bool smaller;
int max_m, max_n;
long long pref[N][N]; 
long long dp[N][N][N]; 

long long bt(int col, int last, int last2) {
  if (col > n || (smaller && col > 5)) {
    return 0;
  }
  long long& ret = dp[col][last][last2];
  if (ret != -1) {
    return ret;
  }
  long long sum = 0; 
  long long ps = pref[col][last]; 
  for (int nlast = 0; nlast <= min(n, 11); ++nlast) {
    if (nlast > last2 && nlast > last) sum += a[col - 1][nlast];
    if (nlast <= last) ps -= a[col][nlast];
    //if (sum) assert(ps == 0);
    ret = max(ret, bt(col + 1, nlast, last) + sum + ps); 
  }
  return ret;
}

long long max_weights(int N_, int M, vector<int> X, vector<int> Y, vector<int> W) {
  n = N_; 
  bool even = true;
  bool zero_Y = true;
  smaller = true;
  for (int i = 0; i < M; ++i) {
    max_m = max(max_m, X[i] + 1); 
    max_n = max(max_n, Y[i] + 1); 
    even &= (X[i] % 2 == 0);
    zero_Y &= Y[i] == 0;
    smaller &= X[i] <= 1; 
  }
  if (even || zero_Y) {
    return accumulate(W.begin(), W.end(), 0LL);
  }
  for (int i = 0; i < M; ++i) {
    a[X[i] + 1][Y[i] + 1] = W[i];
  }
  for (int i = 1; i <= max_m; ++i) {
    for (int j = 1; j <= max_n; ++j) {
      pref[i][j] = pref[i][j - 1] + a[i][j];      
    } 
  }
  memset(dp, -1, sizeof dp);
  return bt(1, 0, 0); 
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2164 KB Output is correct
2 Correct 22 ms 2648 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 66 ms 13680 KB Output is correct
6 Correct 68 ms 13920 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 215824 KB Output is correct
2 Incorrect 110 ms 220684 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '1450741445090'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 13 ms 2516 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 215884 KB Output is correct
2 Correct 86 ms 215908 KB Output is correct
3 Correct 69 ms 215888 KB Output is correct
4 Correct 73 ms 215836 KB Output is correct
5 Correct 67 ms 215836 KB Output is correct
6 Correct 67 ms 215888 KB Output is correct
7 Correct 71 ms 215880 KB Output is correct
8 Correct 67 ms 215872 KB Output is correct
9 Correct 68 ms 216396 KB Output is correct
10 Correct 71 ms 217040 KB Output is correct
11 Correct 84 ms 216352 KB Output is correct
12 Correct 67 ms 216908 KB Output is correct
13 Correct 64 ms 216140 KB Output is correct
14 Correct 85 ms 217000 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 215884 KB Output is correct
2 Correct 86 ms 215908 KB Output is correct
3 Correct 69 ms 215888 KB Output is correct
4 Correct 73 ms 215836 KB Output is correct
5 Correct 67 ms 215836 KB Output is correct
6 Correct 67 ms 215888 KB Output is correct
7 Correct 71 ms 215880 KB Output is correct
8 Correct 67 ms 215872 KB Output is correct
9 Correct 68 ms 216396 KB Output is correct
10 Correct 71 ms 217040 KB Output is correct
11 Correct 84 ms 216352 KB Output is correct
12 Correct 67 ms 216908 KB Output is correct
13 Correct 64 ms 216140 KB Output is correct
14 Correct 85 ms 217000 KB Output is correct
15 Incorrect 81 ms 217048 KB 1st lines differ - on the 1st token, expected: '299', found: '11'
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 215884 KB Output is correct
2 Correct 86 ms 215908 KB Output is correct
3 Correct 69 ms 215888 KB Output is correct
4 Correct 73 ms 215836 KB Output is correct
5 Correct 67 ms 215836 KB Output is correct
6 Correct 67 ms 215888 KB Output is correct
7 Correct 71 ms 215880 KB Output is correct
8 Correct 67 ms 215872 KB Output is correct
9 Correct 68 ms 216396 KB Output is correct
10 Correct 71 ms 217040 KB Output is correct
11 Correct 84 ms 216352 KB Output is correct
12 Correct 67 ms 216908 KB Output is correct
13 Correct 64 ms 216140 KB Output is correct
14 Correct 85 ms 217000 KB Output is correct
15 Incorrect 81 ms 217048 KB 1st lines differ - on the 1st token, expected: '299', found: '11'
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 13 ms 2516 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2164 KB Output is correct
2 Correct 22 ms 2648 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 66 ms 13680 KB Output is correct
6 Correct 68 ms 13920 KB Output is correct
7 Correct 68 ms 215824 KB Output is correct
8 Incorrect 110 ms 220684 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '1450741445090'
9 Halted 0 ms 0 KB -