oj.uz

Submission #140242

# Submission time Handle Problem Language Result Execution time Memory
140242 2019-08-02T11:05:00 Z egorlifar Sailing Race (CEOI12_race) C++17
0 / 100
 649 ms 2648 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { x = (x > y ? y: x);}
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { x = (x < y ? y: x);}
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 501;

int n, k;
bitset<501> b[MAXN];
int dp[MAXN][MAXN][2];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME); 
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int a;
        while (cin >> a) {
            if (a == 0) {
                break;
            }
            b[i][a - 1] = true;
        }
    }
    for (int len = 0; len <= n - 1; len++) {
        for (int i = 0; i < n; i++) {
            int j = (i + len) % n;
            for (int t = 0; t < 2; t++) {
                dp[len][i][t] = 1;
                int cur = (t == 0 ? i: j);
                for (int k = 0; k <= len; k++) {
                    int g = (i + k >= n ? i + k - n: i + k);
                    if (g != cur) {
                        if (b[cur][g]) {
                            chkmax(dp[len][i][t], dp[k][i][1] + 1);
                            chkmax(dp[len][i][t], dp[(len - k)][g][0] + 1);
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    int pos = -1;
    for (int i =  0; i < n; i++) {
        chkmax(res, dp[n - 1][i][0]);
        if (res == dp[n - 1][i][0]) {
            pos = i;
        }
        chkmax(res, dp[n - 1][i][1]);
        if (res == dp[n - 1][i][1]) {
            pos = (i + n - 1) % n;
        }
    }
    cout << res - 1 << endl;
    cout << pos << endl;
    return 0; 
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 17 ms 504 KB Output isn't correct
3 Incorrect 3 ms 504 KB Output isn't correct
4 Incorrect 3 ms 504 KB Output isn't correct
5 Incorrect 3 ms 504 KB Output isn't correct
6 Incorrect 3 ms 632 KB Output isn't correct
7 Incorrect 5 ms 632 KB Output isn't correct
8 Incorrect 4 ms 632 KB Output isn't correct
9 Incorrect 8 ms 760 KB Output isn't correct
10 Incorrect 8 ms 760 KB Output isn't correct
11 Incorrect 11 ms 760 KB Output isn't correct
12 Incorrect 39 ms 1144 KB Output isn't correct
13 Incorrect 106 ms 1528 KB Output isn't correct
14 Incorrect 215 ms 2040 KB Output isn't correct
15 Incorrect 510 ms 2548 KB Output isn't correct
16 Incorrect 564 ms 2532 KB Output isn't correct
17 Incorrect 512 ms 2512 KB Output isn't correct
18 Incorrect 383 ms 2576 KB Output isn't correct
19 Incorrect 621 ms 2648 KB Output isn't correct
20 Incorrect 649 ms 2628 KB Output isn't correct