oj.uz

Submission #872196

# Submission time Handle Problem Language Result Execution time Memory
872196 2023-11-12T13:32:00 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 109832 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 (int y = i; y < last; y++) c+=a[{x,y}];
    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 1066 ms 41532 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 1083 ms 50528 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 36228 KB Output is correct
2 Correct 66 ms 36180 KB Output is correct
3 Correct 301 ms 53572 KB Output is correct
4 Correct 235 ms 50768 KB Output is correct
5 Correct 569 ms 75856 KB Output is correct
6 Correct 560 ms 74848 KB Output is correct
7 Correct 555 ms 75460 KB Output is correct
8 Correct 565 ms 75224 KB Output is correct

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 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 384 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 812 KB Output is correct
10 Correct 104 ms 2804 KB Output is correct
11 Correct 27 ms 1104 KB Output is correct
12 Correct 33 ms 1620 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 20 ms 1184 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 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 384 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 812 KB Output is correct
10 Correct 104 ms 2804 KB Output is correct
11 Correct 27 ms 1104 KB Output is correct
12 Correct 33 ms 1620 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 20 ms 1184 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Execution timed out 1088 ms 2068 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 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 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 384 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 812 KB Output is correct
10 Correct 104 ms 2804 KB Output is correct
11 Correct 27 ms 1104 KB Output is correct
12 Correct 33 ms 1620 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 20 ms 1184 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Execution timed out 1088 ms 2068 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 36228 KB Output is correct
2 Correct 66 ms 36180 KB Output is correct
3 Correct 301 ms 53572 KB Output is correct
4 Correct 235 ms 50768 KB Output is correct
5 Correct 569 ms 75856 KB Output is correct
6 Correct 560 ms 74848 KB Output is correct
7 Correct 555 ms 75460 KB Output is correct
8 Correct 565 ms 75224 KB Output is correct
9 Execution timed out 1034 ms 109832 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 1066 ms 41532 KB Time limit exceeded
2 Halted 0 ms 0 KB -