結果

問題 No.3257 +|+
ユーザー dp_ijk
提出日時 2025-09-05 22:52:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,094 ms / 3,000 ms
コード長 3,203 bytes
コンパイル時間 1,670 ms
コンパイル使用メモリ 167,468 KB
実行使用メモリ 55,040 KB
最終ジャッジ日時 2025-09-05 22:53:28
合計ジャッジ時間 38,602 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 <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());
}
template <typename T, typename T2>
auto max(T a, T2 b) -> std::common_type_t<T, T2> {
    return (a < b) ? b : a;
}
using std::vector;

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;
struct LookUp {
    vector<ll> mp;
    ll L, R;
    LookUp(ll L, ll R)
        : L(L),
          R(R) {
        mp.resize(R - L);
    }
    ll& operator[](ll key) {
        assert(L <= key && key < R);
        return mp[key - L];
    }
};
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)) / 4 + 1;
    ll W = max((T + 1) * N, U + 1);
    LookUp d(-W, W + 1);
    ll res = 0;
    for (const auto k : rep_impl(1, T + 1)) {
        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;
        }
        for (const auto i : rep_impl(1, N + 1)) {
            ll a = A[i - 1];
            ll key = a - k * i;
            d[key] = 0;
        }
    }
    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