oj.uz

Submission #1090357

# Submission time Handle Problem Language Result Execution time Memory
1090357 2024-09-18T09:27:06 Z vjudge1 Sailing Race (CEOI12_race) C++17
10 / 100
 270 ms 3676 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

int dp[505][505][2], mat[505][505], n, shit;

bool check(int l, int r, int i) {
    if(l < i && i < r) return 1;
    if(r < l && (l < i && i < r)) return 1; 
    return 0;
}

int f(int l, int r, int t) {
    if(dp[l][r][t] != -1) return dp[l][r][t];

    int ans = 0, p = (t ? l : r);
    for(int i=0; i<n; i++) {
        if(!mat[p][i] || !check(l, r, i)) continue;
        ans = max(ans, max(f(l, i, 0), f(i, r, 1)) + 1);
    }

    return dp[l][r][t] = ans;
}

signed main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> shit;

    for(int i=0; i<n; i++) {
        int x;
        while(cin >> x) {
            if(!x) break;
            mat[i][x-1] = 1;
        }
    }

    int ans=-1, pos=-1;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(!mat[i][j]) continue;
            int res = max(f(i, j, 0), f(j, i, 1)) + 1;
            if(res > ans) {
                ans = res;
                pos = i + 1;
            }
        }
    }

    cout << ans << " " << pos << '\n';
    return 0;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Incorrect 2 ms 2400 KB Output isn't correct
6 Incorrect 2 ms 2396 KB Output isn't correct
7 Incorrect 2 ms 2396 KB Output isn't correct
8 Incorrect 2 ms 2396 KB Output isn't correct
9 Incorrect 3 ms 2396 KB Output isn't correct
10 Correct 4 ms 2652 KB Output is correct
11 Incorrect 4 ms 2492 KB Output isn't correct
12 Incorrect 14 ms 2648 KB Output isn't correct
13 Incorrect 33 ms 2908 KB Output isn't correct
14 Incorrect 74 ms 3236 KB Output isn't correct
15 Incorrect 192 ms 3500 KB Output isn't correct
16 Incorrect 229 ms 3420 KB Output isn't correct
17 Incorrect 192 ms 3676 KB Output isn't correct
18 Incorrect 102 ms 3416 KB Output isn't correct
19 Incorrect 261 ms 3580 KB Output isn't correct
20 Incorrect 270 ms 3420 KB Output isn't correct