oj.uz

Submission #873549

# Submission time Handle Problem Language Result Execution time Memory
873549 2023-11-15T09:42:12 Z Ludissey Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 135872 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;
vector<vector<int>> prfx;
 
map<pair<int,pair<int,int>>, int> memo;
int N,M;
//x N possible
//last 2N possible negatif et pas negatif
//big 2 possible
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;
 
  int mx = 0;
  for (auto i:fsh[x]) //O(N)
  {
    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) {
        if(last<i&&i>0){  
          for (auto y : cfsh[x-1]){
            if(y>=last&&y<i) c+=a[{x-1,y}];
          }
        }
        if(i<last&&last>0){
          for (auto y : cfsh[x]) { 
            if(y>=i&&y<last) c+=a[{x,y}];
          }
        }
      }else{
        if(abs(last)<i&&i>0){
          for (auto y : cfsh[x-1]){
            if(y>=abs(last)&&y<i) c+=a[{x-1,y}];
          }
        }
      }
      
    }
    mx=max(c, mx);
  }
  return memo[{x,{last,big}}]=mx;
}
 
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]);
    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()); // N log  N
  int p=dp(0,0,1); //(N*2N*2*N) (300*600*300*2) (108.000.000)
  return p;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 41832 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 348 KB Output is correct
2 Execution timed out 1084 ms 51924 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 34648 KB Output is correct
2 Correct 35 ms 34640 KB Output is correct
3 Correct 186 ms 48784 KB Output is correct
4 Correct 120 ms 46676 KB Output is correct
5 Correct 356 ms 65892 KB Output is correct
6 Correct 297 ms 65380 KB Output is correct
7 Correct 295 ms 65872 KB Output is correct
8 Correct 319 ms 65864 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 0 ms 348 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 19 ms 1372 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 7 ms 860 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 5 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 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 0 ms 348 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 19 ms 1372 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 7 ms 860 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 5 ms 860 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 359 ms 1292 KB Output is correct
17 Execution timed out 1063 ms 5716 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 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 0 ms 348 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 19 ms 1372 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 7 ms 860 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 5 ms 860 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 359 ms 1292 KB Output is correct
17 Execution timed out 1063 ms 5716 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 34648 KB Output is correct
2 Correct 35 ms 34640 KB Output is correct
3 Correct 186 ms 48784 KB Output is correct
4 Correct 120 ms 46676 KB Output is correct
5 Correct 356 ms 65892 KB Output is correct
6 Correct 297 ms 65380 KB Output is correct
7 Correct 295 ms 65872 KB Output is correct
8 Correct 319 ms 65864 KB Output is correct
9 Correct 526 ms 89172 KB Output is correct
10 Correct 401 ms 52816 KB Output is correct
11 Correct 910 ms 105172 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 35 ms 34736 KB Output is correct
19 Correct 35 ms 34644 KB Output is correct
20 Correct 39 ms 34640 KB Output is correct
21 Correct 35 ms 34640 KB Output is correct
22 Correct 500 ms 92320 KB Output is correct
23 Execution timed out 1068 ms 135872 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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