結果
問題 | No.2488 Mod Sum Maximization |
ユーザー |
|
提出日時 | 2023-09-29 11:42:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 422 ms / 2,000 ms |
コード長 | 1,021 bytes |
コンパイル時間 | 1,660 ms |
コンパイル使用メモリ | 200,224 KB |
最終ジャッジ日時 | 2025-02-17 02:54:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/segtree.hpp> #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i) using namespace std; using ll = long long; void chmin(ll& a, ll b) { if (a > b) a = b; } ll op(ll a, ll b) { return min(a, b); } ll e() { return 1e18; } int main() { int N; cin >> N; vector<int> A(N); rep (i, N) cin >> A[i]; const int M = A[N - 1]; vector<int> idx(M + 1, N); rep (i, N) idx[A[i]] = i; rrep (i, M + 1) { if (idx[i] == N) idx[i] = idx[i + 1]; } atcoder::segtree<ll, op, e> seg(N); seg.set(N - 1, 0); rrep (i, N - 1) { int j = i + 1; ll mn = 1e18; while (j != N) { int p = A[j] / A[i]; int k = (p + 1) * A[i] > M ? N : idx[(p + 1) * A[i]]; chmin(mn, seg.prod(j, k) + p * A[i]); j = k; } seg.set(i, mn); } ll sm = 0; rep (i, N) sm += A[i]; cout << sm - seg.get(0) << endl; }