oj.uz

Submission #871836

# Submission time Handle Problem Language Result Execution time Memory
871836 2023-11-11T17:21:52 Z Ludissey Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> a;
vector<vector<int>> fsh;

vector<vector<int>> prefx;
vector<vector<vector<int>>> memo;
int N,M;
int dp(int x, int last, int lastlast){
  if(memo[x][last][lastlast]!=-1) return memo[x][last][lastlast];
  if(x==N) return memo[x][last][lastlast]=0;
 
  memo[x][last][lastlast] = 0;
  for (auto i:fsh[x])
  {
    int c=dp(x+1, i, last);
    if(x>0) c+=max(0LL,prefx[x-1][max(i,lastlast)]-prefx[x-1][last]);
    if(x==N-1) c+=max(0LL,prefx[x][last]-prefx[x][i]);
    memo[x][last][lastlast]=max(c, memo[x][last][lastlast]);
  }
  return memo[x][last][lastlast];
}
 
long long max_weights(signed n, signed m, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
  N=n; M=m; 
  a.resize(N, vector<int>(N,0));
  fsh.resize(N+1, vector<int>(1,0));
  prefx.resize(N, vector<int>(N+1,0)); //y+1
  memo.resize(N+1, vector<vector<int>>(N+1, vector<int>(N+1,-1)));
  for (int i = 0; i < M; i++){
    a[X[i]][Y[i]] = W[i];
    fsh[X[i]+1].push_back(Y[i]+1);
    if(X[i]>0) fsh[X[i]-1].push_back(Y[i]+1);

  }
  for (int x = 0; x < N; x++)
  {
    for (int y = 0; y < N; y++)
    {
       prefx[x][y+1]=a[x][y]+prefx[x][y];
    }
  }
  
  int p=dp(0,0,0);
  return p;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Runtime error 818 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 758 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 13 ms 28516 KB Output is correct
10 Correct 98 ms 218952 KB Output is correct
11 Correct 14 ms 28504 KB Output is correct
12 Correct 97 ms 218948 KB Output is correct
13 Correct 2 ms 4184 KB Output is correct
14 Correct 95 ms 218960 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 13 ms 28516 KB Output is correct
10 Correct 98 ms 218952 KB Output is correct
11 Correct 14 ms 28504 KB Output is correct
12 Correct 97 ms 218948 KB Output is correct
13 Correct 2 ms 4184 KB Output is correct
14 Correct 95 ms 218960 KB Output is correct
15 Correct 98 ms 218988 KB Output is correct
16 Correct 127 ms 4444 KB Output is correct
17 Execution timed out 1077 ms 220744 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 13 ms 28516 KB Output is correct
10 Correct 98 ms 218952 KB Output is correct
11 Correct 14 ms 28504 KB Output is correct
12 Correct 97 ms 218948 KB Output is correct
13 Correct 2 ms 4184 KB Output is correct
14 Correct 95 ms 218960 KB Output is correct
15 Correct 98 ms 218988 KB Output is correct
16 Correct 127 ms 4444 KB Output is correct
17 Execution timed out 1077 ms 220744 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 758 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 1004 ms 2097152 KB Time limit exceeded
2 Halted 0 ms 0 KB -