Submission #1095440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1095440	2024-10-02T08:01:28 Z	hqminhuwu	Sailing Race (CEOI12_race)	C++14	40 / 100	308 ms	9564 KB

race

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 1e3 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int debug = 0;

int dp[N][N][2], n, t, u;
vector <int> a[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef hqm
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> t;

    forr (i, 1, n){
        while (cin >> u && u != 0){
            a[u].pb(i);
            a[u + n].pb(i);
            a[u].pb(i + n);
            a[u + n].pb(i + n);
        }
    }

    memset (dp, -1, sizeof dp);

    forr (i, 1, 2 * n){
        for (int u : a[i]){
            if (u < i)
                dp[u][i][0] = 1;
            else dp[i][u][1] = 1;
        }
    }

    int mx = 0, pos = 0;

    forr (len, 1, n){
        forr (i, 1, 2 * n - len + 1){
            int u = i, v = i + len - 1;

            forr (t, 0, 1){
                int e = (t ? v : u);

                if (dp[u][v][t] > mx){
                    mx = dp[u][v][t];
                    pos = e - n * (e > n);
                } 

                if (dp[u][v][t] != -1){
                    if (debug)
                        cout << u << " " << v << " " << t << " " << dp[u][v][t] << "\n";
                    for (int w : a[e]){
                        if (w < u){
                            maxz(dp[w][v][0], dp[u][v][t] + 1);
                        } else if (w > v){
                            maxz(dp[u][w][1], dp[u][v][t] + 1);
                        }
                    }
                }
            }
        }
    }   
    

    cout << mx << " " << pos << "\n";

    return 0;
}
/*



*/

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8536 KB	Output is correct
2	Incorrect	3 ms	8280 KB	Output isn't correct
3	Incorrect	4 ms	8284 KB	Output isn't correct
4	Incorrect	3 ms	8284 KB	Output isn't correct
5	Correct	4 ms	8268 KB	Output is correct
6	Incorrect	4 ms	8284 KB	Output isn't correct
7	Correct	6 ms	8284 KB	Output is correct
8	Incorrect	5 ms	8284 KB	Output isn't correct
9	Correct	8 ms	8344 KB	Output is correct
10	Correct	15 ms	8540 KB	Output is correct
11	Correct	10 ms	8284 KB	Output is correct
12	Incorrect	25 ms	8568 KB	Output isn't correct
13	Incorrect	38 ms	8540 KB	Output isn't correct
14	Correct	74 ms	8540 KB	Output is correct
15	Incorrect	211 ms	9052 KB	Output isn't correct
16	Incorrect	264 ms	9564 KB	Output isn't correct
17	Incorrect	217 ms	9048 KB	Output isn't correct
18	Correct	86 ms	8536 KB	Output is correct
19	Incorrect	306 ms	9560 KB	Output isn't correct
20	Incorrect	308 ms	9564 KB	Output isn't correct