Submission #36781

#TimeUsernameProblemLanguageResultExecution timeMemory
36781RockyBSailing Race (CEOI12_race)C++14
40 / 100
1129 ms6304 KiB
/// In The Name Of God #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx") #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define pp pop_back #define mp make_pair #define sz(x) (int)x.size() #define sqr(x) ((x) * 1ll * (x)) #define all(x) x.begin(), x.end() #define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define nl '\n' #define ioi exit(0); typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = (int)500 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7; const ll linf = (ll)1e18 + 7; const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; using namespace std; int n, k; vector <int> g[N]; bool ok[N][N]; int dp[N][N][2]; int dp1[N][N][2]; int nxt(int x) { if (x == 1) return n; return x - 1; } int prv(int x) { if (x == n) return 1; return x + 1; } int calc(int A, int B, int t) { if (~dp[A][B][t]) return dp[A][B][t]; int res = 0; if (t) { for (int i = nxt(A); i != B; i = nxt(i)) { if (ok[B][i]) { res = max(res, calc(A, i, 1) + 1); res = max(res, calc(B, i, 0) + 1); } } } else { for (int i = prv(A); i != B; i = prv(i)) { if (ok[B][i]) { res = max(res, calc(A, i, 0) + 1); res = max(res, calc(B, i, 1) + 1); } } } return dp[A][B][t] = res; } int f(int A, int B, int t) { if (A == B) return 0; if (~dp1[A][B][t]) return dp1[A][B][t]; int res = -inf; if (t) { for (int i = nxt(A); ; i = nxt(i)) { if (ok[A][i]) res = max(res, f(i, B, 1) + 1); if (i == B) break; } } else { for (int i = prv(A); ; i = prv(i)) { if (ok[A][i]) res = max(res, f(i, B, 0) + 1); if (i == B) break; } } return dp1[A][B][t] = res; } int mx, opt; int res[N]; void bye() { printf ("%d\n%d", mx, opt); ioi } void solve() { memset(dp1, -1, sizeof(dp1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { f(i, j, 0), f(i, j, 1); } } for (int j = 1; j <= n; j++) { for (int l = prv(j); l != j; l = prv(l)) { int mxi = -1, opti = -1; for (int r = prv(l); r != j; r = prv(r)) { ///case1 if (opti != -1 && ok[r][l] && 2 + dp1[j][r][1] + dp[j][l][0] > mx) { mx++; opt = opti; bye(); } ///case2 if (opti != -1 && ok[r][l] && 2 + mxi + dp1[j][r][1] > mx) { mx++; opt = opti; bye(); } ///case3 if (opti != -1 && ok[r][l] && 2 + dp1[j][l][0] + dp[j][r][1] > mx) { mx++; opt = opti; bye(); } if (ok[r][j] && dp[r][l][1] > mxi) { mxi = dp[r][l][1]; opti = r; bye(); } } } } assert(0); } int main() { #ifdef IOI2018 freopen ("in.txt", "r", stdin); #endif scanf ("%d%d", &n, &k); for (int i = 1; i <= n; i++) { int to; while (scanf ("%d", &to) && to) { ok[i][to] = 1; } } memset(dp, -1, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { calc(i, j, 0), calc(i, j, 1); if (ok[i][j]) res[i] = max(res[i], max(calc(i, j, 0), calc(i, j, 1)) + 1); if (res[i] > mx) mx = res[i], opt = i; } } if (k == 1) solve(); else bye(); bye(); ioi }

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:144:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...