#1020272 (C++23) No.2938 Sigma Sigma Distance Distance Problem

提出ソース
結果

問題	No.2938 Sigma Sigma Distance Distance Problem
ユーザー	ルク
提出日時	2024-10-18 21:22:42
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	20,959 bytes
コンパイル時間	8,743 ms
コンパイル使用メモリ	353,968 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-18 21:39:18
合計ジャッジ時間	10,351 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	1 ms 6,820 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	2 ms 6,816 KB
testcase_20	AC	2 ms 6,816 KB
testcase_21	AC	2 ms 6,820 KB
04_evil_01.txt	WA	-
04_evil_02.txt	WA	-
04_evil_03.txt	WA	-
04_evil_04.txt	WA	-
04_evil_05.txt	WA	-
04_evil_06.txt	WA	-
04_evil_07.txt	WA	-
04_evil_08.txt	WA	-
04_evil_09.txt	WA	-
04_evil_10.txt	WA	-
04_evil_11.txt	WA	-
04_evil_12.txt	WA	-
04_evil_13.txt	WA	-
04_evil_14.txt	WA	-
04_evil_15.txt	WA	-
04_evil_16.txt	WA	-
04_evil_17.txt	WA	-
04_evil_18.txt	WA	-
04_evil_19.txt	WA	-
04_evil_20.txt	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#if __has_include("./cpp-dump/cpp-dump.hpp")
#include "./cpp-dump/cpp-dump.hpp"
#endif
#include <chrono>
#include <unistd.h>
#include <random>
using namespace std;
using namespace chrono;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using mint = modint998244353;
using MINT = modint1000000007;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr double pi = 3.141592653589793;
constexpr ll smallMOD = 998244353;
constexpr ll bigMOD = 1000000007;
constexpr ll INF = 1LL << 60;
constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

// init.
struct Init
{
    Init()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(15);
    }
} init;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
    os << "[";
    rep(i, vec.size())
    {
        os << vec[i];
        if (i != vec.size() - 1)
            os << ", ";
    }
    os << "]";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &vec)
{
    os << "[";
    rep(i, vec.size())
    {
        os << vec[i];
        if (i != vec.size() - 1)
            os << ", ";
    }
    os << "]";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var)
{
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
    os << "{";
    for (auto itr = st.begin(); itr != st.end(); ++itr)
    {
        os << *itr;
        if (next(itr) != st.end())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st)
{
    os << "{";
    for (auto itr = st.begin(); itr != st.end(); ++itr)
    {
        os << *itr;
        if (next(itr) != st.end())
            os << ", ";
    }
    os << "}";
    return os;
}
template <class T>
bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, T b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}

// functions.
// Math.
void calc_divisors(ll N, vector<ll> &res)
{
    for (ll i = 1; i * i <= N; ++i)
    {
        if (N % i != 0)
            continue;
        res.push_back(i);
        if (N / i != i)
            res.push_back(N / i);
    }
    sort(res.begin(), res.end());
}
void recursive_comb(vector<ll> indexes, ll s, ll rest, function<void(vector<ll>)> f)
{
    if (rest == 0)
    {
        f(indexes);
    }
    else
    {
        if (s < 0)
            return;
        recursive_comb(indexes, s - 1, rest, f);
        indexes[rest - 1] = s;
        recursive_comb(indexes, s - 1, rest - 1, f);
    }
}
void foreach_comb(ll n, ll k, function<void(vector<ll>)> f)
{
    vector<ll> indexes(k);
    recursive_comb(indexes, n - 1, k, f);
}
void prime_factorize(ll N, vector<pair<ll, ll>> &res)
{
    for (ll p = 2; p * p <= N; ++p)
    {
        if (N % p != 0)
            continue;
        ll e = 0;
        while (N % p == 0)
        {
            ++e;
            N /= p;
        }
        res.emplace_back(p, e);
    }
    if (N != 1)
    {
        res.emplace_back(N, 1);
    }
}
ll repeated_squaring(ll x, ll y, ll z = smallMOD)
{
    ll ans = 1;
    bitset<64> bits(y);
    string bit_str = bits.to_string();
    reverse(all(bit_str));
    rep(i, 64)
    {
        if (bit_str[i] == '1')
            ans = ans * x % z;
        x = x * x % z;
    }
    return ans;
}

// String.
bool isPalindrome(string str)
{
    ll low = 0;
    ll high = str.length() - 1;
    while (low < high)
    {
        if (str[low] != str[high])
        {
            return false;
        }
        low++;
        high--;
    }
    return true;
}
map<char, ll> alphabetHash = {
    {'a', 2},
    {'b', 3},
    {'c', 5},
    {'d', 7},
    {'e', 11},
    {'f', 13},
    {'g', 17},
    {'h', 19},
    {'i', 23},
    {'j', 29},
    {'k', 31},
    {'l', 37},
    {'m', 41},
    {'n', 43},
    {'o', 47},
    {'p', 53},
    {'q', 59},
    {'r', 61},
    {'s', 67},
    {'t', 71},
    {'u', 73},
    {'v', 79},
    {'w', 83},
    {'x', 89},
    {'y', 97},
    {'z', 101},
};
void split(vector<string> &elems, const string &s, char delim)
{
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim))
    {
        elems.push_back(item);
    }
}
ll string_mod(string s, ll mod)
{
    ll rest = 0;
    for (char c : s)
    {
        ll v = c - '0';
        rest = (rest * 10 + v) % mod;
    }
    return rest;
}

// algorithms.
pair<pair<ll, ll>, pair<ll, ll>> maxAndMinSubarraySum(const vector<ll> &nums)
{
    ll maxSum = nums[0];
    ll minSum = nums[0];
    ll maxStart = 0;
    ll maxEnd = 0;
    ll minStart = 0;
    ll minEnd = 0;
    ll currentMaxSum = nums[0];
    ll currentMinSum = nums[0];
    ll tempMaxStart = 0;
    ll tempMinStart = 0;

    for (ll i = 1; i < nums.size(); ++i)
    {
        if (currentMaxSum < 0)
        {
            currentMaxSum = nums[i];
            tempMaxStart = i;
        }
        else
        {
            currentMaxSum += nums[i];
        }
        if (currentMaxSum > maxSum)
        {
            maxSum = currentMaxSum;
            maxStart = tempMaxStart;
            maxEnd = i;
        }
        if (currentMinSum > 0)
        {
            currentMinSum = nums[i];
            tempMinStart = i;
        }
        else
        {
            currentMinSum += nums[i];
        }
        if (currentMinSum < minSum)
        {
            minSum = currentMinSum;
            minStart = tempMinStart;
            minEnd = i;
        }
    }
    return make_pair(make_pair(maxStart, maxEnd), make_pair(minStart, minEnd));
}

// array.
vector<string> RotateVectorString(vector<string> A, bool clockwise = false, char leading = 0)
{
    ll N = A.size();
    if (N == 0)
        return A;
    ll M = 0;
    rep(i, N)
    {
        M = max(M, (ll)A[i].size());
    }
    vector<string> B(M, string(N, leading));
    rep(i, N)
    {
        rep(j, A[i].size())
        {
            if (clockwise)
            {
                B[j][N - 1 - i] = A[i][j];
            }
            else
            {
                B[M - 1 - j][i] = A[i][j];
            }
        }
    }
    return B;
}

// struct.
// Data structure.
struct CumulativeSum2D
{
    vector<vector<ll>> data;
    CumulativeSum2D(vector<vector<ll>> &source)
    {
        ll h = source.size();
        ll w = 0;
        if (h != 0)
            w = source[0].size();
        data.resize(h + 1, vector<ll>(w + 1, 0));
        rep(i, h) rep(j, w) data[i + 1][j + 1] = source[i][j];
        rep(i, h + 1) rep(j, w) data[i][j + 1] += data[i][j];
        rep(i, h) rep(j, w + 1) data[i + 1][j] += data[i][j];
    }
    ll query(ll x1, ll y1, ll x2, ll y2)
    {
        return data[x2][y2] - data[x1][y2] - data[x2][y1] + data[x1][y1];
    }
};
struct UnionFind
{
    vector<ll> parent;
    vector<ll> parentSize;
    UnionFind(ll N)
    {
        rep(i, N + 1)
        {
            parent.push_back(i);
            parentSize.push_back(1);
        }
    }
    ll root(ll x)
    {
        if (parent[x] == x)
            return x;
        parent[x] = root(parent[x]);
        return parent[x];
    }
    void unite(ll x, ll y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return;
        if (parentSize[x] <= parentSize[y])
        {
            parent[x] = y;
            parentSize[y] += parentSize[x];
        }
        else
        {
            parent[y] = x;
            parentSize[x] += parentSize[y];
        }
    }
    bool same(ll x, ll y)
    {
        return root(x) == root(y);
    }
    ll size(ll x)
    {
        return parentSize[root(x)];
    }
};

// Math.
struct NCR
{
    ll max = 510000, mod = 0;
    vector<ll> fact, inv, inv_fact;
    NCR(ll mod = 998244353)
    {
        this->mod = mod;
        fact.resize(max);
        inv.resize(max);
        inv_fact.resize(max);
        fact[0] = 1;
        fact[1] = 1;
        inv[0] = 1;
        inv[1] = 1;
        inv_fact[0] = 1;
        inv_fact[1] = 1;
        for (ll i = 2; i < max; i++)
        {
            fact[i] = fact[i - 1] * i % mod;
            inv[i] = mod - inv[mod % i] * (mod / i) % mod;
            inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;
        }
    }
    ll nCr(ll n, ll r)
    {
        ll x = fact[n];
        ll y = inv_fact[n - r];
        ll z = inv_fact[r];
        if (n < r)
            return 0;
        if (n < 0 || r < 0)
            return 0;
        return x * ((y * z) % mod) % mod;
    }
};

// Graph.
struct Edge
{
    ll to;
    ll cost;
    Edge(ll to, ll cost) : to(to), cost(cost) {}
    bool operator>(const Edge &e) const
    {
        return cost > e.cost;
    }
};
struct Graph
{
    vector<vector<Edge>> g;
    Graph(ll n)
    {
        g.resize(n);
    }
    ll size()
    {
        return g.size();
    }
    void add_edge(ll from, ll to, ll cost = 1)
    {
        g[from].push_back(Edge(to, cost));
        g[to].push_back(Edge(from, cost));
    }
    void add_directed_edge(ll from, ll to, ll cost = 1)
    {
        g[from].push_back(Edge(to, cost));
    }
    pair<ll, vector<ll>> tree_diameter()
    {
        function<pair<ll, ll>(ll, ll)> dfs = [&](ll v, ll p) -> pair<ll, ll>
        {
            pair<ll, ll> res = {0, v};
            for (auto e : g[v])
            {
                if (e.to == p)
                    continue;
                auto [d, u] = dfs(e.to, v);
                d += e.cost;
                if (res.first < d)
                {
                    res.first = d;
                    res.second = u;
                }
            }
            return res;
        };
        auto [d, u] = dfs(0, -1);
        auto [d2, v] = dfs(u, -1);
        vector<ll> path;
        function<void(ll, ll, ll)> get_path = [&](ll v, ll p, ll u)
        {
            if (v == u)
            {
                path.push_back(v);
                return;
            }
            for (auto e : g[v])
            {
                if (e.to == p)
                    continue;
                get_path(e.to, v, u);
                if (!path.empty())
                {
                    path.push_back(v);
                    return;
                }
            }
        };
        get_path(u, -1, v);
        return {d2, path};
    }
    vector<Edge> &operator[](ll v)
    {
        return g[v];
    }
};
struct Dijkstra
{
    vector<ll> dist;
    vector<ll> prev;

    // dijkstraを構築
    Dijkstra(Graph &g, ll s)
    {
        ll n = g.size();
        dist.assign(n, INF);
        prev.assign(n, -1);
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
        dist[s] = 0;
        pq.emplace(dist[s], s);
        while (!pq.empty())
        {
            auto p = pq.top();
            pq.pop();
            ll v = p.second;
            if (dist[v] < p.first)
                continue;
            for (auto &e : g[v])
            {
                if (dist[e.to] > dist[v] + e.cost)
                {
                    dist[e.to] = dist[v] + e.cost;
                    prev[e.to] = v;
                    pq.emplace(dist[e.to], e.to);
                }
            }
        }
    }

    // 最小コストを求める
    ll get_cost(ll to)
    {
        return dist[to];
    }

    // 最短経路を求める
    vector<ll> get_path(ll to)
    {
        vector<ll> get_path;
        for (ll i = to; i != -1; i = prev[i])
        {
            get_path.push_back(i);
        }
        reverse(get_path.begin(), get_path.end());
        return get_path;
    }

    // 到達可能か調べる
    bool cango(ll to)
    {
        return (dist[to] != INF);
    }
};
struct Bellman_ford
{
    vector<ll> dist;
    vector<ll> prev;
    ll start;
    ll size;
    bool cl = false;

    // bellman_fordを構築
    Bellman_ford(Graph &g, ll s)
    {
        start = s;
        ll n = g.size();
        size = n;
        dist.assign(n, INF);
        prev.assign(n, -1);
        vector<ll> counts(n);
        vector<bool> inqueue(n);

        queue<ll> q;
        dist[s] = 0;
        q.push(s);
        inqueue[s] = true;

        while (!q.empty())
        {
            ll from = q.front();
            q.pop();
            inqueue[from] = false;

            for (auto &e : g[from])
            {
                ll d = dist[from] + e.cost;
                if (d < dist[e.to])
                {
                    dist[e.to] = d;
                    prev[e.to] = from;
                    if (!inqueue[e.to])
                    {
                        q.push(e.to);
                        inqueue[e.to] = true;
                        ++counts[e.to];

                        if (n < counts[e.to])
                            cl = true;
                    }
                }
            }
        }
    }

    // 最小コストを求める
    ll get_cost(ll to)
    {
        return dist[to];
    }

    // 最短経路を求める
    vector<ll> get_path(ll to)
    {
        vector<ll> path;
        if (dist[to] != INF)
        {
            for (ll i = to; i != -1; i = prev[i])
            {
                path.push_back(i);
            }
            reverse(path.begin(), path.end());
        }
        return path;
    }

    // 到達可能か調べる
    bool cango(ll to)
    {
        return (dist[to] != INF);
    }

    // 閉路の有無を調べる
    bool closed()
    {
        return cl;
    }
};
struct Warshall_floyd
{
    vector<vector<ll>> d;
    vector<vector<ll>> next;
    bool cl = false;

    // warshall_floydを構築
    Warshall_floyd(Graph &g)
    {
        ll n = g.size();
        d.resize(n, vector<ll>(n, INF));
        next.resize(n, vector<ll>(n, -1));

        for (ll i = 0; i < n; i++)
        {
            d[i][i] = 0;
        }

        for (ll i = 0; i < n; i++)
        {
            for (auto e : g[i])
            {
                d[i][e.to] = e.cost;
                next[i][e.to] = e.to;
            }
        }

        for (ll k = 0; k < n; ++k)
        {
            for (ll i = 0; i < n; ++i)
            {
                for (ll j = 0; j < n; ++j)
                {
                    if (d[i][j] > d[i][k] + d[k][j])
                    {
                        d[i][j] = d[i][k] + d[k][j];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }

        for (ll i = 0; i < n; i++)
        {
            if (d[i][i] < 0)
            {
                cl = true;
                break;
            }
        }
    }

    // 最小コストを求める
    ll get_cost(ll from, ll to)
    {
        return d[from][to];
    }

    // 最短経路を求める
    vector<ll> get_path(ll from, ll to)
    {
        if (d[from][to] == INF)
            return {};
        vector<ll> path;
        for (ll at = from; at != to; at = next[at][to])
        {
            if (at == -1)
                return {};
            path.push_back(at);
        }
        path.push_back(to);
        return path;
    }

    // 到達可能か調べる
    bool cango(ll from, ll to)
    {
        return d[from][to] != INF;
    }

    // 負の閉路の有無を調べる
    bool closed()
    {
        return cl;
    }
};

// String.
struct Suffix_array
{
    vector<ll> sa, rank, tmp;
    ll n;
    string base;

    // suffix_arrayを構築
    Suffix_array(const string s)
    {
        n = s.size();
        base = s;
        sa.resize(n);
        rank.resize(n);
        tmp.resize(n);

        for (ll i = 0; i < n; i++)
        {
            sa[i] = i;
            rank[i] = s[i];
        }

        for (ll k = 1; k < n; k *= 2)
        {
            auto compare_sa = [&](ll i, ll j)
            {
                if (rank[i] != rank[j])
                    return rank[i] < rank[j];
                ll ri = (i + k < n) ? rank[i + k] : -1;
                ll rj = (j + k < n) ? rank[j + k] : -1;
                return ri < rj;
            };
            sort(sa.begin(), sa.end(), compare_sa);

            tmp[sa[0]] = 0;
            for (ll i = 1; i < n; i++)
            {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
            }
            rank = tmp;
        }
    }

    // 部分文字列の個数を求める
    ll get_counts(string t)
    {
        string u = t + "彁";
        ll num1, num2;
        {
            ll m = t.size();
            ll ng = -1, ok = n;
            while (ok - ng > 1)
            {
                ll mid = (ng + ok) / 2;
                ll l = sa[mid];
                if (base.substr(l, m) >= t)
                {
                    ok = mid;
                }
                else
                {
                    ng = mid;
                }
            }
            num1 = ok;
        }
        {
            ll m = u.size();
            ll ng = -1, ok = n;
            while (ok - ng > 1)
            {
                ll mid = (ng + ok) / 2;
                ll l = sa[mid];
                if (base.substr(l, m) >= u)
                {
                    ok = mid;
                }
                else
                {
                    ng = mid;
                }
            }
            num2 = ok;
        }
        return num2 - num1;
    }

    // make lcp array
    vector<ll> make_lcp()
    {
        vector<ll> lcp(n);
        for (ll i = 0; i < n; i++)
        {
            rank[sa[i]] = i;
        }
        ll h = 0;
        lcp[0] = 0;
        for (ll i = 0; i < n; i++)
        {
            if (rank[i] == n - 1)
            {
                h = 0;
                continue;
            }
            ll j = sa[rank[i] + 1];
            while (i + h < n && j + h < n && base[i + h] == base[j + h])
            {
                h++;
            }
            lcp[rank[i]] = h;
            if (h > 0)
            {
                h--;
            }
        }
        return lcp;
    }
};

// others.
class Timer
{
public:
    Timer(ll ms) : duration(ms), start_time(steady_clock::now()) {}
    bool isTimeOver() const
    {
        auto current_time = steady_clock::now();
        auto elapsed = duration_cast<milliseconds>(current_time - start_time).count();
        return elapsed >= duration;
    }

private:
    ll duration;
    steady_clock::time_point start_time;
};

class FunctionalGraph
{
private:
    const ll V;
    ll loop_id;
    vector<ll> nx;
    void make_loop(const ll st, ll nw, vector<ll> &vec)
    {
        while (nx[nw] != st)
        {
            vec.push_back(nx[nw]);
            visit[nx[nw]] = loop_id;
            nw = nx[nw];
        }
    }
    ll dfs(ll u, vector<ll> &vec)
    {
        visit[u] = -loop_id;
        ll v = nx[u];
        if (visit[v] == -loop_id)
        {
            vec.push_back(u), vec.push_back(v);
            visit[u] = visit[v] = loop_id;
            make_loop(u, v, vec);
            loop_id++;
            return 0;
        }
        else if (visit[v] == 0)
        {
            const ll res = dfs(v, vec);
            if (res == 0)
                return 0;
            else
                return visit[u] = res;
        }
        return visit[u] = (visit[v] > 0 ? -visit[v] : visit[v]);
    }
    void make_graph()
    {
        graph.resize(V);
        for (ll i = 0; i < V; i++)
        {
            if (visit[i] < 0)
                graph[nx[i]].push_back(i);
        }
    }

public:
    vector<ll> visit;
    vector<vector<ll>> loop, graph;
    FunctionalGraph(const ll node_size)
        : V(node_size), loop_id(1), nx(V, 0), visit(V, 0) {}
    void add_edge(ll u, ll v)
    {
        nx[u] = v;
        if (u == nx[u])
            visit[u] = loop_id++, loop.push_back({u});
    }
    void solve()
    {
        for (ll i = 0; i < V; i++)
        {
            if (visit[i] == 0)
            {
                vector<ll> vec;
                dfs(i, vec);
                if (!vec.empty())
                    loop.push_back(move(vec));
            }
        }
    }
};

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    if (n > 100)
    {
        return 0;
    }
    ll ans = 0;
    rep(i, n)
    {
        rep(j, n)
        {
            ans += abs(i - j) * abs(a[i] - a[j]);
        }
    }
    cout << ans << endl;
    return 0;
}
yukicoder

結果

テストケース

ソースコード
