fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxN = 1e5 + 10;
  4.  
  5. int n, m, a[maxN], star[2010], sum[2*maxN], f[maxN], g[maxN], cnt[maxN];
  6. struct TData
  7. {
  8.     int st, en;
  9. } mon[maxN];
  10.  
  11. int main()
  12. {
  13.  
  14.     cin >> n >> m;
  15.     for (int i = 1; i <= n; ++i)
  16.         cin >> a[i];
  17.     sort(a + 1, a + 1 + n);
  18.     a[0] = -10;
  19.     int tmp = 0;
  20.     for (int i = 1; i <= n; ++i)
  21.         if (a[i] == a[i - 1] + 1)
  22.             ++mon[tmp].en;
  23.         else mon[++tmp].st = mon[tmp].en = a[i];
  24.     n = tmp;
  25.  
  26.     for (int i = 1; i <= m; ++i)
  27.     {
  28.         cin >> star[i];
  29.         ++sum[star[i]];
  30.     }
  31.     sort(star + 1, star + 1 + m);
  32.     for (int i = 1; i < 2*maxN; ++i)
  33.         sum[i] += sum[i - 1];
  34.  
  35.     for (int i = 1; i <= n; ++i)
  36.     {
  37.         g[i] = max(g[i], g[i - 1]);
  38.         for (int j = 1; j <= m; ++j)
  39.         {
  40.             int l = star[j], r = mon[i].st;
  41.             if (l > r) break;
  42.             if (i - (r - l + 1) >= 0)
  43.                 {
  44.                     f[i] = max(f[i], g[i - (r - l + 1)] + sum[r] - sum[l - 1] + sum[mon[i].en] - sum[mon[i].st - 1]);
  45. //                    cout << "nom " << i << ' ' << g[i - (r - l + 1)] << ' ' << r << ' ' << l << endl;
  46.                 }
  47.  
  48.         }
  49.         for (int j = m; j >= 1; --j)
  50.         {
  51.             int l = mon[i].en, r = star[j];
  52.             if (l > r) break;
  53.             if (i + (r - l) <= n)
  54.                 g[i + (r - l)] = max(g[i + (r - l)], f[i] + sum[r] - sum[l] + sum[mon[i].en] - sum[mon[i].st - 1]);
  55.         }
  56.         g[i] = max(g[i], f[i]);
  57. //        cout << i << ' ' << g[i] << ' ' << f[i] << endl;
  58.     }
  59.     cout << g[n];
  60. }
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
5 3
5 6 1 7 2
8 1 9
stdout
copy 
Standard output is empty
https://ideone.com/uOz762
language:
C++14 (gcc 8.3)
created:
4 years 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!