fork download
copy 
  1. #include <bits/stdc++.h>
  2. // #include <ext/pb_ds/assoc_container.hpp>
  3. // #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. // using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define REP(i, n) for (auto i = 0; i < (n); ++i)
  11. #define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
  12. #define FORD(i, a, b) for (auto i = (a); i >= (b); --i)
  13. #define FORE(i, a, b) for (auto i = (a); i < (b); ++i)
  14. #define MASK(x) (1LL << (x))
  15. #define BIT(x, i) (((x) >> (i)) & 1)
  16. #define ALL(x) (x).begin(), (x).end()
  17. #define left ___left 
  18. #define right ___right 
  19. #define __builtin_popcount __builtin_popcountll
  20.  
  21. #define int long long 
  22.  
  23. void you_make_it(void) {
  24.     map <char, int> dd;
  25.     dd['n'] = 0;
  26.     dd['a'] = 1;
  27.     dd['r'] = 2;
  28.     dd['e'] = 3; 
  29.     dd['k'] = 4;
  30.     int n, m; cin >> n >> m;
  31.     vector <vector <char>> a(n, vector <char> (m));
  32.     for (int i = 0; i < n; ++i) {
  33.         for (int j = 0; j < m; ++j) cin >> a[i][j];
  34.     }
  35.     vector <vector <int>> dp(n + 1, vector <int> (5, -1e9));
  36.     dp[0][0] = 0;
  37.     int ans = 0;
  38.     for (int i = 0; i < n; ++i) {
  39.         for (int k = 0; k < 5; ++k) {
  40.             int r = k, res = 0;
  41.             for (int j = 0; j < m; ++j) {
  42.                 if(not dd.count(a[i][j])) continue;
  43.                 if(dd[a[i][j]] == r) res++, r = (r + 1) % 5;
  44.                 else res--;
  45.             }
  46.             dp[i + 1][r] = max(dp[i + 1][r], dp[i][k] + res);
  47.             dp[i + 1][k] = max(dp[i + 1][k], dp[i][k]); 
  48.         }
  49.     }
  50.     for (int i = 0; i < 5; ++i) ans = max(ans, dp[n][i] - 2 * i);
  51.     cout << ans;
  52. }
  53.  
  54. signed main() {
  55.  
  56. #ifdef LOCAL
  57.     freopen("TASK.inp", "r", stdin);
  58.     freopen("TASK.out", "w", stdout);
  59. #endif // LOCAL
  60.     auto start_time = chrono::high_resolution_clock::now();
  61.  
  62.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  63.  
  64.     int test = 1;
  65.     cin >> test;
  66.  
  67.     for (int i = 0; i < test; ++i) {
  68.         you_make_it();
  69.         cout << '\n';
  70.     }
  71.     auto end_time = chrono::high_resolution_clock::now();
  72.  
  73.     cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
  74.     return (0 ^ 0);
  75. }
  76.  
  77. // Dream it. Wish it. Do it.
  78.  
Success #stdin #stdout #stderr 0s 5280KB
comments (?)
stdin
copy 
1
5 8
nrrarekn
nrnekanx
uuuuuuux
pppppppx
nkarekzn
stdout
copy 
5
stderr
copy 
Execution time : 0[ms]
https://ideone.com/3PVrlr
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!