oj.uz

Submission #1090332

# Submission time Handle Problem Language Result Execution time Memory
1090332 2024-09-18T08:57:04 Z vjudge1 Sailing Race (CEOI12_race) C++17
10 / 100
 397 ms 3540 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][(j-1)%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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 0 ms 604 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 3 ms 860 KB Output isn't correct
8 Incorrect 2 ms 860 KB Output isn't correct
9 Incorrect 6 ms 860 KB Output isn't correct
10 Incorrect 4 ms 832 KB Output isn't correct
11 Incorrect 7 ms 860 KB Output isn't correct
12 Incorrect 34 ms 1628 KB Output isn't correct
13 Incorrect 59 ms 2648 KB Output isn't correct
14 Incorrect 130 ms 2652 KB Output isn't correct
15 Incorrect 307 ms 3420 KB Output isn't correct
16 Incorrect 350 ms 3524 KB Output isn't correct
17 Incorrect 305 ms 3284 KB Output isn't correct
18 Incorrect 218 ms 3420 KB Output isn't correct
19 Incorrect 397 ms 3540 KB Output isn't correct
20 Incorrect 391 ms 3420 KB Output isn't correct