結果

問題 No.3257 +|+
ユーザー dp_ijk
提出日時 2025-09-05 22:39:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,804 ms / 3,000 ms
コード長 3,184 bytes
コンパイル時間 1,782 ms
コンパイル使用メモリ 173,956 KB
実行使用メモリ 22,228 KB
最終ジャッジ日時 2025-09-05 22:40:01
合計ジャッジ時間 45,842 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>
struct IOSetup {
    IOSetup() {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(15);
        std::cerr << std::fixed << std::setprecision(8);
    }
};
IOSetup iosetup;
using ll = int64_t;
using int128_t = __int128;
using uint128_t = unsigned __int128;
template <typename T>
constexpr auto rep_iota_impl(T start, T stop) noexcept {
    return std::views::iota(start, (start < stop ? stop : start));
}
template <typename T = int64_t>
inline constexpr auto rep_impl(auto start, auto stop) noexcept {
    return rep_iota_impl<T>(start, stop);
}
template <class... Ts>
inline void read(Ts&... ts) {
    (std::cin >> ... >> ts);
}
template <typename T = int64_t>
std::vector<T> VEC(int size) {
    std::vector<T> res(size);
    for (T& x : res)
        std::cin >> x;
    return res;
}
template <class Iterable>
auto max(const Iterable& A) {
    if (A.empty()) { assert(false); }
    return *std::max_element(A.begin(), A.end());
}
using std::vector;
inline constexpr uint32_t pow_mod_uint32(auto base, int64_t exp, uint32_t mod) {
    assert(0 <= exp);
    assert(mod != 0);
    return pow_mod_constexpr<uint32_t, uint64_t>(safe_mod_uint(base, mod), exp, mod);
}
inline uint64_t pow_mod_uint64(auto base, int64_t exp, uint64_t mod) {
    using uint128_t = unsigned __int128;
    assert(0 <= exp);
    assert(mod != 0);
    return pow_mod_constexpr<uint64_t, uint128_t>(safe_mod_uint(base, mod), exp, mod);
}
template <typename T>
void put(const T& t) {
    std::cout << t;
}
template <typename... Ts>
void print(const Ts&... ts) {
    put(ts...);
    std::cout << "\n";
}
using std::cin;
using std::cout;
using std::map;
using std::pair;
using std::set;
using std::string;
using std::tuple;
using std::vector;
int main() {
    int64_t N;
    read(N);
    auto A = VEC(N);
    ll U = max(A);
    ll T = (ll)(pow(1.0 * U * U / N, 1.0 / 3.0)) / 3 + 1;
    ll res = 0;
    for (const auto k : rep_impl(1, T + 1)) {
        std::unordered_map<ll, ll> d;
        d.reserve(N);
        for (const auto i : rep_impl(1, N + 1)) {
            ll a = A[i - 1];
            ll key = a - k * i;
            res += d[-(key)];
            d[key] += 1;
        }
    }
    ll mx = (2 * U) / T;
    for (const auto i : rep_impl(1, N + 1)) {
        if (not(i <= mx)) break;
        ll a = A[i - 1];
        for (const auto j : rep_impl(i + 1, N + 1)) {
            if (not(i + j <= mx)) break;
            ll b = A[j - 1];
            if ((a + b) % (i + j) != 0) continue;
            ll k = (a + b) / (i + j);
            if (T + 1 <= k) res += 1;
        }
    }
    print(res);
}
0