oj.uz

Submission #873277

# Submission time Handle Problem Language Result Execution time Memory
873277 2023-11-14T17:58:49 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 161648 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 big){
  if(memo.find({x,{last,big}})!=memo.end()) return memo[{x,{last,big}}];
  if(x==N) return 0;
 
  memo[{x,{last,big}}] = 0;
  for (auto i:fsh[x])
  {
    int c=0;
    if(i==0){
      if(last<=0) c=dp(x+1, 0, 1);
      else if(last>0) c=dp(x+1,(-last), 1);
    } else if(i>=abs(last)) {
      if(big==0) break;
      c=dp(x+1, i, 1);
    }else if(i<abs(last)){
      c=dp(x+1, i, 0);
    }
    if(x>0) {
      if(last>=0) {
        for (int y = last; y < i; y++) c+=a[{x-1,y}];
        for (int y = i; y < last; y++) c+=a[{x,y}];
      }else{
        for (int y = abs(last); y < i; y++) c+=a[{x-1,y}];
      }
      
    }
    memo[{x,{last,big}}]=max(c, memo[{x,{last,big}}]);
  }
  return memo[{x,{last,big}}];
}
 
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,1);
  return p;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 39476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 1092 ms 48660 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 32284 KB Output is correct
2 Correct 63 ms 32512 KB Output is correct
3 Correct 232 ms 45352 KB Output is correct
4 Correct 196 ms 43860 KB Output is correct
5 Correct 455 ms 60644 KB Output is correct
6 Correct 449 ms 59928 KB Output is correct
7 Correct 421 ms 60752 KB Output is correct
8 Correct 410 ms 60596 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 0 ms 432 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 24 ms 1244 KB Output is correct
11 Correct 8 ms 604 KB Output is correct
12 Correct 12 ms 1060 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 7 ms 860 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 0 ms 432 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 24 ms 1244 KB Output is correct
11 Correct 8 ms 604 KB Output is correct
12 Correct 12 ms 1060 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 7 ms 860 KB Output is correct
15 Correct 18 ms 3432 KB Output is correct
16 Correct 422 ms 1360 KB Output is correct
17 Execution timed out 1068 ms 6140 KB Time limit exceeded
18 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 0 ms 432 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 24 ms 1244 KB Output is correct
11 Correct 8 ms 604 KB Output is correct
12 Correct 12 ms 1060 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 7 ms 860 KB Output is correct
15 Correct 18 ms 3432 KB Output is correct
16 Correct 422 ms 1360 KB Output is correct
17 Execution timed out 1068 ms 6140 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 32284 KB Output is correct
2 Correct 63 ms 32512 KB Output is correct
3 Correct 232 ms 45352 KB Output is correct
4 Correct 196 ms 43860 KB Output is correct
5 Correct 455 ms 60644 KB Output is correct
6 Correct 449 ms 59928 KB Output is correct
7 Correct 421 ms 60752 KB Output is correct
8 Correct 410 ms 60596 KB Output is correct
9 Execution timed out 1031 ms 161648 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 1052 ms 39476 KB Time limit exceeded
2 Halted 0 ms 0 KB -