Submission #1311554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311554		Nipphitch	Sailing Race (CEOI12_race)	C++20	100 / 100	841 ms	6628 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int> 
const int N=505;
const int INF=1e9+7;

int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],nxt[N][2];
bool adj[N][N];

void dp(int l,int r,int x){
    if(adj[l][r]){
        dp1[l][r][x]=1;
        dp2[l][r][x]=1+dp3[r][nxt[l][x]][x^1];
    }
    else dp1[l][r][x]=dp2[l][r][x]=-INF;
    for(int k=nxt[l][x];k!=r;k=nxt[k][x]){
        dp1[l][r][x]=max(dp1[l][r][x],dp1[l][k][x]+dp1[k][r][x]);
        dp2[l][r][x]=max(dp2[l][r][x],dp1[l][k][x]+dp2[k][r][x]);
    }
    dp3[l][r][x]=max(dp2[l][r][x],dp3[l][nxt[r][x^1]][x]);
}

void solve(){
    int n;
    bool type;
    cin >> n >> type;
    for(int i=0;i<n;i++){
        int x;
        while(cin >> x && x--){
            adj[i][x]=true;
        }
        nxt[i][0]=(i+1)%n;
        nxt[i][1]=(i-1+n)%n;
    }
    for(int d=1;d<n;d++){
        for(int l=0,r=(l+d)%n;l<n;l++,r=nxt[r][0]){
            dp(l,r,0);
            dp(r,l,1);
        }
    }
    pii ans;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<2;k++){
                ans=max({{dp2[i][j][k],i},ans});
            }
        }
    }
    if(type){
        for(int l=0;l<n;l++){
            for(int r=0;r<n;r++){
                for(int x=0;x<2;x++){
                    if(dp1[l][r][x]<=0) continue;
                    int st=nxt[r][x];
                    while(st!=l && !adj[st][l]) st=nxt[st][x];
                    if(st==l) continue;
                    for(int ed=nxt[st][x];ed!=l;ed=nxt[ed][x]){
                        if(adj[r][ed]){
                            int num=max(dp3[ed][nxt[st][x]][x^1],dp3[ed][nxt[l][x^1]][x]);
                            ans=max(ans,{2+dp1[l][r][x]+num,st});
                        }
                    }
                }
            }
        }
    }
    cout << ans.first << "\n" << ans.second+1;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

• Subtask 1: 100 / 100