Submission #832281

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
832281	2023-08-21T08:24:39 Z	TS_2392	Sailing Race (CEOI12_race)	C++14	0 / 100	1107 ms	5296 KB

race

#include <bits/stdc++.h>
using namespace std;

#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED {ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);}
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}

const int N = 503;
int n, type, res, nxt[N], prv[N];
int adj[N][N], dp1[N][N][2], dp2[N][N][2];
int main(){
    cin >> n >> type;
    for(int u = 1, v; u <= n; ++u){
        while(cin >> v){
            if(v == 0) break;
            else adj[u][v] = 1;
        }
        nxt[u] = u + 1; prv[u] = u - 1;
    }
    nxt[n] = 1; prv[1] = n;
    for(int len = 2; len < n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1;
            if(j > n) j -= n;

            if(adj[i][j]) dp1[i][j][0] = 1;
            for(int k = nxt[i]; k != j; k = nxt[k]) if(adj[k][j] && dp1[i][k][0]){
                maximize(dp1[i][j][0], dp1[i][k][0] + 1);
            }

            if(adj[j][i]) dp1[i][j][1] = 1;
            for(int k = prv[j]; k != i; k = prv[k]) if(adj[k][i] && dp1[k][j][1]){
                maximize(dp1[i][j][1], dp1[k][j][1] + 1);
            }

        }
    }
    for(int len = 2; len < n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1;
            if(j > n) j -= n;

            dp2[i][j][0] = dp2[i][prv[j]][0];
            if(adj[i][j]) maximize(dp2[i][j][0], dp2[nxt[i]][j][1] + 1);
            for(int k = nxt[i]; k != j; k = nxt[k]) if(adj[k][j] && dp1[i][k][0]){
                maximize(dp2[i][j][0], dp1[i][k][0] + 1 + dp2[nxt[k]][j][1]);
            }

            dp2[i][j][1] = dp2[nxt[i]][j][1];
            if(adj[j][i]) maximize(dp2[i][j][1], dp2[i][prv[j]][0] + 1);
            for(int k = prv[j]; k != i; k = prv[k]) if(adj[k][i] && dp1[k][j][1]){
                maximize(dp2[i][j][1], dp1[k][j][1] + 1 + dp2[i][prv[k]][0]);
            }

            maximize(res, dp2[i][j][0]);
            maximize(res, dp2[i][j][1]);
        }
    }
    cout << res;
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 KB	Unexpected end of file - int32 expected
2	Incorrect	0 ms	468 KB	Output isn't correct
3	Incorrect	1 ms	596 KB	Output isn't correct
4	Incorrect	1 ms	596 KB	Output isn't correct
5	Incorrect	2 ms	724 KB	Unexpected end of file - int32 expected
6	Incorrect	3 ms	796 KB	Output isn't correct
7	Incorrect	5 ms	980 KB	Output isn't correct
8	Incorrect	5 ms	1108 KB	Output isn't correct
9	Incorrect	11 ms	1108 KB	Output isn't correct
10	Incorrect	9 ms	1288 KB	Output isn't correct
11	Incorrect	14 ms	1292 KB	Output isn't correct
12	Incorrect	64 ms	2268 KB	Output isn't correct
13	Incorrect	184 ms	3248 KB	Output isn't correct
14	Incorrect	370 ms	4240 KB	Unexpected end of file - int32 expected
15	Incorrect	856 ms	5168 KB	Output isn't correct
16	Incorrect	946 ms	5216 KB	Output isn't correct
17	Incorrect	878 ms	5220 KB	Output isn't correct
18	Incorrect	645 ms	5172 KB	Unexpected end of file - int32 expected
19	Incorrect	1107 ms	5212 KB	Output isn't correct
20	Incorrect	1016 ms	5296 KB	Output isn't correct