結果
問題 | No.910 素数部分列 |
ユーザー |
![]() |
提出日時 | 2019-10-18 22:03:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 1,000 ms |
コード長 | 1,731 bytes |
コンパイル時間 | 2,345 ms |
コンパイル使用メモリ | 178,336 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 21:27:31 |
合計ジャッジ時間 | 3,976 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using PII = pair<ll, ll>;#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)#define REP(i, n) FOR(i, 0, n)#define ALL(x) x.begin(), x.end()template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;#ifdef DEBUG_#include "../program_contest_library/memo/dump.hpp"#else#define dump(...)#endifconst ll INF = 1LL<<60;int main(void) {ll n;string s;cin >> n >> s;// 3 5 7ll ret = 0;string t = "";REP(i, n) {if(s[i]=='1' || s[i]=='9') t += s[i];else {ret++;}}dump(t);// 19n = t.size();vector<bool> del(n);stack<ll> st;REP(i, n) {if(t[i]=='1') st.push(i);else {if(st.size()>0) {del[st.top()] = true; st.pop();del[i] = true;ret++;}}}s = "";REP(i, n) if(!del[i]) s += t[i];n = s.size();dump(s);// 991while(st.size()) st.pop();del.assign(n, false);REP(i, n) {if(s[i]=='9') {st.push(i);} else {if(st.size()>=2) {del[st.top()] = true; st.pop();del[st.top()] = true; st.pop();del[i] = true;ret++;}}}t = "";REP(i, n) if(!del[i]) t += s[i];n = t.size();dump(t);ll cnt1 = 0;REP(i, n) if(t[i]=='1') cnt1++;ret += cnt1 / 2;cout << ret << endl;return 0;}