結果
問題 | No.910 素数部分列 |
ユーザー |
|
提出日時 | 2020-03-14 19:25:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 1,000 ms |
コード長 | 1,797 bytes |
コンパイル時間 | 1,288 ms |
コンパイル使用メモリ | 120,012 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-11-23 21:26:11 |
合計ジャッジ時間 | 3,356 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <complex>using namespace std;#define chmax(x, y) x = max(x, y)#define chmin(x, y) x = min(x, y)typedef long long ll;typedef uint64_t ull;typedef pair<int, int> P;typedef pair<int, double> Pid;typedef pair<double, int> Pdi;typedef pair<ll, int> Pl;typedef pair<ll, ll> Pll;typedef pair<int, pair<int, int>> PP;typedef pair<P, int> PPi;constexpr double PI = 3.1415926535897932; // acos(-1)constexpr double EPS = 1e-9;constexpr int INF = 1001001001;constexpr int mod = 1e+9 + 7;// constexpr int mod = 998244353;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;string s;cin >> n >> s;int ans = 0;queue<int> One;set<int> Nine;for(int i = n - 1; i >= 0; --i){if(s[i] == '3' || s[i] == '5' || s[i] == '7') ++ans;else if(s[i] == '9') Nine.insert(i);else One.push(i);}int OneCnt = 0, NineCnt = 0;int left = 0;while(!One.empty()){int pos = One.front();One.pop();auto it = Nine.lower_bound(pos);if(it != Nine.end()){++ans;Nine.erase(*it);}else{++OneCnt;left = pos;}}for(auto it : Nine){if(it < left) ++NineCnt;}ans += min(NineCnt / 2, OneCnt);OneCnt -= min(NineCnt / 2, OneCnt);ans += OneCnt / 2;cout << ans << endl;}