結果
問題 | No.3015 右に寄せろ! |
ユーザー |
![]() |
提出日時 | 2025-01-25 14:06:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 1,706 bytes |
コンパイル時間 | 3,013 ms |
コンパイル使用メモリ | 279,812 KB |
実行使用メモリ | 16,984 KB |
最終ジャッジ日時 | 2025-01-25 23:07:26 |
合計ジャッジ時間 | 4,637 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge8 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define For(i, a, b) for(int i = (a); i < (b); i++) #define rep(i, n) For(i, 0, n) #define rFor(i, a, b) for(int i = (a); i >= (b); i--) #define ALL(v) (v).begin(), (v).end() #define rALL(v) (v).rbegin(), (v).rend() using lint = long long; using ld = long double; int INF = 2000000000; lint LINF = 1000000000000000000; template <class T> vector<pair<T, int>> RLE(vector<T> &v) { vector<pair<T, int>> res; for (auto x : v) { if (res.size() == 0 || res.back().first != x) { res.emplace_back(x, 1); } else { res.back().second++; } } return res; } vector<pair<char, int>> RLE(string &s) { vector<char> v; for (char &c : s) { v.emplace_back(c); } return RLE(v); } template <class T> struct PrefixSum { int n; vector<T> s; PrefixSum() {} PrefixSum(vector<T> &a) : n(a.size()), s(n + 1) { for (int i = 0; i < n; i++) { s[i + 1] = s[i] + a[i]; } } // [l, r) T prod(int l, int r) { assert(0 <= l && l <= r && r <= n); return (l == r ? T(0) : s[r] - s[l]); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; auto rle = RLE(s); int sz = rle.size(); vector<int> sum(sz, 0); rep(i, sz) { if (rle[i].first == '0') { sum[i] = rle[i].second; } } PrefixSum<int> ps(sum); lint ans = 0; rep(i, sz) { if (rle[i].first == '0') { continue; } int cnt = rle[i].second / 2; ans += lint(cnt) * lint(ps.prod(i + 1, sz)); } cout << ans << "\n"; }