oj.uz

Submission #140244

# Submission time Handle Problem Language Result Execution time Memory
140244 2019-08-02T11:12:30 Z egorlifar Sailing Race (CEOI12_race) C++17
15 / 100
 737 ms 2604 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, t;
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 >> t;
    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++) {
                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 - (cur == i ? 1: 0)][(i == cur ? (i + 1) % n: i)][1] + 1);
                            chkmax(dp[len][i][t], dp[(len - k) - (cur == j ? 1: 0)][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 << endl;
    cout << pos << endl;
    return 0; 
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 508 KB Output isn't correct
4 Incorrect 0 ms 504 KB Output isn't correct
5 Incorrect 1 ms 504 KB Output isn't correct
6 Incorrect 4 ms 632 KB Output isn't correct
7 Correct 6 ms 632 KB Output is correct
8 Incorrect 5 ms 632 KB Output isn't correct
9 Incorrect 9 ms 632 KB Output isn't correct
10 Correct 10 ms 760 KB Output is correct
11 Incorrect 13 ms 760 KB Output isn't correct
12 Incorrect 53 ms 1144 KB Output isn't correct
13 Incorrect 115 ms 1532 KB Output isn't correct
14 Incorrect 248 ms 2040 KB Output isn't correct
15 Incorrect 600 ms 2488 KB Output isn't correct
16 Incorrect 677 ms 2412 KB Output isn't correct
17 Incorrect 597 ms 2476 KB Output isn't correct
18 Incorrect 416 ms 2340 KB Output isn't correct
19 Incorrect 737 ms 2604 KB Output isn't correct
20 Incorrect 736 ms 2596 KB Output isn't correct