Language: C++

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <string>
#include <climits>

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector <vector <int>> vvi;
typedef vector <ll> vl;
typedef vector <vector <ll>> vvl;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;

//const int kINF = INT_MAX;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

template <typename type>
ostream &operator<<(ostream &out, const vector <type> &massive) {
    for (const type &i : massive) {
        out << i << ' ';
    }
    return out;
}

template <typename type>
void print(const vector <type> &massive, const string &sep, const string &end) {
    if (!massive.empty()) {
        cout << massive[0];
        for (int i = 1; i < massive.size(); ++i) {
            cout << sep << massive[i];
        }
    }
    cout << end;
}

template <typename type>
void print(const vector <type> &massive) {
    print(massive, " ", "\n");
}

template <typename type>
void print(const type &element, const string &end) {
    cout << element << end;
}

template <typename type>
void print(const type &element) {
    print(element, "\n");
}

struct capital {
    long long cash, stocks;

    void sell(const long long &cost) {
        cash += (cost * stocks);
        stocks = 0;
    }

    void buy(const long long &cost) {
        stocks += (cash / cost);
        cash -= (cash / cost * cost);
    }
};

capital max_cash(const capital &a, const capital &b) {
    if (a.cash > b.cash) {
        return a;
    } else if (a.cash == b.cash) {
        if (a.stocks > b.stocks) {
            return a;
        } else {
            return b;
        }
    } else {
        return b;
    }
}

capital max_stocks(const capital &a, const capital &b) {
    if (a.stocks > b.stocks) {
        return a;
    } else if (a.stocks == b.stocks) {
        if (a.cash > b.cash) {
            return a;
        } else {
            return b;
        }
    } else {
        return b;
    }
}

int clever(const int &n, const vector <int> &a) {
    int now_sum = 1000, stocks = 0, ans = now_sum;
    bool buying = true;
    for (int i = 0; i < n - 1; ++i) {
        if (buying) {
            if (a[i] < a[i + 1]) {
                buying = false;
                stocks += (now_sum / a[i]);
                now_sum -= (stocks * a[i]);
            }
        } else {
            if (a[i] > a[i + 1]) {
                buying = true;
                now_sum += (stocks * a[i]);
                stocks = 0;
            }
        }
        ans = max(ans, now_sum + stocks * a[i]);
    }
    if (!buying) {
        now_sum += (stocks * a[n - 1]);
        stocks = 0;
        ans = max(ans, now_sum);
    }

    return ans;
}

ostream &operator<<(ostream &out, const capital &a) {
    out << '[' << a.cash << ", " << a.stocks << ']';
    return out;
}

ostream &operator<<(ostream &out, const pair <capital, capital> &a) {
    out << '(' << a.first << ", " << a.second << ')';
    return out;
}

long long new_clever(const long long &n, const vector <long long> &a) {
    vector <pair <capital, capital>> dp(n + 1, {{0, 0}, {0, 0}}); // sell (max_stocks) - buy (max_cash)
    dp[0].first = dp[1].second = {1000, 0};

    long long ans = 1000;
    for (long long i = 1; i <= n; ++i) {
        for (long long j = i - 1; j >= 0; --j) {
            dp[i].first = max_stocks(dp[i].first, max_stocks(dp[j].first, dp[j].second));
            dp[i].second = max_cash(dp[i].second, max_cash(dp[j].first, dp[j].second));
        }
        dp[i].first.sell(a[i - 1]);
        dp[i].second.buy(a[i - 1]);
        ans = max(ans, max(dp[i].first.cash, dp[i].second.cash));
    }

    //print(dp, "\n", "\n");
    return ans;
}

void stress() {
    int n;
    vector <int> a;
    do {
        n = rand() % 5 + 1;
        a.resize(n);
        for (int &i : a) {
            i = rand() % 200 + 1;
        }
    } while (clever(n, a) == new_clever(n, a));
    print(n);
    print(a);
    print(clever(n, a));
    print(new_clever(n, a));
}

void solve() {
    long long n;
    cin >> n;
    vector <long long> a(n);
    for (long long &i : a) {
        cin >> i;
    }

    print(new_clever(n, a));
}

int main() {
    fast();

    //freopen("../input.txt", "r", stdin);
    solve();
    //stress();

    return 0;
}


Compiler output:
a.cc: In function 'void stress()':
a.cc:168:44: error: invalid initialization of reference of type 'const std::vector<long long int>&' from expression of type 'std::vector<int>'
  168 |     } while (clever(n, a) == new_clever(n, a));
      |                                            ^
a.cc:140:68: note: in passing argument 2 of 'long long int new_clever(const long long int&, const std::vector<long long int>&)'
  140 | long long new_clever(const long long &n, const vector <long long> &a) {
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~^
a.cc:172:25: error: invalid initialization of reference of type 'const std::vector<long long int>&' from expression of type 'std::vector<int>'
  172 |     print(new_clever(n, a));
      |                         ^
a.cc:140:68: note: in passing argument 2 of 'long long int new_clever(const long long int&, const std::vector<long long int>&)'
  140 | long long new_clever(const long long &n, const vector <long long> &a) {
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~^