Submission #1125851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125851		fryingduc	Arcade (NOI20_arcade)	C++17	100 / 100	162 ms	6564 KiB

Arcade

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5e5 + 5;
int n, m;
int a[maxn], t[maxn];
int ord[maxn];
void solve() {
  cin >> n >> m;
  for(int i = 1; i <= m; ++i) {
    cin >> t[i];
  }
  for(int i = 1; i <= m; ++i) {
    cin >> a[i];
    ord[i] = i;
  }
  // rotate 45 ccw 
  // MIS on dag
  sort(ord + 1, ord + m + 1, [](const int &x, const int &y) -> bool {
    if(t[x] - a[x] != t[y] - a[y]) return t[x] - a[x] > t[y] - a[y];
    return t[x] + a[x] > t[y] + a[y];
  });
  vector<int> vec;
  for(int i = 1; i <= m; ++i) {
    auto it = lower_bound(vec.begin(), vec.end(), t[ord[i]] + a[ord[i]]);
    if(it == vec.end()) vec.push_back(t[ord[i]] + a[ord[i]]);
    else *it = t[ord[i]] + a[ord[i]];
  }
  cout << (int)vec.size();
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15