Submission #49550034

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    ValueVector A(N + 1);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    ValueVector FirstPos(11, -1);

    ValueMatrix SecondPos(11, ValueVector(11, -1));

    valueType ans = 0;

    valueType l = -1;
    
    for (valueType i = 1; i <= N; ++i) {
        for (valueType j = 1; j <= 10; ++j) {
            valueType const diff = A[i] - j;

            valueType const first = j - diff;

            if (first < 1 || first > 10)
                continue;

            l = std::max(l, SecondPos[j][first]);
        }

        if (l != -1)
            ans += l;

        for (valueType j = 1; j <= 10; ++j)
            SecondPos[A[i]][j] = std::max(SecondPos[A[i]][j], FirstPos[j]);

        FirstPos[A[i]] = i;
    }

    std::cout << ans << std::endl;

    return 0;
}

Submission Info

Judge Result