oj.uz

Submission #888845

# Submission time Handle Problem Language Result Execution time Memory
888845 2023-12-18T09:16:54 Z Ludissey Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> a;
vector<vector<int>> fsh;
vector<vector<int>> prfx;
vector<vector<int>> possprfx;
 
vector<vector<vector<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+N][big]!=-1) return memo[x][last+N][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+N][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));
  possprfx.resize(N+1, vector<int>(N+1,0));
  memo.resize(N+1, vector<vector<int>>(2*(N+1), vector<int>(2,-1)));
  a.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];
    }
  }
  for (int i = 0; i <= N; i++) //N*N
  {
    int mxIndx=-1;
    for (int j = 0; j < N; j++)
    {
      possprfx[i][j]=-a[i][j];
      if(j>0) possprfx[i][j]+=possprfx[i][j-1];
      if(i<N-1) possprfx[i][j]+=a[i+1][j];
      if(mxIndx==-1 || possprfx[i][j]>possprfx[i][mxIndx]) mxIndx=j;
    }
    fsh[i].push_back(mxIndx+1);
    for (int j = 0; j < N; j++) possprfx[i][j]=0;
    mxIndx=-1;
    for (int j = N-1; j >= 0; j--)
    {
      possprfx[i][j]=-a[i][j];
      if(j>0) possprfx[i][j]+=possprfx[i][j-1];
      if(i<N-1) possprfx[i][j]+=a[i+1][j];
      if(mxIndx==-1 || possprfx[i][j]>possprfx[i][mxIndx]) mxIndx=j;
    }
    fsh[i].push_back(mxIndx+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 Execution timed out 1012 ms 2097152 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 436 KB Output is correct
2 Runtime error 823 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 779 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 1 ms 440 KB Output is correct
9 Correct 4 ms 3460 KB Output is correct
10 Correct 14 ms 12636 KB Output is correct
11 Correct 4 ms 3420 KB Output is correct
12 Correct 14 ms 12636 KB Output is correct
13 Correct 1 ms 1112 KB Output is correct
14 Correct 14 ms 12668 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 1 ms 440 KB Output is correct
9 Correct 4 ms 3460 KB Output is correct
10 Correct 14 ms 12636 KB Output is correct
11 Correct 4 ms 3420 KB Output is correct
12 Correct 14 ms 12636 KB Output is correct
13 Correct 1 ms 1112 KB Output is correct
14 Correct 14 ms 12668 KB Output is correct
15 Correct 17 ms 12508 KB Output is correct
16 Correct 8 ms 1372 KB Output is correct
17 Correct 351 ms 15308 KB Output is correct
18 Correct 362 ms 15944 KB Output is correct
19 Correct 220 ms 15760 KB Output is correct
20 Correct 194 ms 15696 KB Output is correct
21 Correct 189 ms 15728 KB Output is correct
22 Correct 758 ms 18904 KB Output is correct
23 Correct 38 ms 13180 KB Output is correct
24 Correct 148 ms 14428 KB Output is correct
25 Correct 14 ms 12636 KB Output is correct
26 Correct 27 ms 12880 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 1 ms 440 KB Output is correct
9 Correct 4 ms 3460 KB Output is correct
10 Correct 14 ms 12636 KB Output is correct
11 Correct 4 ms 3420 KB Output is correct
12 Correct 14 ms 12636 KB Output is correct
13 Correct 1 ms 1112 KB Output is correct
14 Correct 14 ms 12668 KB Output is correct
15 Correct 17 ms 12508 KB Output is correct
16 Correct 8 ms 1372 KB Output is correct
17 Correct 351 ms 15308 KB Output is correct
18 Correct 362 ms 15944 KB Output is correct
19 Correct 220 ms 15760 KB Output is correct
20 Correct 194 ms 15696 KB Output is correct
21 Correct 189 ms 15728 KB Output is correct
22 Correct 758 ms 18904 KB Output is correct
23 Correct 38 ms 13180 KB Output is correct
24 Correct 148 ms 14428 KB Output is correct
25 Correct 14 ms 12636 KB Output is correct
26 Correct 27 ms 12880 KB Output is correct
27 Execution timed out 1089 ms 1209928 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 779 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 Execution timed out 1012 ms 2097152 KB Time limit exceeded
2 Halted 0 ms 0 KB -