fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int long long int
  5. #define ld long double
  6. #define all(x) x.begin(), x.end()
  7. #define sortall(x) sort(all(x))
  8. #define endl '\n'
  9. #define yes cout<<"YES\n";
  10. #define no cout<<"NO\n";
  11. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  12. /*
  13.  * Think twice, code once
  14.  * Think of different approaches to tackle a problem: write them down.
  15.  * Think of different views of the problem. don't look from only one side.
  16.  * don't get stuck in one approach.
  17.  * common mistakes: - over_flow
  18.  *                  - out_of_bound index
  19.  *                  - infinite loop
  20.  *                  - corner cases
  21.  *                  - duplication counting.
  22. */
  23.  
  24.  
  25. void solve()
  26. {
  27.     int n, m; cin >> n >> m;
  28.     vector<int> v(n);
  29.     for (auto&i:v)
  30.         cin >> i;
  31.     map<int, int> freq;
  32.     for (int i = 0; i < m; ++i)
  33.         freq[v[i]]++;
  34.     int mxElement = 0, mxFreq = 0;
  35.     for (map<int, int>::iterator i = freq.begin(); i != freq.end(); ++i)
  36.     {
  37.         if (i->second > mxFreq)
  38.         {
  39.             mxFreq = i->second;
  40.             mxElement = i->first;
  41.         }
  42.         else if (i->second == mxFreq)
  43.             mxElement = max(mxElement, i->first);
  44.     }
  45.     int ans = mxElement;
  46.     int l = 1, r = m;
  47.     while (r < n)
  48.     {
  49.         freq[v[l-1]]--, freq[v[r]]++;
  50.         if (!freq[v[l-1]]) freq.erase(v[l-1]);
  51.         if (freq[v[r]] > mxFreq || (freq[v[r]] == mxFreq && v[r] > mxElement))
  52.         {
  53.             mxElement = v[r];
  54.             mxFreq = freq[v[r]];
  55.         }else if (v[l-1] == mxElement && freq[v[l-1]] < mxFreq)
  56.         {
  57.             mxElement = 0, mxFreq = 0;
  58.             for (map<int, int>::iterator i = freq.begin(); i != freq.end(); ++i)
  59.             {
  60.                 if (i->second > mxFreq)
  61.                 {
  62.                     mxElement = i->first;
  63.                     mxFreq = i->second;
  64.                 }
  65.                 else if (i->second == mxFreq)
  66.                     mxElement = max(mxElement, i->first);
  67.             }
  68.         }
  69.         // cout << mxElement << ' ' << mxFreq << '\n';
  70.         l++, r++;
  71.         ans += mxElement;
  72.     }
  73.     cout << ans;
  74. }
  75.  
  76. int32_t main()
  77. {
  78.     fast
  79.     int t = 1;
  80.     // cin >> t;
  81.     while (t--)
  82.     {
  83.         solve();
  84.         if (t) cout << '\n';
  85.     }
  86.     cout << '\n';
  87.     return 0;
  88. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/PLO4Ht
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!