oj.uz

답안 #659606

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

const int INF = 1e18;

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);
    interesting[i].push_back(N);
    sort(interesting[i].begin(), interesting[i].end());
    interesting[i].resize(unique(interesting[i].begin(), interesting[i].end()) -
                          interesting[i].begin());
  }
  array<vector<pair<int, int>>, 2> oldDp, suffixMax;
  for (int i = 0; i < 2; ++i) {
    for (int x : interesting[0]) {
      oldDp[i].emplace_back(x, 0);
      suffixMax[i].emplace_back(x, 0);
    }
  }

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

  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();
    vector<pair<int, int>> dp0, dp1;
    int curOld = 0;
    int cntBefore = interesting[i - 1].size();
    vector<int> prevI(cntBefore);
    int curPos = 0;
    int curSum = 0;
    for (int jHauteur = 0; jHauteur < cntBefore; ++jHauteur) {
      int oldH = interesting[i - 1][jHauteur];
      prevI[jHauteur] = oldDp[1][jHauteur].second;
      while (curPos < (int)onCol[i].size() and onCol[i][curPos].first <= oldH)
        curSum += onCol[i][curPos++].second;
      prevI[jHauteur] += curSum;
    }
    for (int j = cntBefore - 2; j >= 0; --j)
      prevI[j] = max(prevI[j], prevI[j + 1]);

    for (int iHauteur = 0; iHauteur < nbInteressants; ++iHauteur) {
      int h = interesting[i][iHauteur];
      // 1
      int v1 = 0;
      int v0 = 0;
      while (curOld < cntBefore and interesting[i - 1][curOld] <= h)
        ++curOld;
      assert(curOld);
      v0 = suffixMax[1][curOld - 1].second;
      if (curOld < cntBefore)
        v1 = max(v1, prevI[curOld] - getSum(i, 0, h - 1));
      for (int jHauteur = 0; jHauteur < (int)interesting[i - 1].size();
           ++jHauteur) {
        int oldH = interesting[i - 1][jHauteur];
        // if (oldH > h)
        // v1 = max(v1, getSum(i, h, oldH) + eval(1, oldH));
        if (oldH < h)
          v0 = max(v0, getSum(i - 1, oldH, h) + eval(0, oldH));
      }
      v1 = max(v1, v0);
      sol = max(sol, v1);
      dp0.emplace_back(h, v0);
      dp1.emplace_back(h, v1);
      // cout << i << ' ' << h << ' ' << v0 << ' ' << v1 << endl;
    }
    oldDp[0] = move(dp0);
    oldDp[1] = move(dp1);
    suffixMax[0] = oldDp[0];
    suffixMax[1] = oldDp[1];
    for (int h = nbInteressants - 2; h >= 0; --h)
      for (int side = 0; side < 2; ++side)
        suffixMax[side][h].second =
            max(suffixMax[side][h].second, suffixMax[side][h + 1].second);
  }
  return sol;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1086 ms 31276 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 13604 KB Output is correct
2 Correct 39 ms 13536 KB Output is correct
3 Incorrect 75 ms 17472 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '23377109270875'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '218543882738'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '218543882738'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '218543882738'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 13604 KB Output is correct
2 Correct 39 ms 13536 KB Output is correct
3 Incorrect 75 ms 17472 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '23377109270875'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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