oj.uz

Submission #1090333

# Submission time Handle Problem Language Result Execution time Memory
1090333 2024-09-18T08:58:39 Z vjudge1 Sailing Race (CEOI12_race) C++17
5 / 100
 385 ms 3672 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];

signed main() {
    int n, k;
    cin >> n >> k;

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

    for(int len=1; len<=n; len++) {
        for(int i=0; i<n; i++) {
            int j = (i + len - 1) % n;
            if(mat[i][j]) dp[i][j][0] = max(dp[i][j][0], dp[(i+1)%n][j][1] + 1);
            if(mat[j][i]) dp[i][j][1] = max(dp[i][j][1], dp[i][(i+len-2)%n][0] + 1);
            for(int k=i+1; k<i+len-1; k++) {
                int x = k % n;
                dp[i][j][0] = max(dp[i][j][0], dp[i][x][0]);
                dp[i][j][1] = max(dp[i][j][1], dp[x][j][1]);
                if(mat[i][x]) dp[i][j][0] = max(dp[i][j][0], dp[x][j][0] + 1);
                if(mat[j][x]) dp[i][j][1] = max(dp[i][j][1], dp[i][x][1] + 1);
            }
        }
    }

    int ans = -1, ans2 = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(dp[i][j][0] > ans) {
                ans = dp[i][j][0];
                ans2 = i;
            }
            if(dp[i][j][1] > ans) {
                ans = dp[i][j][1];
                ans2 = j;
            }
        }
    }
    cout << ans + 1 << '\n' << ans2 + 1 << '\n';
    return 0;
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 3 ms 868 KB Output isn't correct
8 Incorrect 2 ms 860 KB Output isn't correct
9 Incorrect 5 ms 860 KB Output isn't correct
10 Incorrect 4 ms 964 KB Output isn't correct
11 Incorrect 7 ms 1052 KB Output isn't correct
12 Incorrect 25 ms 1628 KB Output isn't correct
13 Incorrect 60 ms 2136 KB Output isn't correct
14 Incorrect 127 ms 2648 KB Output isn't correct
15 Incorrect 304 ms 3416 KB Output isn't correct
16 Incorrect 345 ms 3332 KB Output isn't correct
17 Incorrect 292 ms 3416 KB Output isn't correct
18 Incorrect 200 ms 3420 KB Output isn't correct
19 Incorrect 385 ms 3672 KB Output isn't correct
20 Incorrect 385 ms 3420 KB Output isn't correct