oj.uz

답안 #140275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140275 2019-08-02T12:20:13 Z egorlifar Sailing Race (CEOI12_race) C++17
100 / 100
 2205 ms 2656 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { x = (x > y ? y: x);}
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { x = (x < y ? y: x);}
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 501;

int n, t;
bitset<501> b[MAXN];
int dp[MAXN][MAXN][2];
int dp1[MAXN][MAXN][2];
int dp2[MAXN];
int curm[MAXN];


int dist(const int &i, const int &j) {
    return (j >= i ? j - i: n - i + j);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME); 
    cin >> n >> t;
    for (int i = 0; i < n; i++) {
        int a;
        while (cin >> a) {
            if (a == 0) {
                break;
            }
            b[i][a - 1] = true;
        }
    }
    for (int len = 1; len <= n - 1; len++) {
        for (int i = 0; i < n; i++) {
            int j = (i + len) % n;
            for (int t = 0; t < 2; t++) {
                int cur = (t == 0 ? i: j);
                for (int k = 0; k <= len; k++) {
                    int g = (i + k >= n ? i + k - n: i + k);
                    if (g != cur) {
                        if (b[cur][g]) {
                            chkmax(dp[len][i][t], dp[k - (cur == i ? 1: 0)][(i == cur ? (i + 1) % n: i)][1] + 1);
                            chkmax(dp[len][i][t], dp[(len - k) - (cur == j ? 1: 0)][g][0] + 1);
                        }
                    }
                }
            }
        }
    }
    if (t == 0) {
        int res = 0;
        int pos = -1;
        for (int i =  0; i < n; i++) {
            chkmax(res, dp[n - 1][i][0]);
            if (res == dp[n - 1][i][0]) {
                pos = i;
            }
            chkmax(res, dp[n - 1][i][1]);
            if (res == dp[n - 1][i][1]) {
                pos = (i + n - 1) % n;
            }
        }
        cout << res << endl;
        cout << pos + 1 << endl;
        return 0;
    }
    int res = 0;
    int pos = -1;
    for (int i =  0; i < n; i++) {
        chkmax(res, dp[n - 1][i][0]);
        if (res == dp[n - 1][i][0]) {
            pos = i;
        }
        chkmax(res, dp[n - 1][i][1]);
        if (res == dp[n - 1][i][1]) {
            pos = (i + n - 1) % n;
        }
    }
    for (int j = 0; j < n; j++) {
        memset(curm, 0, sizeof(curm));
        vector<int> g;
        g.pb(j);
        memset(dp2, 0, sizeof(dp2));
        dp2[j] = 2;
        for (int is = 2; is < n; is++) {
            int i = (j + is) % n;
            int f = (j + is - 1) % n;
            for (auto x: g) {
                if (b[x][f]) {
                    chkmax(dp2[f], dp2[x] + 1);
                }
            }
            for (int j = 0; j < n; j++) {
                if (b[f][j]) {
                    chkmax(curm[j], dp2[f]);
                }
            }
            g.pb(f);
            if (!b[i][j]) {
                continue;
            }
            int i1 = (i + 1) % n;
            for (int k = is + 1; k < n; k++) {
                int t = (j + k);
                if (t >= n) {
                    t -= n;
                } 
                int len = max(dp[n - k - 1][t][0], dp[k - is - 1][i1][1]);
                if (len + curm[t] > res && curm[t] > 2) {
                    res = len + curm[t];
                    pos = i;
                }
            }
        }
    }
    for (int j = 0; j < n; j++) {
        memset(curm, 0, sizeof(curm));
        vector<int> g;
        g.pb(j);
        memset(dp2, 0, sizeof(dp2));
        dp2[j] = 2;
        int j1 = (j + 1) % n;
        for (int is = 2; is < n; is++) {
            int i = (j - is + n) % n;
            int f = (j - is + 1 + n) % n;
            for (auto x: g) {
                if (b[x][f]) {
                    chkmax(dp2[f], dp2[x] + 1);
                }
            }
            for (int j = 0; j < n; j++) {
                if (b[f][j]) {
                    chkmax(curm[j], dp2[f]);
                }
            }
            g.pb(f);
            if (!b[i][j]) {
                continue;
            }
            for (int k = is + 1; k < n; k++) {
                int t = (j - k);
                if (t < 0) {
                    t += n;
                } 
                int len = max(dp[k - is - 1][t][0], dp[n - k - 1][j1][1]);
                if (len + curm[t] > res && curm[t] > 2) {
                    res = len + curm[t];
                    pos = i;
                }
            }
        }
    }
    cout << res << endl;
    cout << pos + 1 << endl;
    return 0; 
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 16 ms 632 KB Output is correct
9 Correct 10 ms 760 KB Output is correct
10 Correct 10 ms 760 KB Output is correct
11 Correct 13 ms 760 KB Output is correct
12 Correct 129 ms 1244 KB Output is correct
13 Correct 310 ms 1528 KB Output is correct
14 Correct 238 ms 1904 KB Output is correct
15 Correct 1673 ms 2424 KB Output is correct
16 Correct 1940 ms 2344 KB Output is correct
17 Correct 1686 ms 2656 KB Output is correct
18 Correct 414 ms 2424 KB Output is correct
19 Correct 2201 ms 2460 KB Output is correct
20 Correct 2205 ms 2508 KB Output is correct