Submission #1106887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106887		Zero_OP	Sailing Race (CEOI12_race)	C++14	40 / 100	1058 ms	14524 KiB

race

#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, K;
    cin >> N >> K;
    vector<vector<int>> adj(N);
    vector<vector<bool>> e(N, vector<bool>(N));

    for(int i = 0, j; i < N; ++i){
        while(cin >> j){
            if(!j) break;
            --j;
            adj[i].push_back(j);
            e[i][j] = 1;
        }
    }

    vector<vector<vector<int>>> f(N, vector<vector<int>>(N, vector<int>(2, -1)));

    function<int(int, int, int)> dp = [&](int l, int r, int x){
        if(f[l][r][x] != -1) return f[l][r][x];
        int& ret = f[l][r][x]; ret = 0;

        for(int i = (l + 1) % N; i != r; i = (i + 1) % N){
            if(x == 0){
                if(e[l][i]){
                    maximize(ret, dp(l, i, 1) + 1);
                    maximize(ret, dp(i, r, 0) + 1);
                }
            } else{
                if(e[r][i]){
                    maximize(ret, dp(i, r, 0) + 1);
                    maximize(ret, dp(l, i, 1) + 1);
                }
            }
        }

        return ret;
    };

    pair<int, int> answer = {0, 0};
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(e[i][j]){
                maximize(answer, {dp(i, j, 1) + 1, i});
                maximize(answer, {dp(j, i, 0) + 1, i});
            }
        }
    }

    cout << answer.first << ' ' << answer.second + 1 << '\n';

    return 0;
}

• Subtask 1: 40 / 100