제출 #1193439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193439		loom	Arcade (NOI20_arcade)	C++20	100 / 100	141 ms	16556 KiB

Arcade

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

inline void solve(){
   int m, n;
   cin>>m>>n;
   int t[n], a[n];
   vector<pair<int,int>> v;

   for(int i=0; i<n; i++) cin>>t[i];
   for(int i=0; i<n; i++){
      cin>>a[i];
      v.push_back({t[i]+a[i], t[i]-a[i]});
   }
   sort(v.begin(), v.end());

   vector<int> lis;
   for(int i=0; i<n; i++){
      int x = -v[i].second;

      if(lis.empty() or lis.back() < x){
         lis.push_back(x);
         continue;
      }

      lis[lower_bound(lis.begin(), lis.end(), x) - lis.begin()] = x;
   }

   cout<<lis.size();
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) 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