oj.uz

Submission #871912

# Submission time Handle Problem Language Result Execution time Memory
871912 2023-11-11T20:47:52 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 133796 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++) 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 1061 ms 39120 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 1073 ms 47288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 33872 KB Output is correct
2 Correct 68 ms 33960 KB Output is correct
3 Correct 300 ms 50268 KB Output is correct
4 Correct 244 ms 48156 KB Output is correct
5 Correct 550 ms 70032 KB Output is correct
6 Correct 563 ms 69200 KB Output is correct
7 Correct 543 ms 69888 KB Output is correct
8 Correct 556 ms 70040 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 504 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 7 ms 604 KB Output is correct
10 Correct 106 ms 2444 KB Output is correct
11 Correct 28 ms 1116 KB Output is correct
12 Correct 35 ms 1784 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 17 ms 1380 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 504 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 7 ms 604 KB Output is correct
10 Correct 106 ms 2444 KB Output is correct
11 Correct 28 ms 1116 KB Output is correct
12 Correct 35 ms 1784 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 17 ms 1380 KB Output is correct
15 Correct 22 ms 3416 KB Output is correct
16 Execution timed out 1043 ms 1892 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 504 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 7 ms 604 KB Output is correct
10 Correct 106 ms 2444 KB Output is correct
11 Correct 28 ms 1116 KB Output is correct
12 Correct 35 ms 1784 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 17 ms 1380 KB Output is correct
15 Correct 22 ms 3416 KB Output is correct
16 Execution timed out 1043 ms 1892 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 33872 KB Output is correct
2 Correct 68 ms 33960 KB Output is correct
3 Correct 300 ms 50268 KB Output is correct
4 Correct 244 ms 48156 KB Output is correct
5 Correct 550 ms 70032 KB Output is correct
6 Correct 563 ms 69200 KB Output is correct
7 Correct 543 ms 69888 KB Output is correct
8 Correct 556 ms 70040 KB Output is correct
9 Execution timed out 1067 ms 133796 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 1061 ms 39120 KB Time limit exceeded
2 Halted 0 ms 0 KB -