結果
問題 | No.2076 Concon Substrings (ConVersion) |
ユーザー |
![]() |
提出日時 | 2024-07-23 11:02:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,213 ms / 5,000 ms |
コード長 | 1,442 bytes |
コンパイル時間 | 575 ms |
コンパイル使用メモリ | 42,364 KB |
最終ジャッジ日時 | 2025-02-23 17:53:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:32:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 32 | scanf("%d%d%d%s", &n, &a, &b, s); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 2076.cc: No.2076 Concon Substrings (ConVersion) - yukicoder*/#include<cstdio>#include<algorithm>using namespace std;/* constant */const int MAX_N = 50000;const int MAX_M = MAX_N / 3;const int MAX_K = MAX_N / 3;/* typedef *//* global variables */char s[MAX_N + 4];int ls[MAX_M], dp[2][MAX_K + 1];/* subroutines */inline void setmax(int &a, int b) { if (a < b) a = b; }/* main */int main() {int n, a, b;scanf("%d%d%d%s", &n, &a, &b, s);int k = n / 3;int m = 0;for (int i = 0; i + 2 < n;) {while (i + 2 < n && s[i] != 'c') i++;if (i + 2 >= n) break;int j = i;while (i + 2 < n &&s[i] == 'c' && s[i + 1] == 'o' && s[i + 2] == 'n') i += 3;int a = (i - j) / 3;if (a > 0) ls[m++] = a;else i++;}//for (int i = 0; i < m; i++) printf(" %d", ls[i]); putchar('\n');fill(dp[0], dp[0] + k + 1, -1);dp[0][0] = 0;int cur = 0, nxt = 1;for (int i = 0; i < k; i++) {fill(dp[nxt], dp[nxt] + k + 1, -1);for (int j = 0; j <= k; j++)if (dp[cur][j] >= 0) {for (int j1 = 0; j + j1 <= k && j1 * a <= ls[i]; j1++)setmax(dp[nxt][j + j1], dp[cur][j] + (ls[i] - j1 * a) / b);}swap(cur, nxt);}int maxc = 0;for (int j = 1; j <= k; j++) {if (dp[cur][j] >= j) setmax(maxc, j * 2);else if (dp[cur][j] >= j - 1) setmax(maxc, j * 2 - 1);}printf("%d\n", maxc);return 0;}