oj.uz

답안 #922494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922494 2024-02-05T14:52:27 Z Ludissey 메기 농장 (IOI22_fish) C++17
0 / 100
 892 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);
  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];
    }
  }
  int mx=0;
  for (int x = N-1; x >= 0; x--) // O(N)
  {
    for (int big = 0; big <= 2; big++) { // O(2)
      int _mx=-1, _mxI=0;
      for (int i = 0; i < N; i++)
      {
        int cmx=max(dp[x+1][i][big],max(dp[x+1][i][big],dp[x+1][i][big]));
        if(cmx>_mx) _mxI=i;
        _mx=max(_mx,cmx);
      }
      fsh[x].push_back(_mxI);
      _mx=-1, _mxI=N;
      for (int i = N; i > 0; i--)
      {
        int cmx=max(dp[x+1][i][big],max(dp[x+1][i][big],dp[x+1][i][big]));
        if(cmx>_mx) _mxI=i;
        _mx=max(_mx,cmx);
      }
      fsh[x].push_back(_mxI);

      for (int last = 0; last <= N; last++) // O(N)
      {
        if(x==0&&last>0) break;
          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;
            }
            dp[x][last][big]=max(c, dp[x][last][big]);
            mx=max(dp[x][last][big],mx);
          //zcerr<<x << " " << last << " " << big << " = " << dp[x][last][big] <<  "\n";
        }
      }
    }
  }
  return mx;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 892 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 763 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 730 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 3 ms 2140 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '213041971702'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 3 ms 2140 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '213041971702'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 3 ms 2140 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '213041971702'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 730 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 892 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -