Submission #245167

#	Time	Username	Problem	Language	Result	Execution time	Memory
245167		Vladikus004	Rima (COCI17_rima)	C++14	14 / 140	810 ms	128536 KiB

rima

#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 500000 + 3, LEN = 3000000 + 3, P = 31;
int n;
string s[N];
vector <ull> h[N];
ull deg[LEN];
unordered_map <ull, int> dp[2];

void init(){
    deg[0] = 1;
    for (int i = 1; i < LEN; i++)
        deg[i] = deg[i - 1] * P;
}

void make_hash(int ind){
    h[ind].resize(s[ind].size());
    h[ind][0] = s[ind][0] - 'a' + 1;
    for (int i = 1; i < s[ind].size(); i++)
        h[ind][i] = h[ind][i - 1] * P + (s[ind][i] - 'a' + 1);
}

ull get_hash(int ind, int l, int r){
    if (!l) return h[ind][r];
    return h[ind][r] - h[ind][l - 1] * deg[r - l + 1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    init();
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        make_hash(i);
//        for (auto u: h[i]) cout << u << " ";
//        cout << "!\n";
    }
    int ans = 0;
    for (int i = n - 1; i >= 0; i--){
        ull hs1 = get_hash(i, 0, s[i].size() - 1);
        dp[1][hs1] = max(dp[1][hs1], dp[0][hs1]) + 1;
        ans = max(ans, dp[1][hs1]);
        if (s[i].size() != 1){
            ull hs = get_hash(i, 1, s[i].size() - 1);
            dp[0][hs] = max(dp[1][hs], dp[0][hs]) + 1;
            dp[0][hs] = max(dp[0][hs], dp[1][hs1]);
            dp[1][hs1] = max(dp[0][hs], dp[1][hs1]);
            ans = max(ans, dp[0][hs]);
        }
    }
    cout << ans;
}

Compilation message (stderr)

rima.cpp: In function 'void make_hash(int)':
rima.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < s[ind].size(); i++)
                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 14 / 140