oj.uz

Submission #871918

# Submission time Handle Problem Language Result Execution time Memory
871918 2023-11-11T21:09:34 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 134932 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;

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 (int y = last; y < max(i,lastlast); y++) if(y>=last||y<max(i,lastlast)) c+=a[{x-1,y}];
    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));
  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 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 1027 ms 39356 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 1083 ms 47508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 33856 KB Output is correct
2 Correct 67 ms 34068 KB Output is correct
3 Correct 305 ms 50632 KB Output is correct
4 Correct 234 ms 47444 KB Output is correct
5 Correct 545 ms 68436 KB Output is correct
6 Correct 550 ms 68432 KB Output is correct
7 Correct 538 ms 68436 KB Output is correct
8 Correct 547 ms 68352 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 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 100 ms 2576 KB Output is correct
11 Correct 28 ms 1104 KB Output is correct
12 Correct 35 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 17 ms 1224 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 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 100 ms 2576 KB Output is correct
11 Correct 28 ms 1104 KB Output is correct
12 Correct 35 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 17 ms 1224 KB Output is correct
15 Correct 22 ms 3564 KB Output is correct
16 Execution timed out 1061 ms 2004 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 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 7 ms 604 KB Output is correct
10 Correct 100 ms 2576 KB Output is correct
11 Correct 28 ms 1104 KB Output is correct
12 Correct 35 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 17 ms 1224 KB Output is correct
15 Correct 22 ms 3564 KB Output is correct
16 Execution timed out 1061 ms 2004 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 33856 KB Output is correct
2 Correct 67 ms 34068 KB Output is correct
3 Correct 305 ms 50632 KB Output is correct
4 Correct 234 ms 47444 KB Output is correct
5 Correct 545 ms 68436 KB Output is correct
6 Correct 550 ms 68432 KB Output is correct
7 Correct 538 ms 68436 KB Output is correct
8 Correct 547 ms 68352 KB Output is correct
9 Execution timed out 1067 ms 134932 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 39356 KB Time limit exceeded
2 Halted 0 ms 0 KB -