oj.uz

Submission #872200

# Submission time Handle Problem Language Result Execution time Memory
872200 2023-11-12T13:36:32 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 108884 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);
    }
  }
  for (int i = 0; i < N; i++) sort(fsh[i].begin(),fsh[i].end());
  
  int p=dp(0,0,0);
  return p;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 41860 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 1049 ms 50588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 36188 KB Output is correct
2 Correct 66 ms 36180 KB Output is correct
3 Correct 301 ms 53516 KB Output is correct
4 Correct 236 ms 50344 KB Output is correct
5 Correct 567 ms 73644 KB Output is correct
6 Correct 562 ms 73812 KB Output is correct
7 Correct 561 ms 73832 KB Output is correct
8 Correct 558 ms 73812 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 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 756 KB Output is correct
10 Correct 102 ms 2580 KB Output is correct
11 Correct 27 ms 1112 KB Output is correct
12 Correct 32 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 16 ms 1280 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 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 756 KB Output is correct
10 Correct 102 ms 2580 KB Output is correct
11 Correct 27 ms 1112 KB Output is correct
12 Correct 32 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 16 ms 1280 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Execution timed out 1093 ms 2036 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 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 756 KB Output is correct
10 Correct 102 ms 2580 KB Output is correct
11 Correct 27 ms 1112 KB Output is correct
12 Correct 32 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 16 ms 1280 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Execution timed out 1093 ms 2036 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 36188 KB Output is correct
2 Correct 66 ms 36180 KB Output is correct
3 Correct 301 ms 53516 KB Output is correct
4 Correct 236 ms 50344 KB Output is correct
5 Correct 567 ms 73644 KB Output is correct
6 Correct 562 ms 73812 KB Output is correct
7 Correct 561 ms 73832 KB Output is correct
8 Correct 558 ms 73812 KB Output is correct
9 Execution timed out 1065 ms 108884 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 1047 ms 41860 KB Time limit exceeded
2 Halted 0 ms 0 KB -