oj.uz

답안 #659594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659594 2022-11-18T17:34:54 Z peijar 메기 농장 (IOI22_fish) C++17
0 / 100
 1000 ms 820232 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1e18;

const int MAXN = 1e5;
vector<pair<int, int>> dp[MAXN][2];

int eval(int i, int side, int h) {
  auto it = upper_bound(dp[i][side].begin(), dp[i][side].end(), pair(h, INF));
  assert(it != dp[i][side].begin());
  --it;
  return it->second;
}

int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y,
                vector<signed> W) {
  vector<vector<pair<int, int>>> onCol(N);
  vector<vector<int>> prefSum(N);
  for (int i = 0; i < M; ++i)
    onCol[X[i]].emplace_back(Y[i] + 1, W[i]);
  for (int i = 0; i < N; ++i) {
    sort(onCol[i].begin(), onCol[i].end());
    prefSum[i].resize(onCol[i].size() + 1);
    for (int j = 0; j < (int)onCol[i].size(); ++j)
      prefSum[i][j + 1] = prefSum[i][j] + onCol[i][j].second;
  }

  vector<vector<int>> interesting(N);
  for (int i = 0; i < N; ++i) {
    interesting[i].push_back(0);
    for (auto [y, w] : onCol[i])
      interesting[i].push_back(y);
    if (i)
      for (auto [y, w] : onCol[i - 1])
        interesting[i].push_back(y);
    if (i + 1 < N)
      for (auto [y, w] : onCol[i + 1])
        interesting[i].push_back(y);
    sort(interesting[i].begin(), interesting[i].end());
    interesting[i].resize(unique(interesting[i].begin(), interesting[i].end()) -
                          interesting[i].begin());
  }
  dp[0][0].emplace_back(0, 0);
  dp[0][1].emplace_back(0, 0);

  auto getSum = [&](int i, int h1, int h2) -> int {
    int lo = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h1, INF)) -
             onCol[i].begin();
    int up = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h2, INF)) -
             onCol[i].begin();
    return prefSum[i][up] - prefSum[i][lo];
  };

  int sol = 0;
  for (int i = 1; i < N; ++i) {
    int nbInteressants = interesting[i].size();
    for (int iHauteur = 0; iHauteur < nbInteressants; ++iHauteur) {
      int h = interesting[i][iHauteur];
      // 1
      int v1 = 0;
      for (int jHauteur = iHauteur + 1; jHauteur < nbInteressants; ++jHauteur) {
        int oldH = interesting[i][jHauteur];
        v1 = max(v1,
                 getSum(i, h, oldH) + eval(i - 1, 1, interesting[i][jHauteur]));
      }
      // 0
      int v0 = 0;
      for (int jHauteur = 0; jHauteur < nbInteressants; ++jHauteur) {
        int oldH = interesting[i][jHauteur];
        if (jHauteur >= iHauteur)
          v0 = max(v0, eval(i - 1, 1, oldH));
        else {
          v0 = max(v0, getSum(i - 1, oldH, h) + eval(i - 1, 0, oldH));
        }
        v1 = max(v1, v0);
        sol = max(sol, v1);
        dp[i][0].emplace_back(h, v0);
        dp[i][1].emplace_back(h, v1);
        // cout << i << ' ' << h << ' ' << v0 << ' ' << v1 << endl;
      }
    }
  }
  return sol;
  /*for (int i = 1; i < N; ++i)
    for (int h = 0; h <= N; ++h) {
      // 1
      for (int oldH = h + 1; oldH <= N; ++oldH) {
        int lo = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h, INF)) -
                 onCol[i].begin();
        int up =
            upper_bound(onCol[i].begin(), onCol[i].end(), pair(oldH, INF)) -
            onCol[i].begin();
        dp[i][h][1] =
            max(dp[i][h][1], prefSum[i][up] - prefSum[i][lo] +
                                 max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
      }
      // 0
      for (int oldH = 0; oldH <= N; ++oldH) {
        if (oldH >= h)
          dp[i][h][0] =
              max(dp[i][h][0], max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
        else {
          int lo = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
                               pair(oldH, INF)) -
                   onCol[i - 1].begin();
          int up = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
                               pair(h, INF)) -
                   onCol[i - 1].begin();
          dp[i][h][0] =
              max(dp[i][h][0],
                  dp[i - 1][oldH][0] + prefSum[i - 1][up] - prefSum[i - 1][lo]);
        }
      }
      sol = max({sol, dp[i][h][0], dp[i][h][1]});
    }
  return sol;*/
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1130 ms 820232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24564 KB Output is correct
2 Correct 32 ms 24568 KB Output is correct
3 Incorrect 77 ms 33052 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21221552654198'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24564 KB Output is correct
2 Correct 32 ms 24568 KB Output is correct
3 Incorrect 77 ms 33052 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21221552654198'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1130 ms 820232 KB Time limit exceeded
2 Halted 0 ms 0 KB -