Codeforces Round 641 (Div. 2) 1350B - Orac and Models Solution

 

Problem Link : https://codeforces.com/problemset/problem/1350/B

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. int32_t main() {
5. ios_base::sync_with_stdio(0);
6. cin.tie(0);
7. int t;
8. cin >> t;
9. while (t--) {
10. int n ;
11. cin >> n ;
12. int a[n+2] , dp[n+2] ;
13. for ( int i = 1 ; i <= n ; i++ ) {
14. cin >> a[i] ;
15. dp[i] = 1 ;
16. }
17. int ans = 1;
18. for ( int i = 1 ; i <= n ; i++ ) {
19. for ( int j = i*2 ; j <= n ; j+=i ){
20. if ( a[i] < a[j] ){
21. dp[j] = max ( dp[j] , dp[i] + 1 ) ;
22. ans = max ( ans , dp[j] ) ;
23. }
24. }
25. }
26. cout << ans <<"\n" ;
27. }
28. }