Submission #1280742

#TimeUsernameProblemLanguageResultExecution timeMemory
1280742vuquangsangMoney (IZhO17_money)C++20
100 / 100
988 ms63072 KiB
#include <bits/stdc++.h> using namespace std; #define el "\n" #define FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++) #define FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--) #define pb push_back #define fi first #define se second #define all(x) x.begin(),x.end() #define lg(x) __lg(x) #define alla(a,n) a+1,a+n+1 #define ll long long template <class T> bool maxi(T &x, T y) { if(x < y) { x = y ; return true ;} return false;} template <class T> bool mini(T &x, T y) { if(x > y) { x = y ; return true ;} return false;} const int N = 1e6 + 2; const int INF = 1e9 + 2; int n, a[N]; void inp() { cin >> n; FOR(i, 1, n) cin >> a[i]; } /* Try your best No regrets */ namespace subtask_3 { int dp[N]; void slv() { FOR(i, 1, n) dp[i] = INF; FOR(i, 1, n) { dp[i] = min(dp[i], dp[i - 1] + 1); FORD(j, i - 1, 1) { if(a[j] > a[j + 1]) break; bool ok = 1; FOR(t, 1, j - 1) { if(a[j] < a[t] && a[t] < a[i]) ok = 0; } if(!ok) break; mini(dp[i], dp[j - 1] + 1); } } cout << dp[n]; } } namespace subtask_4 { int left[N]; int valLeft[N]; int dp[N]; void slv() { left[1] = 1; for(int i = 2; i <= n; i++) { left[i] = (a[i] >= a[i - 1] ? left[i - 1] : i); } set<int> S; a[0] = INF; valLeft[0] = INF; for(int i = 0; i < n; i++) { S.insert(a[i]); if(i > 0) valLeft[i] = *S.upper_bound(a[i + 1]); } for(int i = 1; i <= n; i++) dp[i] = INF; for(int i = 1; i <= n; i++) { int l = left[i], r = i, mid, pos = i; while(l <= r) { mid = (r + l) >> 1; if(valLeft[mid - 1] >= a[i]) pos = mid, r = mid - 1; else l = mid + 1; } dp[i] = dp[pos - 1] + 1; } cout << dp[n]; } } /* Code slowly, think carefully */ main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define __Azul__ "money" if(fopen(__Azul__".inp", "r")) { freopen(__Azul__".inp", "r", stdin); freopen(__Azul__".out", "w", stdout); } bool qs = 0; int T = 1; if(qs) cin >> T; while(T--) { inp(); subtask_4::slv(); } cerr << "\nTime" << 0.001 * clock() << "s "; return 0; }

Compilation message (stderr)

money.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main()
      | ^~~~
money.cpp: In function 'int main()':
money.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(__Azul__".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
money.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(__Azul__".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...