oj.uz

Submission #922394

# Submission time Handle Problem Language Result Execution time Memory
922394 2024-02-05T13:18:49 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>>> dp;
int N,M;
 
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));
  dp.resize(N+1, vector<vector<int>>((N+1), vector<int>(3,0)));
  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 mx=0;
  for (int x = N-1; x >= 0; x--) // O(N)
  {
    for (int last = 0; last <= N; last++) // O(N)
    {
      if(x==0&&last>0) break;
      for (int big = 0; big <= 2; big++)// O(2)
      {
        for (auto i:fsh[x]) // O(N)
        {
          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;
          }
          dp[x][last][big]=max(c, dp[x][last][big]);
          mx=max(dp[x][last][big],mx);
        }
        //cerr<<x << " " << last << " " << big << " = " << dp[x][last][big] <<  "\n";
      }
    }
  }
  return mx;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 919 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 600 KB Output is correct
2 Runtime error 806 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 750 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 432 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 4 ms 2232 KB Output is correct
10 Correct 23 ms 7772 KB Output is correct
11 Correct 5 ms 2140 KB Output is correct
12 Correct 17 ms 7608 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 15 ms 7644 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 4 ms 2232 KB Output is correct
10 Correct 23 ms 7772 KB Output is correct
11 Correct 5 ms 2140 KB Output is correct
12 Correct 17 ms 7608 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 15 ms 7644 KB Output is correct
15 Correct 11 ms 7516 KB Output is correct
16 Correct 6 ms 916 KB Output is correct
17 Correct 258 ms 10076 KB Output is correct
18 Correct 253 ms 10584 KB Output is correct
19 Correct 260 ms 10492 KB Output is correct
20 Correct 255 ms 10508 KB Output is correct
21 Correct 272 ms 10512 KB Output is correct
22 Correct 502 ms 13436 KB Output is correct
23 Correct 62 ms 8028 KB Output is correct
24 Correct 180 ms 9480 KB Output is correct
25 Correct 17 ms 7516 KB Output is correct
26 Correct 59 ms 8028 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 4 ms 2232 KB Output is correct
10 Correct 23 ms 7772 KB Output is correct
11 Correct 5 ms 2140 KB Output is correct
12 Correct 17 ms 7608 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 15 ms 7644 KB Output is correct
15 Correct 11 ms 7516 KB Output is correct
16 Correct 6 ms 916 KB Output is correct
17 Correct 258 ms 10076 KB Output is correct
18 Correct 253 ms 10584 KB Output is correct
19 Correct 260 ms 10492 KB Output is correct
20 Correct 255 ms 10508 KB Output is correct
21 Correct 272 ms 10512 KB Output is correct
22 Correct 502 ms 13436 KB Output is correct
23 Correct 62 ms 8028 KB Output is correct
24 Correct 180 ms 9480 KB Output is correct
25 Correct 17 ms 7516 KB Output is correct
26 Correct 59 ms 8028 KB Output is correct
27 Execution timed out 1086 ms 706260 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 750 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 919 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -