Submission #993459

#	Time	Username	Problem	Language	Result	Execution time	Memory
993459		Mike_Vu	Sailing Race (CEOI12_race)	C++14	5 / 100	828 ms	8696 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 = 2; 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 ((a[i][j]&&dp[k][i][2])&&maximize(dp[i][j][0], dp[k][i][2]+1)) {
                        start[i][j][0] = start[k][i][2];
                    }
                    if ((dp[i][k][0] && dp[k][j][0])&&maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0])) {
                        start[i][j][0] = start[i][k][0];
                    }
                    if ((a[i][k]&&dp[k][j][2])&&maximize(dp[i][j][1], dp[k][j][2]+1)) {
                        start[i][j][1] = i;
                    }
                    if ((dp[i][k][1]&&dp[k][j][0])&&maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0])) {
                        start[i][j][1] = start[i][k][1];
                    }
                }
                if (maximize(ans, dp[i][j][0])) s = start[i][j][0];
                if (type && maximize(ans, dp[i][j][1])) s = start[i][j][1];
//                cout << i << ' ' << j << " 01 " << dp[i][j][0] << ' ' << dp[i][j][1] << "\n";
//                cout << i << ' ' << j << " 01 " << start[i][j][0] << ' ' << start[i][j][1] << "\n";
            }
            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 ((a[i][j]&&dp[k][i][0])&&maximize(dp[i][j][2], dp[k][i][0]+1)) {
                        start[i][j][2] = start[k][i][0];
                    }
                    if ((dp[i][k][2] && dp[k][j][2])&&maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2])) {
                        start[i][j][2] = start[i][k][2];
                    }
                    if ((a[i][k]&&dp[k][j][0])&&maximize(dp[i][j][3], dp[k][j][0]+1)) {
                        start[i][j][3] = i;
                    }
                    if ((dp[i][k][3]&&dp[k][j][2])&&maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2])) {
                        start[i][j][3] = start[i][k][3];
                    }
                }
                if (maximize(ans, dp[i][j][2])) s = start[i][j][2];
                if (type && maximize(ans, dp[i][j][3])) s = start[i][j][3];
//                cout << i << ' ' << j << " 23 " << dp[i][j][2] << ' ' << dp[i][j][3] << "\n";
//                cout << i << ' ' << j << " 23 " << start[i][j][2] << ' ' << start[i][j][3] << "\n";
            }
            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 ((a[i][j]&&dp[k][i][2])&&maximize(dp[i][j][0], dp[k][i][2]+1)) {
                        start[i][j][0] = start[k][i][2];
                    }
                    if ((dp[i][k][0] && dp[k][j][0])&&maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0])) {
                        start[i][j][0] = start[i][k][0];
                    }
                    if ((a[i][k]&&dp[k][j][2])&&maximize(dp[i][j][1], dp[k][j][2]+1)) {
                        start[i][j][1] = i;
                    }
                    if ((dp[i][k][1]&&dp[k][j][0])&&maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0])) {
                        start[i][j][1] = start[i][k][1];
                    }
                }
                if (maximize(ans, dp[i][j][0])) s = start[i][j][0];
                if (type && maximize(ans, dp[i][j][1])) s = start[i][j][1];
//                cout << i << ' ' << j << " 01 " << dp[i][j][0] << ' ' << dp[i][j][1] << "\n";
//                cout << i << ' ' << j << " 01 " << start[i][j][0] << ' ' << start[i][j][1] << "\n";
            }
            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 ((a[i][j]&&dp[k][i][0])&&maximize(dp[i][j][2], dp[k][i][0]+1)) {
                        start[i][j][2] = start[k][i][0];
                    }
                    if ((dp[i][k][2] && dp[k][j][2])&&maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2])) {
                        start[i][j][2] = start[i][k][2];
                    }
                    if ((a[i][k]&&dp[k][j][0])&&maximize(dp[i][j][3], dp[k][j][0]+1)) {
                        start[i][j][3] = i;
                    }
                    if ((dp[i][k][3]&&dp[k][j][2])&&maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2])) {
                        start[i][j][3] = start[i][k][3];
                    }
                }
                if (maximize(ans, dp[i][j][2])) s = start[i][j][2];
                if (type && maximize(ans, dp[i][j][3])) s = start[i][j][3];
//                cout << i << ' ' << j << " 23 " << dp[i][j][2] << ' ' << dp[i][j][3] << "\n";
//                cout << i << ' ' << j << " 23 " << start[i][j][2] << ' ' << start[i][j][3] << "\n";
            }
        }
    }
    cout << ans << "\n" << s;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

• Subtask 1: 5 / 100