oj.uz

Submission #873601

# Submission time Handle Problem Language Result Execution time Memory
873601 2023-11-15T11:19:47 Z Ludissey Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 283020 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int, unordered_map<int,int>> a;
vector<vector<int>> fsh;
vector<vector<int>> cfsh;
vector<vector<int>> prfx;
 
unordered_map<int, unordered_map<int, unordered_map<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[x][last].find(big)!=memo[x][last].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 1068 ms 70084 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 1093 ms 78656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 65856 KB Output is correct
2 Correct 61 ms 65736 KB Output is correct
3 Correct 174 ms 101892 KB Output is correct
4 Correct 136 ms 94916 KB Output is correct
5 Correct 308 ms 141564 KB Output is correct
6 Correct 308 ms 140996 KB Output is correct
7 Correct 300 ms 141512 KB Output is correct
8 Correct 297 ms 141484 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 11 ms 1880 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 5 ms 1540 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 11 ms 1880 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 5 ms 1540 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 180 ms 1796 KB Output is correct
17 Execution timed out 1033 ms 5340 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 11 ms 1880 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 5 ms 1540 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 180 ms 1796 KB Output is correct
17 Execution timed out 1033 ms 5340 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 65856 KB Output is correct
2 Correct 61 ms 65736 KB Output is correct
3 Correct 174 ms 101892 KB Output is correct
4 Correct 136 ms 94916 KB Output is correct
5 Correct 308 ms 141564 KB Output is correct
6 Correct 308 ms 140996 KB Output is correct
7 Correct 300 ms 141512 KB Output is correct
8 Correct 297 ms 141484 KB Output is correct
9 Correct 424 ms 188352 KB Output is correct
10 Correct 300 ms 100192 KB Output is correct
11 Correct 639 ms 200100 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 432 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 65 ms 65952 KB Output is correct
19 Correct 60 ms 65736 KB Output is correct
20 Correct 61 ms 65732 KB Output is correct
21 Correct 61 ms 65736 KB Output is correct
22 Correct 437 ms 182508 KB Output is correct
23 Correct 887 ms 268208 KB Output is correct
24 Correct 943 ms 283020 KB Output is correct

Subtask #8
0 / 16.0

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