oj.uz

Submission #1090353

# Submission time Handle Problem Language Result Execution time Memory
1090353 2024-09-18T09:24:56 Z vjudge1 Sailing Race (CEOI12_race) C++17
10 / 100
 276 ms 3792 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 = 1, 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));
            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 1 ms 2396 KB Output isn't correct
6 Incorrect 2 ms 2500 KB Output isn't correct
7 Incorrect 3 ms 2396 KB Output isn't correct
8 Incorrect 2 ms 2396 KB Output isn't correct
9 Incorrect 4 ms 2392 KB Output isn't correct
10 Correct 5 ms 2672 KB Output is correct
11 Incorrect 7 ms 2648 KB Output isn't correct
12 Incorrect 16 ms 2652 KB Output isn't correct
13 Incorrect 33 ms 2908 KB Output isn't correct
14 Incorrect 73 ms 3244 KB Output isn't correct
15 Incorrect 196 ms 3508 KB Output isn't correct
16 Incorrect 228 ms 3792 KB Output isn't correct
17 Incorrect 201 ms 3420 KB Output isn't correct
18 Incorrect 105 ms 3416 KB Output isn't correct
19 Incorrect 262 ms 3404 KB Output isn't correct
20 Incorrect 276 ms 3568 KB Output isn't correct