fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4.  
  5. #define debug     cout << "ok\n";
  6. #define SQR(x)    (1LL * ((x) * (x)))
  7. #define MASK(i)   (1LL << (i))
  8. #define BIT(x, i) (((x) >> (i)) & 1)
  9. #define fi        first
  10. #define se        second
  11. #define pb        push_back
  12.  
  13. #define mp make_pair
  14. #define pii pair<int,int>
  15. #define pli pair<ll,int>
  16. #define vi vector<int>
  17.  
  18. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef unsigned int ui;
  24.  
  25. using namespace std;
  26.  
  27. const int M = 1e9 + 7;
  28. const int INF = 1e9 + 7;
  29. const ll INFLL = (ll)2e18 + 7LL;
  30. const ld PI = acos(-1);
  31.  
  32. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  33. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  34.  
  35. template<class _, class __>
  36.     bool minimize(_ &x, const __ y){
  37.         if(x > y){
  38.             x = y;
  39.             return true;
  40.         } else return false;
  41.     }
  42. template<class _, class __>
  43.     bool maximize(_ &x, const __ y){
  44.         if(x < y){
  45.             x = y;
  46.             return true;
  47.         } else return false;
  48.     }
  49.  
  50. template<class _,class __>
  51.     void Add(_ &x, const __ y) {
  52.         x += y;
  53.         if (x >= M) {
  54.             x -= M;
  55.         }
  56.         return;
  57.     }
  58.  
  59. template<class _,class __>
  60.     void Diff(_ &x, const __ y) {
  61.         x -= y;
  62.         if (x < 0) {
  63.             x += M;
  64.         }
  65.         return;
  66.     }
  67.  
  68. //--------------------------------------------------------------
  69.  
  70. const int MaxN = 2e5+7;
  71.  
  72. int n,k,a[MaxN],f[MaxN][3],cnt_f[MaxN][3],Cost;
  73. vi b,c;
  74.  
  75. pii Get(int Cost,vi & a) {
  76.     f[0][1] = -INFLL;
  77.     f[0][2] = -INFLL;
  78.     f[0][0] = 0;
  79.     cnt_f[0][0] = 0;
  80.     for (int i=1;i<=n;i++) {
  81.         for (int j=0;j<3;j++) f[i][j] = f[i-1][j], cnt_f[i][j] = cnt_f[i-1][j];
  82.         if (maximize(f[i][0],f[i-1][1] + a[i] - Cost)) cnt_f[i][0] = cnt_f[i-1][1] + 1;
  83.         if (maximize(f[i][0],f[i-1][2] - a[i] - Cost)) cnt_f[i][0] = cnt_f[i-1][2] + 1;
  84.         if (maximize(f[i][1],f[i-1][0] - a[i])) cnt_f[i][1] = cnt_f[i-1][0];
  85.         if (maximize(f[i][2],f[i-1][0] + a[i])) cnt_f[i][2] = cnt_f[i-1][0];
  86.     }
  87.     return mp(f[n][0],cnt_f[n][0]);
  88. }
  89.  
  90. pii Calc(int Cost) {
  91.     pii tmp1 = Get(Cost,b);
  92.     pii tmp2 = Get(Cost,c);
  93.     if (tmp1.fi > tmp2.fi) return tmp1;
  94.     if (tmp1.fi < tmp2.fi) return tmp2;
  95.     return mp(tmp1.fi,min(tmp1.se,tmp2.se));
  96. }
  97.  
  98. void sol() {
  99.     cin >> n >> k;
  100.     for (int i=1;i<=n;i++) cin >> a[i];
  101.     int p = 0;
  102.     for (int i=1;i<=n;i++) if (a[i] > a[p]) p = i;
  103.     b.pb(0);
  104.     c.pb(0);
  105.     for (int i=p;i<=n;i++) b.pb(a[i]);
  106.     for (int i=1;i<p;i++) b.pb(a[i]);
  107.     for (int i=p+1;i<=n;i++) c.pb(a[i]);
  108.     for (int i=1;i<=p;i++) c.pb(a[i]);
  109.     Cost = 0;
  110.     int l = 1, r = 1e14;
  111.     while (l <= r) {
  112.         int mid = (l+r) >> 1;
  113.         if (Calc(mid).se >= k) {
  114.             Cost = mid;
  115.             l = mid + 1;
  116.         }
  117.         else r = mid - 1;
  118.     }
  119.     cout << Calc(Cost).fi + Cost * k;
  120. }
  121.  
  122. signed main() {
  123.     freopen("KHONGBIETLAM.inp","r",stdin);
  124.     freopen("KHONGBIETLAM.out","w",stdout);
  125.     FAST
  126.     int t=1;
  127. //    cin >> t;
  128.     while (t--) sol();
  129. }
  130.  
Success #stdin #stdout 0.01s 5908KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/06KqfL
language:
C++14 (gcc 8.3)
created:
8 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!