結果
問題 | No.910 素数部分列 |
ユーザー |
![]() |
提出日時 | 2019-12-24 20:36:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 1,000 ms |
コード長 | 1,124 bytes |
コンパイル時間 | 1,938 ms |
コンパイル使用メモリ | 178,048 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-22 11:32:12 |
合計ジャッジ時間 | 3,606 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;typedef long long ll;#define EPS (1e-7)#define INF (1e9)#define rep(i, n) for(int i = 0; i < (int)(n); i++)#define all(x) x.begin(),x.end()const double PI = acos(-1);const ll MOD = 1000000007;template<class T>inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}template<class T>inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}///////////////////////////////////////////////////////////////int main() {ios::sync_with_stdio(false); cin.tie(nullptr);int N; cin >> N;string S; cin >> S;int count = 0;string T = "";rep(i,N) {if (S[i] == '1' || S[i] == '9') T += S[i];else count++;}int M = T.size();int cnt1 = 0;int cnt9 = 0;for (int i = M-1; i >= 0; i--) {if (T[i] == '9') cnt9++;else if (cnt9 > 0) {cnt9--;count++;} else {cnt1++;}}while (cnt9 > 1 && cnt1 > 0) {count++;cnt9 -= 2;cnt1--;}count += (cnt1/2);cout << count << endl;}