fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ld long double
  3. using namespace std;
  4. #define IO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  5. typedef long long ll;
  6.  
  7. char file_name[100];
  8.  
  9. void set_output_path(string s)
  10. {
  11.     strcpy(file_name, s.c_str());
  12.     // cout << file_name << '\n';
  13.     freopen(file_name, "w", stdout);
  14. }
  15.  
  16. string get_id(int num)
  17. {
  18.     if (num < 10)
  19.         return "0" + to_string(num);
  20.     return to_string(num);
  21. }
  22.  
  23. void set_output_in(int num)
  24. {
  25.     set_output_path(get_id(num) + ".in");
  26. }
  27.  
  28. void set_output_ok(int num)
  29. {
  30.     set_output_path(get_id(num) + ".ok");
  31. }
  32.  
  33.  
  34. const int N = 1001, K = 51, INF = 1e9;
  35.  
  36. int n, k, a[N], mem[N][N][K][2];
  37.  
  38. int dp(int i, int pre, int cnt_lm, bool pre_is_greaterThan_prepre)
  39. {
  40.     if (cnt_lm > k) return INF;
  41.     if (i == n + 1) return cnt_lm == k ? 0 : INF;
  42.  
  43.     auto &ret = mem[i][pre][cnt_lm][pre_is_greaterThan_prepre];
  44.     if (~ret) return ret;
  45.  
  46.     int c1 = 1 + dp(i + 1, pre, cnt_lm, pre_is_greaterThan_prepre); // leaave
  47.     int c2 = INF;   // try to pick
  48.  
  49.     if (a[i] < a[pre] && pre_is_greaterThan_prepre)
  50.     {
  51.         c2 = dp(i + 1, i, cnt_lm + 1, 0);
  52.     }
  53.     else
  54.     {
  55.         c2 = dp(i + 1, i, cnt_lm, a[i] > a[pre]);
  56.     }
  57.     return ret = min(c1, c2);
  58. }
  59.  
  60. void solve()
  61. {
  62.     a[0] = INF;
  63.     memset(mem, -1, sizeof mem);
  64.     auto ans = dp(1, 0, 0, 0);
  65.     if (ans == INF)
  66.     {
  67.         ans = -1;
  68.     }
  69.     cout << ans;
  70. }
  71.  
  72. void out(int tt, int lim)
  73. {
  74.     set_output_in(tt);
  75.     cout << lim << ' ';
  76.     n = lim;
  77.     int k = rand() % 50 + 1;
  78.     cout << k << '\n';
  79.     int N = 1e9;
  80.     for (int tc = 1; tc <= lim; tc++)
  81.     {
  82.         int z = rand() % N + 1;
  83.         a[tc] = z;
  84.         cout << z << '\n';
  85.     }
  86.     set_output_ok(tt);
  87.     solve();
  88.     // for (int tc = 1; tc <= lim; tc++)
  89.     // {
  90.     //   solve(tc);
  91.     // }
  92. }
  93. int main()
  94. {
  95.     ///cout << fixed << setprecision(10);
  96.     srand(0);
  97.     // IO;
  98.     ///int tc = 1, tt = 2;
  99.     for (int i = 3; i <= 5; i++)
  100.     {
  101.         out(i, 10);
  102.     }
  103.     for (int i = 6; i <= 10; i++)
  104.     {
  105.         out(i, 100);
  106.     }
  107.     for (int i = 11; i <= 15; i++)
  108.     {
  109.         out(i, 1000);
  110.     }
  111.     for (int i = 15; i <= 20; i++)
  112.     {
  113.         out(i, 500);
  114.     }
  115. //    for (int i = 21; i <= 23; i++)
  116. //    {
  117. //        out(i, 100000);
  118. //    }
  119.     // out(4, 100);
  120.     // out(4, 1000);
  121.     // out(6, 100000);
  122.     // out(8, 1000000);
  123.     // solve();
  124. }
  125.  
Success #stdin #stdout 0.77s 403016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lvo03X
language:
C++14 (gcc 8.3)
created:
6 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!