oj.uz

Submission #203137

# Submission time Handle Problem Language Result Execution time Memory
203137 2020-02-19T13:19:28 Z godwind Collecting Stamps 3 (JOI20_ho_t3) C++14
5 / 100
 108 ms 102392 KB 
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
// #include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;

#define int long long
#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228
 
 
 
template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}
 
 
// random_device rnd;
 
// template<typename T> void shuffle(vector< T > &v) {
//     for (int i = 1; i < (int)v.size(); ++i) {
//         swap(v[rnd() % i], v[i]);
//     }
//     for (int i = (int)v.size() - 1; i; --i) {
//         swap(v[rnd() % i], v[i]);
//     }
// }

const int N = 202;
const int INF = 1e17 + 228;

int n, L;
int x[N], t[N];
int dp[N][N][N][2];

int dist(int x, int y) {
    return min(abs(x - y), L - abs(x - y));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> L;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 0; k <= n; ++k) {
                dp[i][j][k][0] = dp[i][j][k][1] = INF;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        dp[i][i][0][0] = dp[i][i][0][1] = dist(0, x[i]);
        if (dist(0, x[i]) <= t[i]) {
            dp[i][i][1][0] = dp[i][i][1][1] = dist(0, x[i]);
        }
    }
    for (int LEN = 0; LEN < n - 1; ++LEN) {
        for (int l = 1; l <= n; ++l) {
            int r = l + LEN;
            if (r > n) r -= n;
            // (l, r)
            int bl = l - 1;
            if (bl == 0) bl = n;
            int ar = r + 1;
            if (ar == n + 1) ar = 1;
            for (int k = 0; k <= LEN + 1; ++k) {
                uin(dp[bl][r][k][0], dp[l][r][k][0] + dist(x[l], x[bl]));
                if (dp[l][r][k][0] + dist(x[l], x[bl]) <= t[bl]) {
                    uin(dp[bl][r][k + 1][0], dp[l][r][k][0] + dist(x[l], x[bl]));
                }
                uin(dp[l][ar][k][1], dp[l][r][k][0] + dist(x[l], x[ar]));
                if (dp[l][r][k][0] + dist(x[l], x[ar]) <= t[ar]) {
                    uax(dp[l][ar][k + 1][1], dp[l][r][k][0] + dist(x[l], x[ar]));
                }

                uin(dp[l][ar][k][1], dp[l][r][k][1] + dist(x[r], x[ar]));
                if (dp[l][r][k][1] + dist(x[r], x[ar]) <= t[ar]) {
                    uin(dp[l][ar][k + 1][1], dp[l][r][k][1] + dist(x[r], x[ar]));
                }
                uin(dp[bl][r][k][0], dp[l][r][k][1] + dist(x[r], x[bl]));
                if (dp[l][r][k][1] + dist(x[r], x[bl]) <= t[bl]) {
                    uin(dp[bl][r][k + 1][0], dp[l][r][k][1] + dist(x[r], x[bl]));
                }
            }
        }
    }
    int answer = 0;
    for (int l = 1; l <= n; ++l) {
        for (int r = 1; r <= n; ++r) {
            for (int tet = 0; tet < 2; ++tet) {
                for (int k = 1; k <= n; ++k) {
                    if (dp[l][r][k][tet] < INF / 2) {
                        uax(answer, k);
                    }
                }
            }
        }
    }
    cout << answer << '\n';
    return 0;
}
// RU_023
 
 
/*
6 25
3 4 7 17 21 23
11 7 17 10 8 10
---
4


5 20
4 5 8 13 17
18 23 15 7 10
---
5

4 19
3 7 12 14
2 0 5 4
---
0

10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
---
5


*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 760 KB Output is correct
13 Correct 5 ms 760 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 6 ms 760 KB Output is correct
17 Correct 5 ms 760 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 760 KB Output is correct
13 Correct 5 ms 760 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 6 ms 760 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 5 ms 1016 KB Output is correct
19 Correct 5 ms 636 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 5 ms 1016 KB Output is correct
22 Correct 5 ms 632 KB Output is correct
23 Correct 5 ms 1016 KB Output is correct
24 Correct 5 ms 888 KB Output is correct
25 Incorrect 5 ms 1016 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 760 KB Output is correct
13 Correct 5 ms 760 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 6 ms 760 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 108 ms 102392 KB Output is correct
19 Correct 64 ms 61944 KB Output is correct
20 Correct 36 ms 32888 KB Output is correct
21 Correct 64 ms 58360 KB Output is correct
22 Correct 75 ms 75896 KB Output is correct
23 Incorrect 28 ms 27896 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 760 KB Output is correct
13 Correct 5 ms 760 KB Output is correct
14 Correct 5 ms 504 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 6 ms 760 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 5 ms 1016 KB Output is correct
19 Correct 5 ms 636 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 5 ms 1016 KB Output is correct
22 Correct 5 ms 632 KB Output is correct
23 Correct 5 ms 1016 KB Output is correct
24 Correct 5 ms 888 KB Output is correct
25 Incorrect 5 ms 1016 KB Output isn't correct
26 Halted 0 ms 0 KB -