oj.uz

Submission #922356

# Submission time Handle Problem Language Result Execution time Memory
922356 2024-02-05T12:33:12 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 N possible negatif et pas negatif
//big 3 possible
int dp(int x, int last, int big){
  if(memo[x][last][big]!=-1) return memo[x][last][big];
  if(x==N) {
    return 0;
  }
  int mx = 0;
  for (auto i:fsh[x]) //O(3)
  {
    if(i>last&&big==0) continue;
    int c=0;
    if(i==0) {
      if(big!=2) c=dp(x+1, last, 1+(last>0));
      else c=dp(x+1, 0, 1);
    }
    else c+=dp(x+1, i, (i>last));

    if(i==0&&last>0) {
      if(big<2) c+=prfx[x][last-1];
    }
    else if(last>i&&big<2) {
      c+=prfx[x][last-1]-prfx[x][i-1];
    }
    else if(i>last&&x>0){
      int ng=0;
      if(last>0) ng=prfx[x-1][last-1];
      c+=prfx[x-1][i-1]-ng;
    }
    mx=max(c, mx);
  }
  //cerr<<x << " " << last << " " << big << " = " << mx <<  "\n";
  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));
  possprfx.resize(N+1, vector<int>(N+1,0));
  memo.resize(N+1, vector<vector<int>>(2*(N+1), vector<int>(3,-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;
    int mx=0;
    //decrease
    for (int j = 0; j < N; j++)
    {
      if(j>0) possprfx[i][j]=possprfx[i][j-1];
      possprfx[i][j]-=a[i][j];
      if(i<N-1) possprfx[i][j]+=a[i+1][j];
      if(possprfx[i][j]>=mx) { mxIndx=j; mx=possprfx[i][j]; }
    }
    fsh[i].push_back(mxIndx+1);
    mxIndx=-1;
    mx=0;
    //increase
    for (int j = 0; j < N; j++)
    {
      if(j>0) possprfx[i][j]=possprfx[i][j-1];
      if(i>0) possprfx[i][j]+=a[i-1][j];
      if(possprfx[i][j]>mx) { mxIndx=j; mx=possprfx[i][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 1041 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 344 KB Output is correct
2 Runtime error 928 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 857 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 344 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 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 3512 KB Output is correct
10 Correct 15 ms 12644 KB Output is correct
11 Correct 5 ms 3420 KB Output is correct
12 Correct 19 ms 12672 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 18 ms 12636 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 3512 KB Output is correct
10 Correct 15 ms 12644 KB Output is correct
11 Correct 5 ms 3420 KB Output is correct
12 Correct 19 ms 12672 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 18 ms 12636 KB Output is correct
15 Correct 13 ms 12380 KB Output is correct
16 Correct 6 ms 1368 KB Output is correct
17 Correct 384 ms 15308 KB Output is correct
18 Correct 413 ms 15944 KB Output is correct
19 Correct 295 ms 15764 KB Output is correct
20 Correct 222 ms 15780 KB Output is correct
21 Correct 224 ms 15728 KB Output is correct
22 Correct 798 ms 18904 KB Output is correct
23 Correct 38 ms 13148 KB Output is correct
24 Correct 153 ms 14472 KB Output is correct
25 Correct 14 ms 12436 KB Output is correct
26 Correct 32 ms 13128 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 3512 KB Output is correct
10 Correct 15 ms 12644 KB Output is correct
11 Correct 5 ms 3420 KB Output is correct
12 Correct 19 ms 12672 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 18 ms 12636 KB Output is correct
15 Correct 13 ms 12380 KB Output is correct
16 Correct 6 ms 1368 KB Output is correct
17 Correct 384 ms 15308 KB Output is correct
18 Correct 413 ms 15944 KB Output is correct
19 Correct 295 ms 15764 KB Output is correct
20 Correct 222 ms 15780 KB Output is correct
21 Correct 224 ms 15728 KB Output is correct
22 Correct 798 ms 18904 KB Output is correct
23 Correct 38 ms 13148 KB Output is correct
24 Correct 153 ms 14472 KB Output is correct
25 Correct 14 ms 12436 KB Output is correct
26 Correct 32 ms 13128 KB Output is correct
27 Execution timed out 1115 ms 1210108 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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