結果
問題 | No.910 素数部分列 |
ユーザー |
|
提出日時 | 2023-02-24 09:38:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 1,000 ms |
コード長 | 1,246 bytes |
コンパイル時間 | 779 ms |
コンパイル使用メモリ | 79,512 KB |
最終ジャッジ日時 | 2025-02-10 20:11:30 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include<iostream>#include<vector>#include<queue>using namespace std;using ll=long long;#define rep(i,n) for(int i=0;i<n;i++)#define rrep(i,n) for(int i=(n)-1;i>=0;i--)#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;string s;cin>>n>>s;int ans=0;vector<bool>flag(n);queue<int>q;int cnt1=0;rep(i,n){if(s[i]=='1'){q.push(i);cnt1++;}else if(s[i]=='9'){if(q.size()){int x=q.front();q.pop();flag[x]=flag[i]=true;ans++;cnt1--;}}else{flag[i]=true;ans++;}}int c=0;rep(i,n){if(flag[i])continue;if(s[i]=='1'){if(c>=2){c-=2;ans++;cnt1--;}}else{c++;}}ans+=cnt1/2;cout<<ans<<"\n";}