結果
問題 | No.910 素数部分列 |
ユーザー |
![]() |
提出日時 | 2019-10-18 22:16:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 1,000 ms |
コード長 | 1,886 bytes |
コンパイル時間 | 1,170 ms |
コンパイル使用メモリ | 114,664 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-25 21:43:57 |
合計ジャッジ時間 | 2,733 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <iostream>#include <algorithm>#include <bitset>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <cstring>#include <utility>#include <vector>#include <complex>#include <valarray>#include <fstream>#include <cassert>#include <cmath>#include <functional>#include <iomanip>#include <numeric>#include <climits>#include <random>#define _overload(a, b, c, d, ...) d#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))#define all(X) (X).begin(),(X).end()#define len(X) ((int)(X).size())#define mod(n, m) (((n)%(m)+(m))%m)#define fi first#define sc secondusing namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> Pii;typedef pair<ll,ll> Pll;const int INFINT = 1 << 30; // 1.07x10^ 9const ll INFLL = 1LL << 60; // 1.15x10^18const double EPS = 1e-10;const int MOD = 1000000007;const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};int N;string S;int main() {cin >> N;cin >> S;int ans = 0;string extracted;for (int i = 0; i < N; ++i) {if (S[i] == '1' || S[i] == '9') {extracted += S[i];} else {++ans;}}int one = 0;int nine = 0;for (int i = 0; i < len(extracted); ++i) {if (extracted[i] == '1') {++one;} else {if (one > 0) {++ans; --one;} else {++nine;}}}if ((nine/2) <= one) {ans += nine/2;one -= nine/2;ans += (one/2);} else {ans += one;}cout << ans << endl;return 0;}