Submission #1041903

#TimeUsernameProblemLanguageResultExecution timeMemory
1041903jhinezeal123Sailing Race (CEOI12_race)C++17
0 / 100
618 ms9416 KiB
#include <bits/stdc++.h> #define int long long #define ii pair<int, int> #define iii pair<int,ii> #define vii vector<ii> #define fi first #define se second #define endl '\n' #define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;} #define all(T) T.begin(),T.end() using namespace std; const double eps = 0.0000001; const int mod = 1e9+7; const int N = 505; const int MATRIX_SIZE = 64; const int BLOCK=500; int n,dp1[N][N][2],dp2[N][N][2],k; bool ke[N][N]; vector <int> G[N]; int id(int x){ if (x>n) x-=n; else if (x<1) x+=n; return x; } void tim_dp1(){ for (int i=1,mid1,to1,mid2,to2;i<=n;++i){ for (int j=1;j<n;++j){ to1=id(i+j); to2=id(i-j); for (int z=1;z<j;++z){ mid1=id(i+z); mid2=id(i-z); if (ke[mid1][to1]&&dp1[i][mid1][0]) dp1[i][to1][0]=max(dp1[i][to1][0],dp1[i][mid1][0]+1); if (ke[mid2][to2]&&dp1[i][mid2][1]) dp1[i][to2][1]=max(dp1[i][to2][1],dp1[i][mid2][1]+1); } } } } void tim_dp2(){ for (int kc=1;kc<n;++kc){ for (int i=1,j1,j2,mid1,mid2;i<=n;++i){ j1=id(i+kc); j2=id(i-kc); dp2[i][j1][0]=max(dp1[i][j1][0],dp2[i][id(i+kc-1)][0]); dp2[i][j2][1]=max(dp1[i][j2][1],dp2[i][id(i-kc+1)][1]); for (int z=1;z<kc;++z){ mid1=id(i+z); mid2=id(i-z); if (dp1[i][mid1][0]) dp2[i][j1][0]=max(dp2[i][j1][0],dp1[i][mid1][0]+dp2[mid1][j1][0]); if (dp1[i][mid2][1]) dp2[i][j2][1]=max(dp2[i][j2][1],dp1[i][mid2][1]+dp2[mid2][j2][1]); } if (ke[i][j1]) dp2[i][j1][0]=max(dp2[i][j1][0],dp2[j1][id(i+1)][1]+1); if (ke[i][j2]) dp2[i][j2][1]=max(dp2[i][j2][1],dp2[j2][id(i-1)][0]+1); } } } void solve(){ cin>>n>>k; for (int i=1,tam;i<=n;++i){ cin>>tam; while (tam){ cout<<i<<' '<<tam<<endl; G[i].push_back(tam); ke[i][tam]=true; dp1[i][tam][0]=dp1[i][tam][1]=1; cin>>tam; } } tim_dp1(); tim_dp2(); ii ans={0,0}; for (int i=1;i<=n;++i){ for (auto x:G[i]){ ans=max({ans,ii(dp2[x][id(i-1)][0]+1,i),ii(dp2[x][id(i+1)][1]+1,i)}); } } if (!k) { cout<<ans.fi<<endl<<ans.se; return; } for (int i=1,mid;i<=n;++i){ for (int j=1;j<=n;++j){ if (dp1[j][i][0]){ mid=0; for (int z=1,tam;z<n;++z){ tam=id(i+z); if (tam==j) break; if (ke[tam][j]) { mid=tam; break; } } if (mid) for (int z=1,tam;z<n;++z){ tam=id(mid+z); if (tam==j) break; if (!ke[i][tam]) continue; ans=max(ans,ii(max(dp2[tam][id(mid+1)][1],dp2[tam][id(j-1)][0])+dp1[j][i][0]+2,mid)); } } if (dp1[j][i][1]){ mid=0; for (int z=1,tam;z<n;++z){ tam=id(i-z); if (tam==j) break; if (ke[tam][j]){ mid=tam; break; } } if (!mid) continue; for (int z=1,tam;z<n;++z){ tam=id(mid-z); if (tam==j) break; if (!ke[i][tam]) continue; ans=max(ans,ii(max(dp2[tam][id(mid-1)][0],dp2[tam][id(j+1)][1])+dp1[j][i][1]+2,mid)); } } } } cout<<ans.fi<<endl<<ans.se; } main() { // freopen("ok.inp","r",stdin); //freopen("ok.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); solve(); // cout<<endl<<clock()/1000.0; }

Compilation message (stderr)

race.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...