oj.uz

Submission #830555

# Submission time Handle Problem Language Result Execution time Memory
830555 2023-08-19T07:59:53 Z NeroZein Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int N = 3003;
int n; 
long long dp[N][N][2][2]; 
vector<vector<int>> a;

long long bt(int col, int last, bool me, bool recent) {
  if (col > n) {
    return 0;
  }
  if (last > n || last < 0) {
    return -1e14;
  }
  long long& ret = dp[col][last][me][recent];
  if (ret != -1) {
    return ret;
  }
  if (me) {
    //if (col != 4 || me != true || last != ) {
    ret = max(bt(col, last - 1, me, recent) + a[col][last],
              bt(col + 1, last, me ^ (last == 0), (last == 0)));
    //} else {
      //ret = bt(col + 1, last, me ^ (last == 0), (last == 0));
    //}
  } else {
    ret = max(bt(col, last + 1, me, recent) + a[col - 1][last] * (recent == false), 
              bt(col + 1, last, me ^ (last == n), false));      
  }
  //cout << col << ' ' << last << ' ' << me << ' ' << recent << ' ' << ret << '\n'; 
  return ret;
}

long long max_weights(int N_, int M, vector<int> X, vector<int> Y, vector<int> W) {
  n = N_; 
  a.resize(n + 1);
  for (int i = 0; i <= n; ++i) {
    a[i].resize(n + 1); 
  }
  for (int i = 0; i < M; ++i) {
    a[X[i] + 1][Y[i] + 1] = W[i];
  }
  memset(dp, -1, sizeof dp);
  return bt(1, 0, 0, 0);
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1218 ms 1986880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 282568 KB Output is correct
2 Runtime error 735 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 828 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 282572 KB Output is correct
2 Correct 104 ms 282552 KB Output is correct
3 Correct 105 ms 282536 KB Output is correct
4 Correct 103 ms 282612 KB Output is correct
5 Correct 105 ms 282580 KB Output is correct
6 Correct 107 ms 282544 KB Output is correct
7 Correct 109 ms 282644 KB Output is correct
8 Correct 107 ms 282536 KB Output is correct
9 Correct 106 ms 282700 KB Output is correct
10 Correct 111 ms 283208 KB Output is correct
11 Correct 107 ms 282812 KB Output is correct
12 Correct 109 ms 283056 KB Output is correct
13 Correct 106 ms 282616 KB Output is correct
14 Correct 109 ms 283136 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 282572 KB Output is correct
2 Correct 104 ms 282552 KB Output is correct
3 Correct 105 ms 282536 KB Output is correct
4 Correct 103 ms 282612 KB Output is correct
5 Correct 105 ms 282580 KB Output is correct
6 Correct 107 ms 282544 KB Output is correct
7 Correct 109 ms 282644 KB Output is correct
8 Correct 107 ms 282536 KB Output is correct
9 Correct 106 ms 282700 KB Output is correct
10 Correct 111 ms 283208 KB Output is correct
11 Correct 107 ms 282812 KB Output is correct
12 Correct 109 ms 283056 KB Output is correct
13 Correct 106 ms 282616 KB Output is correct
14 Correct 109 ms 283136 KB Output is correct
15 Correct 110 ms 283064 KB Output is correct
16 Incorrect 106 ms 282728 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '737338803564'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 282572 KB Output is correct
2 Correct 104 ms 282552 KB Output is correct
3 Correct 105 ms 282536 KB Output is correct
4 Correct 103 ms 282612 KB Output is correct
5 Correct 105 ms 282580 KB Output is correct
6 Correct 107 ms 282544 KB Output is correct
7 Correct 109 ms 282644 KB Output is correct
8 Correct 107 ms 282536 KB Output is correct
9 Correct 106 ms 282700 KB Output is correct
10 Correct 111 ms 283208 KB Output is correct
11 Correct 107 ms 282812 KB Output is correct
12 Correct 109 ms 283056 KB Output is correct
13 Correct 106 ms 282616 KB Output is correct
14 Correct 109 ms 283136 KB Output is correct
15 Correct 110 ms 283064 KB Output is correct
16 Incorrect 106 ms 282728 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '737338803564'
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 828 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 Execution timed out 1218 ms 1986880 KB Time limit exceeded
2 Halted 0 ms 0 KB -