fork download
copy 
  1. #include <iostream>
  2. #include <utility>
  3. #include <vector>
  4.  
  5. using namespace std;
  6. constexpr int MAX = 1'000'000'000;
  7.  
  8. pair<bool, int> f(long double alpha, vector<int> &c) {
  9.     int n = c.size();
  10.     vector<int> jumps(n, 0);
  11.     vector<long double> dp(n, -static_cast<long double>(MAX));
  12.     dp[0] = static_cast<long double>(c[0]);
  13.     int besti = 0;
  14.     for (int i = 1; i < n; i++) {
  15.         dp[i] = static_cast<long double>(-i) - alpha + dp[besti] + static_cast<long double>(besti);
  16.         jumps[i] = jumps[besti]+1;
  17.         if (dp[i] < -alpha*static_cast<long double>(jumps[i])) dp[i] = -static_cast<long double>(MAX);
  18.         else dp[i] += c[i];
  19.         cout << besti << endl;
  20.         if (dp[besti]+static_cast<long double>(besti) < dp[i]+static_cast<long double>(i)) besti = i;
  21.     }
  22.     return {dp[n-1] >= -alpha*static_cast<long double>(jumps[n-1]), jumps[n-1]};
  23. }
  24.  
  25. int main() {
  26.     int n;
  27.     cin >> n;
  28.     vector<int> c(n);
  29.     for (auto& i : c) cin >> i;
  30.     auto res = f(1.999, c);
  31.     if (!res.first) {
  32.         cout << "BRAK\n";
  33.         return 0;
  34.     } else {
  35.         cout << res.second << endl;
  36.     }
  37. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10
1 2 5 10 1 2 2 7 6 7
stdout
copy 
0
1
2
3
3
5
6
7
8
8
https://ideone.com/LlAsVc
language:
C++14 (gcc 8.3)
created:
16 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!