結果
問題 | No.910 素数部分列 |
ユーザー |
![]() |
提出日時 | 2019-10-18 23:20:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 1,000 ms |
コード長 | 1,529 bytes |
コンパイル時間 | 842 ms |
コンパイル使用メモリ | 79,044 KB |
最終ジャッジ日時 | 2025-01-07 23:52:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <iostream>#include <vector>#include <deque>using namespace std;int main(){int N;string S,T = "";cin >> N >> S;int ans = 0;for(int i=0;i<N;i++){if(S[i]!='1' && S[i]!='9') ans++;else T += S[i];}int ans2 = 0;int n = T.size();vector<int> used(n,0);deque<int> nine;for(int i=0;i<n;i++){if(T[i]=='9') nine.push_back(i);else{if(nine.size()>=2){used[i] = 1;for(int j=0;j<2;j++){used[nine.front()] = 1;nine.pop_front();}ans2++;}}}int ni = 0,one = 0;for(int i=n-1;i>=0;i--){if(used[i]) continue;if(T[i]=='9') ni++;else{if(ni){ni--;ans2++;}else one++;}}ans2 += one/2;nine.clear();for(int i=0;i<n;i++) used[i] = 0;int ans3 = 0;for(int i=n-1;i>=0;i--){if(T[i]=='9') nine.push_back(i);else if(!nine.empty()){used[nine.front()] = 1;nine.pop_front();used[i] = 1;ans3++;}}one = 0,ni = 0;for(int i=0;i<n;i++){if(used[i]) continue;if(T[i]=='9') ni++;else{if(ni>=2){ni -= 2;ans3++;}else one++;}}ans3 += one/2;cout << ans+max(ans2,ans3) << endl;}