結果
問題 | No.910 素数部分列 |
ユーザー |
|
提出日時 | 2019-10-18 23:17:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 412 ms / 1,000 ms |
コード長 | 935 bytes |
コンパイル時間 | 1,745 ms |
コンパイル使用メモリ | 170,620 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 21:53:25 |
合計ジャッジ時間 | 3,710 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for( int i=0; i<n; ++i )typedef long long ll;using namespace std;int main(){int n;cin >> n;string s;cin >> s;int c[5];rep(i,5){c[i]=0;}int cnt19 = 0;int over9 = 0;int cnt991 = 0;vector<int> v;int dx1 = -1;rep(i,s.length()){c[(s[i]-'1')/2]++;if ( s[i] == '9' ){if ( 0 <= dx1 ){v.erase(v.begin()+dx1);cnt19++;auto t = find( v.begin()+dx1, v.end(), 1 );if ( t == v.end() ){dx1 = -1;} else {dx1 = t - v.begin();}} else { v.push_back(9); }}if ( s[i] == '1' ){if (dx1==-1)dx1 = v.size();v.push_back(1);}}rep(i,v.size()){if ( v[i] == 1 ){if(1<over9){over9 -= 2;cnt991++;}} else {over9++;}}cout << c[1]+c[2]+c[3] + cnt19 + cnt991 + (c[0]-cnt19-cnt991)/2 << endl;}