Submission #1302709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302709		SmuggingSpun	Money (IZhO17_money)	C++20	100 / 100	769 ms	63056 KiB

money

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
template<class T>void minimize(T& a, T b){
  if(a > b){
    a = b;
  }
}
int n;
namespace sub12{
  void solve(){
    vector<int>a(n);
    for(int& x : a){
      cin >> x;
    }
    int ans = n;
    for(int mask = (1 << (n - 1)) - 2; mask > -1; mask--){
      vector<pair<int, int>>range(1, make_pair(0, 0));
      bool flag = true;
      for(int i = 1; i < n; i++){
        if(1 << (i - 1) & mask){
          range.emplace_back(i, i);
        }
        else{
          if(a[i] < a[range.back().second]){
            flag = false;
            break;
          }
          range.back().second = i;
        }
      }
      if(flag && range.size() < ans){
        vector<int>b;
        for(auto& it : range){
        	int l = it.first, r = it.second;
          if(b.empty()){
            b = vector<int>(a.begin() + l, a.begin() + r + 1);
            continue;
          }
          if(a[r] <= b[0]){
            b.insert(b.begin(), a.begin() + l, a.begin() + r + 1);
          }
          else if(a[l] >= b.back()){
            b.insert(b.end(), a.begin() + l, a.begin() + r + 1);
          }
          else{
            flag = false;
            for(int i = 0; i + 1 < b.size() && !flag; i++){
              if(b[i] <= a[l] && b[i + 1] >= a[r]){
                b.insert(b.begin() + i + 1, a.begin() + l, a.begin() + r + 1);
                flag = true;
              }
            }
            if(!flag){
              break;
            }
          }
        }
        if(flag){
          ans = range.size();
        }
      }
    }
    cout << ans;
  }
}
namespace sub3{
  void solve(){
    vector<int>a(n + 1), dp(n + 1, n);
    for(int i = 1; i <= n; i++){
      cin >> a[i];
    }
    vector<vector<int>>b(n + 1);
    for(int i = 1; i <= n; i++){
      b[i] = b[i - 1];
      b[i].emplace_back(a[i]);
      for(int j = int(b[i].size() - 1); j > 0 && b[i][j] < b[i][j - 1]; j--){
        swap(b[i][j], b[i][j - 1]);
      }
    }
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
      for(int j = i; j > 0; j--){
        if(j < i && a[j] > a[j + 1]){
          break;
        }
        if(b[j - 1].empty() || b[j - 1][0] >= a[i] || b[j - 1].back() <= a[j] || b[j - 1][upper_bound(b[j - 1].begin(), b[j - 1].end(), a[j]) - b[j - 1].begin()] >= a[i]){
          minimize(dp[i], dp[j - 1] + 1);
        }
      }
    }
    cout << dp[n];
  }
}
namespace sub4{
  const int lim = 1e6 + 5;
  const int INF = 1e9;
  int a[lim], right[lim], left[lim], dp[lim];
  void solve(){
    set<int>s;
    s.insert(right[left[0] = a[0] = dp[0] = 0] = INF);
    for(int i = 1; i <= n; i++){
      cin >> a[i];
      left[i] = (a[i] >= a[i - 1] ? left[i - 1] : i);
    }
    for(int i = 1; i < n; i++){
      s.insert(a[i]);
      right[i] = *s.upper_bound(a[i + 1]);
    }
    for(int i = 1; i <= n; i++){
      int low = left[i], high = i, p;
      while(low <= high){
        int mid = (low + high) >> 1;
        if(right[mid - 1] >= a[i]){
          high = (p = mid) - 1;
        }
        else{
          low = mid + 1;
        }
      }
      dp[i] = dp[p - 1] + 1;
    }
    cout << dp[n];
  }
}
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if(fopen(taskname".inp", "r")){
    freopen(taskname".inp", "r", stdin);
  }
  cin >> n;
  if(n <= 20){
    sub12::solve();
  }
  else if(n <= 300){
    sub3::solve();
  }
  else{
    sub4::solve();
  }
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:129:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55