oj.uz

Submission #872219

# Submission time Handle Problem Language Result Execution time Memory
872219 2023-11-12T14:17:04 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 97596 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;
int allPOSS=0;
map<pair<int,pair<int,int>>, int> memo;
int N,M;
int dp(int x, int last, int lastlast){
  if(memo[{x,{last,lastlast}}]!=0) return memo[{x,{last,lastlast}}]-1;
  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}}]);
  }
  memo[{x,{last,lastlast}}]+=1;
  return memo[{x,{last,lastlast}}]-1;
}
 
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 1059 ms 41080 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 348 KB Output is correct
2 Execution timed out 1086 ms 50148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 36436 KB Output is correct
2 Correct 80 ms 36404 KB Output is correct
3 Correct 326 ms 53584 KB Output is correct
4 Correct 257 ms 50276 KB Output is correct
5 Correct 627 ms 73660 KB Output is correct
6 Correct 620 ms 73756 KB Output is correct
7 Correct 591 ms 73980 KB Output is correct
8 Correct 612 ms 73808 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 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 348 KB Output is correct
9 Correct 8 ms 732 KB Output is correct
10 Correct 115 ms 2512 KB Output is correct
11 Correct 30 ms 1112 KB Output is correct
12 Correct 36 ms 1864 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 18 ms 1112 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 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 348 KB Output is correct
9 Correct 8 ms 732 KB Output is correct
10 Correct 115 ms 2512 KB Output is correct
11 Correct 30 ms 1112 KB Output is correct
12 Correct 36 ms 1864 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 18 ms 1112 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Execution timed out 1088 ms 2564 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 1 ms 348 KB Output is correct
3 Correct 0 ms 344 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 348 KB Output is correct
9 Correct 8 ms 732 KB Output is correct
10 Correct 115 ms 2512 KB Output is correct
11 Correct 30 ms 1112 KB Output is correct
12 Correct 36 ms 1864 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 18 ms 1112 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Execution timed out 1088 ms 2564 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 36436 KB Output is correct
2 Correct 80 ms 36404 KB Output is correct
3 Correct 326 ms 53584 KB Output is correct
4 Correct 257 ms 50276 KB Output is correct
5 Correct 627 ms 73660 KB Output is correct
6 Correct 620 ms 73756 KB Output is correct
7 Correct 591 ms 73980 KB Output is correct
8 Correct 612 ms 73808 KB Output is correct
9 Execution timed out 1034 ms 97596 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 1059 ms 41080 KB Time limit exceeded
2 Halted 0 ms 0 KB -