結果

問題 No.3772 Discrete Addition
コンテスト
ユーザー apricity
提出日時 2026-07-04 16:34:25
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,602 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,331 ms
コンパイル使用メモリ 182,908 KB
実行使用メモリ 9,924 KB
最終ジャッジ日時 2026-10-16 20:52:26
合計ジャッジ時間 3,247 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;

int main() {
    ll n, m, q; cin >> n >> m >> q;
    vector<ll> a(n);
    vector<pair<ll,int>> x(q);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++){
        cin >> x[i].first;
        x[i].second = i;
    }
    sort(x.begin(), x.end());
    vector<ll> s(n);
    ll c = 0;
    for (int i = 0; i < n-1; i++){
        s[i+1] = s[i] + a[i];
        c += a[i] * i * 2;
    }
    c -= s[n-1] * (n-1);

    auto f = [&] (int k, int i) {
        return -2*i*(x[k].first+s[n-1]) + 2*n*s[i] + m*i*(n-i);
    };

    auto solve = [&] (this auto self, vector<int> row) -> vector<int> {
        int l = row.size();
        if (l == 0) return {};
        vector<int> row2;
        for (int i = 1; i < l; i+= 2) row2.emplace_back(row[i]);
        vector<int> ans2 = self(row2);
        vector<int> ans(l);
        for (size_t i = 0; i < ans2.size(); i++) ans[2*i+1] = ans2[i];
        int j = 0;
        for (int i = 0; i < l; i += 2) {
            ans[i] = j;
            int end = (i == l-1 ? n-1 : ans[i+1]);
            while (j != end) {
                j++;
                if (f(row[i], ans[i]) > f(row[i], j)) ans[i] = j;
            }
        }
        return ans;
    };

    vector<int> p(q); iota(p.begin(), p.end(), 0);
    vector<int> pos = solve(p);
    vector<ll> ans(q);
    for (int i = 0; i < q; i++) {
        auto [xi, idx] = x[i];
        ans[idx] = f(i, pos[i]) + xi*(n-1) + c;
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
0