fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)a.size()
  8. #define FILL(a, x) memset(a, x, sizeof(a))
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<int, int> ii;
  13. const int N = (int)1e6 + 3;
  14.  
  15. int n, j;
  16. ll M;
  17. ll posArr[N + 5];
  18.  
  19. bool canJump(ll L) {
  20.     int pos = 0;
  21.     int used = 0;
  22.     while (pos < n && used < j) {
  23.         int nxt = pos;
  24.         while (nxt + 1 <= n && posArr[nxt + 1] - posArr[pos] <= L) ++nxt;
  25.         if (nxt == pos) return false;
  26.         pos = nxt;
  27.         ++used;
  28.     }
  29.     return pos == n;
  30. }
  31.  
  32. int main() {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL); cout.tie(NULL);
  35.     freopen("river.inp", "r", stdin);
  36.     freopen("river.out", "w", stdout);
  37.  
  38.     cin >> n >> M >> j;
  39.  
  40.     posArr[0] = 0;
  41.     ll maxD = 0;
  42.     FOR(i, 0, n - 1) {
  43.         ll d = 1 + ( ( (ll)i * (ll)i ) % M );
  44.         posArr[i + 1] = posArr[i] + d;
  45.         if (d > maxD) maxD = d;
  46.     }
  47.  
  48.     ll lo = maxD;
  49.     ll hi = posArr[n];
  50.     ll ans = hi;
  51.  
  52.     while (lo <= hi) {
  53.         ll mid = (lo + hi) >> 1;
  54.         if (canJump(mid)) {
  55.             ans = mid;
  56.             hi = mid - 1;
  57.         } else {
  58.             lo = mid + 1;
  59.         }
  60.     }
  61.  
  62.     cout << ans;
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/H7ONKa
language:
C++14 (clang 8.0)
created:
7 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!