結果
問題 | No.910 素数部分列 |
ユーザー |
|
提出日時 | 2019-11-28 19:41:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 1,000 ms |
コード長 | 786 bytes |
コンパイル時間 | 2,370 ms |
コンパイル使用メモリ | 197,468 KB |
最終ジャッジ日時 | 2025-01-08 05:40:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);int N;cin >> N;string S;cin >> S;vector<int> cnt(10);for (char c : S) ++cnt[c - '0'];int ans = 0;for (int p : { 3, 5, 7 }) ans += cnt[p];vector<int> onepos;for (int i = 0; i < N; ++i) {if (S[i] == '1') {onepos.push_back(i);}}for (int i = N - 1; ~i; --i) {if (S[i] != '9') continue;while (onepos.size() && i < onepos.back()) {onepos.pop_back();}if (onepos.size()) {assert(onepos.back() < i);onepos.pop_back();--cnt[9];--cnt[1];++ans;}}ans += min(cnt[9] / 2, cnt[1]);cnt[1] -= min(cnt[9] / 2, cnt[1]);ans += cnt[1] / 2;cout << ans << endl;return 0;}