oj.uz

Submission #873594

# Submission time Handle Problem Language Result Execution time Memory
873594 2023-11-15T10:42:28 Z Ludissey Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
 
        if (hash1 != hash2) {
            return hash1 ^ hash2;              
        }
         
        // If hash1 == hash2, their XOR is zero.
          return hash1;
    }
};

unordered_map<pair<int,int>, int, hash_pair> a;
vector<vector<int>> fsh;
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){  
          c+=prfx[x-1][i-1];
          if(last>0) c-=prfx[x-1][last-1];
        }
        if(i<last&&last>0){
          c+=prfx[x][last-1];
          if(i>0) c-=prfx[x][i-1];
        }
      }else{
        if(abs(last)<i&&i>0){
          c+=prfx[x-1][i-1];
          if(abs(last)>0) c-=prfx[x-1][abs(last)-1];
        }
      }
      
    }
    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));
  prfx.resize(N+1, vector<int>(N+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()); // N log  N
  for (int i = 0; i < N; i++) //N*N
  {
    for (int j = 0; j < N; j++)
    {
      prfx[i][j]=a[{i,j}];
      if(j>0) prfx[i][j]+=prfx[i][j-1];
    }
  }
  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 Runtime error 979 ms 2097152 KB Execution killed with signal 9
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 Runtime error 788 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 759 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

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 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 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 11 ms 2140 KB Output is correct
10 Correct 106 ms 7364 KB Output is correct
11 Correct 14 ms 2276 KB Output is correct
12 Correct 107 ms 7540 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 99 ms 7056 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 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 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 11 ms 2140 KB Output is correct
10 Correct 106 ms 7364 KB Output is correct
11 Correct 14 ms 2276 KB Output is correct
12 Correct 107 ms 7540 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 99 ms 7056 KB Output is correct
15 Correct 95 ms 7076 KB Output is correct
16 Correct 62 ms 1368 KB Output is correct
17 Execution timed out 1057 ms 11360 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 344 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 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 11 ms 2140 KB Output is correct
10 Correct 106 ms 7364 KB Output is correct
11 Correct 14 ms 2276 KB Output is correct
12 Correct 107 ms 7540 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 99 ms 7056 KB Output is correct
15 Correct 95 ms 7076 KB Output is correct
16 Correct 62 ms 1368 KB Output is correct
17 Execution timed out 1057 ms 11360 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 759 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 979 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -