/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 532.0 KiB
#3 Wrong Answer 1ms 532.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;

vector<int> closest_max_element(vector<int64_t> a) {
  int n = a.size();
  vector<int> r(n);
  stack<int> st;
  st.push(n);
  for (int i = n - 1; i >= 0; i--) {
    while (st.top() != n && a[st.top()] <= a[i]) st.pop();
    r[i] = st.top();
    st.push(i);
  }
  return r;
}
 
void solve() {
  int n;
  cin >> n;
  vector<int64_t> a(n);
  for (auto& ai : a) {
    cin >> ai;
  }
  vector<int64_t> b(n);
  for (auto& bi : b) {
    cin >> bi;
  }
  auto r = closest_max_element(a);
  a.push_back(0);
  vector<int64_t> suff(n + 9);
  vector<int64_t> mxVal(n + 9);
  int64_t mx = 0;
  for (int i = n - 1; i >= 0; i--) {
    suff[i] = mxVal[a[r[i]]] + b[i];
    mx = max(mx, suff[i]);
    mxVal[a[i]] = max(mxVal[a[i]], suff[i]);
  }
  int i = n - 1;
  while (i >= 0 && suff[i] != mx) i--;
  cout << n - i << '\n';
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1224 Maximize the max
Contest
LUCC Presents Intra LU Junior Programming Contest - Replay
Language
C++17 (G++ 13.2.0)
Submit At
2025-09-02 16:43:17
Judged At
2025-09-02 16:43:17
Judged By
Score
1
Total Time
1ms
Peak Memory
532.0 KiB