fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 250;
  9. const int INF = 1e9;
  10. const ll LINF = 1e18;
  11.  
  12. int n, k, dpmin[maxn + 10], dpmax[maxn + 10];
  13. ll a[maxn + 10], ans = LINF, pre[maxn + 10];
  14. vector<ll> s;
  15. deque<int> dq;
  16.  
  17. bool check(ll l, ll r)
  18. {
  19.     memset(dpmin, 0, sizeof dpmin);
  20.     memset(dpmax, 0, sizeof dpmax);
  21.     while (dq.size())
  22.         dq.pop_back();
  23.  
  24.     int p = 1, q = 1;
  25.  
  26.     for (int i = 1; i <= n; i++)
  27.     {
  28.         while (pre[i] - pre[p - 1] >= l)
  29.         {
  30.             if (dpmin[p - 1] != INF)
  31.                 dq.push_back(p - 1);
  32.             p++;
  33.         }
  34.         while (pre[i] - pre[q - 1] > r)
  35.             q++;
  36.         while (dq.size() && dq.front() < q - 1)
  37.             dq.pop_front();
  38.         if (dq.size())
  39.         {
  40.             dpmin[i] = dpmin[dq.front()] + 1;
  41.             dpmax[i] = dpmax[dq.back()] + 1;
  42.         }
  43.         else
  44.             dpmin[i] = dpmax[i] = INF;
  45.     }
  46.  
  47. //    for (int i = 1; i <= n; i++)
  48. //        cout << dpmin[i] << ' ' << dpmax[i], el;
  49.     return dpmin[n] <= k && k <= dpmax[n];
  50. }
  51.  
  52. int main()
  53. {
  54.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  55.     if (fopen("GIFTS.INP", "r"))
  56.     {
  57.         freopen("GIFTS.INP", "r", stdin);
  58.         freopen("GIFTS.OUT", "w", stdout);
  59.     }
  60.  
  61.     cin >> n >> k;
  62.     for (int i = 1; i <= n; i++)
  63.     {
  64.         cin >> a[i];
  65.         pre[i] = pre[i - 1] + a[i];
  66.     }
  67.     for (int i = 1; i <= n; i++)
  68.         for (int j = i; j <= n; j++)
  69.             s.push_back(pre[j] - pre[i - 1]);
  70.     sort(s.begin(), s.end());
  71.     int j = 0;
  72.     for (int i = 0; i < s.size(); i++)
  73.     {
  74.         while (check(s[j], s[i]))
  75.         {
  76.             ans = min(ans, s[i] - s[j]);
  77.             j++;
  78.         }
  79.     }
  80.     cout << ans;
  81. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/wQctCb
language:
C++14 (gcc 8.3)
created:
4 hours 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!