fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int t;
  6.  
  7. const string narek = "narek";
  8.  
  9. void solve(){
  10.     int ans = 0;
  11.     int n , m;
  12.     cin >> n >> m;
  13.     vector<string> s(n);
  14.     for(int i = 0;i < n;i ++){
  15.         cin >> s[i];
  16.     }
  17.     vector<int> dp(5 , -1e9) , ndp;
  18.     dp[0] = 0;
  19.     for(int i = 0; i < n;i ++){
  20.         ndp = dp;
  21.         for(int k = 0;k < 5;k ++){
  22.             if(dp[k] == -1e9) continue;
  23.             int nxt = k , score = 0;
  24.             for(int j = 0;j < m;j ++){
  25.                 int idx = narek.find(s[i][j]);
  26.                 if(idx == -1) continue;
  27.                 if(nxt == idx){
  28.                     nxt = (nxt + 1) % 5;
  29.                     score++;
  30.                 }
  31.                 else score--;
  32.             }
  33.             ndp[nxt] = max(ndp[nxt] , dp[k] + score);
  34.         }
  35.         dp = ndp;
  36.     }
  37.     for(int i = 0;i < 5;i ++) ans = max(ans , dp[i] - 2 * i);
  38.     cout << ans << "\n";
  39. }
  40.  
  41. signed main(){
  42.     ios_base::sync_with_stdio(0);
  43.     cin.tie(0);cout.tie(0);
  44.     cin >> t;
  45.     while(t--){
  46.         solve();
  47.     }
  48.     return 0;
  49. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fCBY3o
language:
C++ (gcc 8.3)
created:
98 days ago
visibility:
secret

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!