oj.uz

Submission #872201

# Submission time Handle Problem Language Result Execution time Memory
872201 2023-11-12T13:40:08 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 101200 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<pair<int,int>, int> a;
vector<vector<int>> fsh;
vector<vector<int>> cfsh;

map<pair<int,pair<int,int>>, int> memo;
int N,M;
int dp(int x, int last, int lastlast){
  if(memo.find({x,{last,lastlast}})!=memo.end()) return memo[{x,{last,lastlast}}];
  if(x==N) return 0;
 
  memo[{x,{last,lastlast}}] = 0;
  for (auto i:fsh[x])
  {
    int c=dp(x+1, i, last);
    if(x>0){
      for (auto y:cfsh[x-1]) {
        if(y>last&&y<=max(i,lastlast)) c+=a[{x-1,y-1}];
      }
    }
    if(x==N-1) {
      for (auto y:cfsh[x]) {
        if(y>i&&y<=last) c+=a[{x,y-1}];
      }
    }
    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; 
  fsh.resize(N+1, vector<int>(1,0));
  cfsh.resize(N+1);
  for (int i = 0; i < M; i++){
    a[{X[i],Y[i]}] = W[i];

    fsh[X[i]+1].push_back(Y[i]+1);
    cfsh[X[i]].push_back(Y[i]+1);
    if(X[i]>0) {
      fsh[X[i]-1].push_back(Y[i]+1);
    }
  }
  
  int p=dp(0,0,0);
  return p;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 41060 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 344 KB Output is correct
2 Execution timed out 1035 ms 50204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 36184 KB Output is correct
2 Correct 64 ms 36344 KB Output is correct
3 Correct 307 ms 53636 KB Output is correct
4 Correct 233 ms 50200 KB Output is correct
5 Correct 571 ms 73924 KB Output is correct
6 Correct 558 ms 73684 KB Output is correct
7 Correct 537 ms 73808 KB Output is correct
8 Correct 558 ms 73776 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 8 ms 604 KB Output is correct
10 Correct 107 ms 2644 KB Output is correct
11 Correct 28 ms 1116 KB Output is correct
12 Correct 34 ms 1764 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 17 ms 1116 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 8 ms 604 KB Output is correct
10 Correct 107 ms 2644 KB Output is correct
11 Correct 28 ms 1116 KB Output is correct
12 Correct 34 ms 1764 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 17 ms 1116 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Execution timed out 1086 ms 2032 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 8 ms 604 KB Output is correct
10 Correct 107 ms 2644 KB Output is correct
11 Correct 28 ms 1116 KB Output is correct
12 Correct 34 ms 1764 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 17 ms 1116 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Execution timed out 1086 ms 2032 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 36184 KB Output is correct
2 Correct 64 ms 36344 KB Output is correct
3 Correct 307 ms 53636 KB Output is correct
4 Correct 233 ms 50200 KB Output is correct
5 Correct 571 ms 73924 KB Output is correct
6 Correct 558 ms 73684 KB Output is correct
7 Correct 537 ms 73808 KB Output is correct
8 Correct 558 ms 73776 KB Output is correct
9 Execution timed out 1018 ms 101200 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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