Submission #59289

#TimeUsernameProblemLanguageResultExecution timeMemory
59289MatheusLealVSailing Race (CEOI12_race)C++17
40 / 100
736 ms9952 KiB
#include <bits/stdc++.h> #define N 1001 using namespace std; int n, k, ans, opt, dp[N][N][2]; vector<int> grafo[N]; int solve(int l, int r, int f) { int ans = 0; if(l > r) return 0; if(dp[l][r][f] != -1) return dp[l][r][f]; if(f == 0) { for(auto v: grafo[l]) { if(l + 1 <= v and v <= r - 1) { int aux = max(solve(l, v, 1), solve(v, r, 0)) + 1; ans = max(ans, aux); } } } else { for(auto v: grafo[r]) { if(l + 1 <= v and v <= r - 1) { int aux = max(solve(l, v, 1), solve(v, r, 0)) + 1; ans = max(ans, aux); } } } //cout<<"SOLVE "<<l<<", "<<r<<" "<<ans<<"\n"; return dp[l][r][f] = ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; memset(dp, -1, sizeof dp); for(int i = 1; i <= n; i++) { while(true) { int x; cin>>x; if(!x) break; grafo[i].push_back(x); grafo[i].push_back(n + x); grafo[i + n].push_back(x); grafo[i + n].push_back(x + n); } } for(int i = 1; i <= 2*n; i++) { for(auto v: grafo[i]) { if(abs(i - v) >= n) continue; if(i < v) { int S = solve(i, v, 1) + 1, S2 = 0;//solve(v, i + n, 0) + 1; //cout<<"AAA "<<v<<" "<<i + n<<"\n"; if(S >= ans) ans = S, opt = i; //if(S2 >= ans) ans = S2, opt = i; } else if(i > v) { int S = solve(v, i, 0) + 1, S2 = 0;//solve(i, v + n, 1) + 1; //cout<<"ff "<<v + n<<" "<<i<<"\n"; if(S >= ans) ans = S, opt = i; //if(S2 >= ans) ans = S2, opt = i; } } } cout<<ans<<"\n"<<(opt <= n ? opt : opt - n)<<"\n"; }

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:84:33: warning: unused variable 'S2' [-Wunused-variable]
     int S = solve(i, v, 1) + 1, S2 = 0;//solve(v, i + n, 0) + 1;
                                 ^~
race.cpp:95:33: warning: unused variable 'S2' [-Wunused-variable]
     int S = solve(v, i, 0) + 1, S2 = 0;//solve(i, v + n, 1) + 1;
                                 ^~
#Verdict Execution timeMemoryGrader output
Fetching results...