fork download
copy 
  1.  
  2.     #include <bits/stdc++.h>
  3.  
  4.     using namespace std;
  5.  
  6.     using ll = long long;
  7.     const int MOD = 1000000007; 
  8.     const int MOD2 =  998244353; 
  9.     const ll INF = 1e18;
  10.     const int MX = 1000001; //check the limits, dummy
  11.  
  12.  
  13.     ll modExp(ll base, ll power) {
  14.         if (power == 0) {
  15.             return 1;
  16.         } else {
  17.             ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
  18.             if (power % 2 == 1) cur = cur * base;
  19.             cur = cur % MOD;
  20.             return cur;
  21.         }
  22.     }
  23.  
  24.     ll inv(ll base) {
  25.         return modExp(base, MOD-2);
  26.     }
  27.  
  28.  
  29.     ll mul(ll A, ll B) {
  30.         return (A*B)%MOD;
  31.     }
  32.  
  33.     ll add(ll A, ll B) {
  34.         return (A+B)%MOD;
  35.     }
  36.  
  37.     ll dvd(ll A, ll B) {
  38.         return mul(A, inv(B));
  39.     }
  40.  
  41.     ll sub(ll A, ll B) {
  42.         return (A-B+MOD)%MOD;
  43.     }
  44.     ll cielDiv(ll A , ll B) {
  45.         return (A + B - 1)/B;
  46.     } 
  47.  
  48.     ll* facs = new ll[MX];
  49.     ll* facInvs = new ll[MX];
  50.  
  51.     ll choose(ll a, ll b) {
  52.         if (b > a) return 0;
  53.         if (a < 0) return 0;
  54.         if (b < 0) return 0;
  55.         ll cur = facs[a];
  56.         cur = mul(cur, facInvs[b]);
  57.         cur = mul(cur, facInvs[a-b]);
  58.         return cur;
  59.     }
  60.  
  61.  
  62.     void initFacs() {
  63.         facs[0] = 1; 
  64.         facInvs[0] = 1;
  65.         for (int i = 1 ; i < MX ; i ++ ) {
  66.             facs[i] = (facs[i-1] * i) % MOD;
  67.             facInvs[i] = inv(facs[i]);
  68.         }
  69.     }
  70.  
  71.  
  72.  
  73.  
  74.     int f(int a , int x) {
  75.         if (a > x) {
  76.             return 1;
  77.         } 
  78.         if (a == x) {
  79.             return 0; 
  80.         }
  81.         return -1;
  82.     }
  83.  
  84.     void solve() { 
  85.         int n ; cin >> n;
  86.         vector<int> arr(n); 
  87.         for (int i = 0 ; i < n; i ++) {
  88.             cin >> arr[i];
  89.         }
  90.         vector<vector<int>> dp(n + 1, vector<int> (3,0)); 
  91.         for (int i = 0 ; i < n; i ++) {
  92.             dp[i+1][0] = dp[i][0] + f(dp[i][0], arr[i]);             // still haven’t skipped, apply rating
  93.             dp[i+1][1] =         dp[i][0];                // start skipping right before contest i+1
  94.             dp[i+1][1] = max(dp[i+1][1], dp[i][1]);       // or we were already in skip
  95.             dp[i+1][2] = max(
  96.                 f(dp[i][1], arr[i]),                      // finish skipping immediately at i
  97.                 f(dp[i][2], arr[i])                       // or we’ve already finished skipping
  98.             );
  99.         }
  100.  
  101.  
  102.         cout << max(dp[n][1], dp[n][2]) << endl; 
  103.  
  104.     }
  105.     int main()  {
  106.         ios_base::sync_with_stdio(0); cin.tie(0);  
  107.  
  108.         int t;
  109.          cin >> t; 
  110.         while (t --) {
  111.             solve(); 
  112.         }
  113.         return 0;
  114.     }
  115.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10
stdout
copy 
0
0
0
0
0
https://ideone.com/LhOolD
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!