oj.uz

답안 #140246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140246 2019-08-02T11:13:50 Z egorlifar Sailing Race (CEOI12_race) C++17
15 / 100
 726 ms 2536 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 = 1; 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 376 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 4 ms 636 KB Output isn't correct
7 Correct 7 ms 632 KB Output is correct
8 Incorrect 5 ms 632 KB Output isn't correct
9 Incorrect 10 ms 632 KB Output isn't correct
10 Correct 10 ms 760 KB Output is correct
11 Incorrect 12 ms 760 KB Output isn't correct
12 Incorrect 45 ms 1144 KB Output isn't correct
13 Incorrect 111 ms 1544 KB Output isn't correct
14 Incorrect 238 ms 1900 KB Output isn't correct
15 Incorrect 581 ms 2296 KB Output isn't correct
16 Incorrect 673 ms 2332 KB Output isn't correct
17 Incorrect 585 ms 2536 KB Output isn't correct
18 Incorrect 410 ms 2296 KB Output isn't correct
19 Incorrect 724 ms 2424 KB Output isn't correct
20 Incorrect 726 ms 2524 KB Output isn't correct