제출 #1293519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293519		sh1ka	9월 (APIO24_september)	C++20	55 / 100	1095 ms	7324 KiB

september

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



int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
    #define int int64_t

    vector<int> id(n), sosal(n, -1);
    for (int i = 0; i < n - 1; i++)
        id[s[0][i]] = i;
    
    for (int i = 1; i < n; i++) {
        sosal[f[i]] = max(sosal[f[i]], id[i] + 1);
    }

    const int INF = 1e12;

    vector<int> mxx(n);

    for (int i = 0; i + 1 < n; i++)
        mxx[i + 1] = sosal[s[0][i]];
    for (int i = 1; i < n; i++)
        mxx[i] = max(mxx[i], mxx[i - 1]);

    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++) {
        if (ph1[i] != penis[i])
            continue;
        if (mxx[i] > i)
            continue;
        
        for (int j = 0; j < i; j++) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    return dp[n - 1];
}

// int32_t main() {
//     using namespace std;
//     int t; cin >> t;
//     int n, m; cin >> n >> m;
//     vector<int32_t> f(n - 1);
//     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: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16