Submission #1293496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293496		sh1ka	9월 (APIO24_september)	C++20	0 / 100	2 ms	568 KiB

september

#include <bits/stdc++.h>
#include "september.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")


int32_t solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
    #define all(a) a.begin(), a.end()
    #define int int64_t
    using namespace std;

    const int INF = 1e12;

    mt19937 rnd(1488);
    vector<int> hsh(n);
    for (int i = 1; i < n; i++)
        hsh[i] = rnd();

    vector<int> ph1(n), penis(n);
    
    for (int i = 0; i + 1 < n; i++) {
        int cur_val = 0;
        for (int j = 0; j < m; j++)
            cur_val += hsh[s[j][i]];
        ph1[i + 1] = cur_val + ph1[i];    
    
        cur_val = 0;
        for (int j = 0; j < m; j++)
            cur_val += hsh[s[0][i]];
        penis[i + 1] = cur_val + penis[i];
    }

    vector<int> dp(n, -INF);
    dp[0] = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (ph1[i] - ph1[j] == penis[i] - penis[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    return dp[n - 1];
}

// int32_t main() {
//     using namespace std;
//     int n, m; cin >> n >> m;
//     vector<int32_t> f(n);
//     vector<vector<int32_t>> s(m, vector<int32_t>(n - 1));
//     for (int32_t &i : f)
//         cin >> i;
//     for (auto &i : s)
//         for (auto &j : i)
//             cin >> j;
//     cout << solve(n, m, f, s);
// }

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16