Submission #993441

#	Time	Username	Problem	Language	Result	Execution time	Memory
993441		Mike_Vu	Sailing Race (CEOI12_race)	C++14	0 / 100	788 ms	8712 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

//const ll mod = 1e9+7;

bool maximize(int &x, int y ){
    if (x < y) {x = y; return true;};
    return false;
}
bool minimize(int &x, int y){
    if (x > y) {x = y; return true;}
    return false;
}
//void add(ll &x, ll y ){
//    x += y;
//    if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
//    x -= y;
//    if (x < 0) x += mod;
//}

const int maxn = 505;
int n, type;
bool a[maxn][maxn] = {0};
int dp[maxn][maxn][4] = {0}, ans = 0, s = 0;
int start[maxn][maxn][4];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> type;
    for (int i = 1; i <= n; i++) {
        int j;
        while (cin >> j) {
            if (j == 0) break;
            a[i][j] = 1;
        }
    }
    for (int l = 1; l <= n; l++) {
        for (int i = 1; i <= n; i++) {
            int j;
            j = i-l+1;
            if (j > 0) {
                //dp1
                if (a[i][j]) {
                    dp[i][j][0] = 1;
                    start[i][j][0] = i;
                }
                for (int k = j+1; k < i; k++) {
                    if (dp[i][k][0] && dp[k][j][0]) maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0]);
                    if (a[i][k]&&dp[k][j][2]) maximize(dp[i][j][1], dp[k][j][2]+1);
                    if (dp[i][k][1]&&dp[k][j][0]) maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0]);
                }
                if (maximize(ans, dp[i][j][0])) s = i;
                if (type && maximize(ans, dp[i][j][1])) s = i;
            }
            else {
                //dp2
                j += n;
                if (a[i][j]) {
                    dp[i][j][2] = 1;
                    start[i][j][2] = i;
                }
                for (int k = j+1; k != i; k=k%n+1) {
                    if (dp[i][k][2] && dp[k][j][2]) maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2]);
                    if (a[i][k]&&dp[k][j][0]) maximize(dp[i][j][3], dp[k][j][0]+1);
                    if (dp[i][k][3]&&dp[k][j][2]) maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2]);
                }
                if (maximize(ans, dp[i][j][2])) s = i;
                if (type && maximize(ans, dp[i][j][3])) s = i;
            }
            j = i+l-1;
            if (j <= n) {
                if (a[i][j]) {
                    dp[i][j][0] = 1;
                    start[i][j][0] = i;
                }
                for (int k = i+1; k < j; k++) {
                    if (dp[i][k][0] && dp[k][j][0]) maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0]);
                    if (a[i][k]&&dp[k][j][2]) maximize(dp[i][j][1], dp[k][j][2]+1);
                    if (dp[i][k][1]&&dp[k][j][0]) maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0]);
                }
                if (maximize(ans, dp[i][j][0])) s = i;
                if (type && maximize(ans, dp[i][j][1])) s = i;
            }
            else {
                j -= n;
                if (a[i][j]) {
                    dp[i][j][2] = 1;
                    start[i][j][2] = i;
                }
                for (int k = i+1; k != j; k=k%n+1) {
                    if (dp[i][k][2] && dp[k][j][2]) maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2]);
                    if (a[i][k]&&dp[k][j][0]) maximize(dp[i][j][3], dp[k][j][0]+1);
                    if (dp[i][k][3]&&dp[k][j][2]) maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2]);
                }
                if (maximize(ans, dp[i][j][2])) s = i;
                if (type && maximize(ans, dp[i][j][3])) s = i;
            }
        }
    }
    cout << ans << "\n" << s;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

• Subtask 1: 0 / 100