Submission #1006383

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1006383	2024-06-23T23:08:03 Z	MilosMilutinovic	Rima (COCI17_rima)	C++14	56 / 140	483 ms	63972 KB

rima

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  for (int i = 0; i < n; i++) {
    reverse(s[i].begin(), s[i].end());
  }
  sort(s.begin(), s.end(), [&](string s, string t) {
    int cs = (int) s.size();
    int ct = (int) t.size();
    if (cs != ct) {
      return cs < ct;
    } else {
      return s < t;
    }
  });
  map<string, int> f;
  auto Modify = [&](string s, int val) {
    f[s] = max(f[s], val);
  };
  auto Query = [&](string s) {
    s.pop_back();
    return f[s];
  };
  auto Good = [&](string s, string t) {
    s.pop_back();
    t.pop_back();
    return s == t;
  };
  for (int i = 0; i < n; i++) {
    int ptr = i;
    while (ptr + 1 < n && (int) s[ptr + 1].size() == (int) s[i].size()) {
      ptr += 1;
    }
    for (int l = i; l <= ptr; l++) {
      int r = l;
      while (r + 1 <= ptr && Good(s[l], s[r + 1])) {
        r += 1;
      }
      int ft = Query(s[l]) + (r - l + 1);
      for (int p = l; p <= r; p++) {
        Modify(s[p], ft);
      }
      l = r;
    }
    i = ptr;
  }
  int res = 0;
  for (auto& p : f) {
    res = max(res, p.second);
  }
  cout << res << '\n';
  return 0;
}

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	483 ms	63972 KB	Output isn't correct
5	Correct	15 ms	9364 KB	Output is correct
6	Incorrect	5 ms	2508 KB	Output isn't correct
7	Incorrect	4 ms	2132 KB	Output isn't correct
8	Incorrect	3 ms	1940 KB	Output isn't correct
9	Incorrect	31 ms	9168 KB	Output isn't correct
10	Incorrect	3 ms	1848 KB	Output isn't correct