oj.uz

Submission #203133

# Submission time Handle Problem Language Result Execution time Memory
203133 2020-02-19T13:08:31 Z godwind Collecting Stamps 3 (JOI20_ho_t3) C++14
5 / 100
 100 ms 102264 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; ++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) {
        int r = l + n-1;
        if (r > n) r -= n;
        for (int k = 0; k <= n; ++k) {
            if (dp[l][r][k][0] != INF || dp[l][r][k][1] != INF) 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 380 KB Output is correct
2 Correct 5 ms 376 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 508 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 5 ms 632 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 2 ms 504 KB Output is correct
15 Correct 5 ms 508 KB Output is correct
16 Correct 5 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 380 KB Output is correct
2 Correct 5 ms 376 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 508 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 5 ms 632 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 2 ms 504 KB Output is correct
15 Correct 5 ms 508 KB Output is correct
16 Correct 5 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 632 KB Output is correct
20 Correct 5 ms 764 KB Output is correct
21 Correct 5 ms 1016 KB Output is correct
22 Correct 5 ms 636 KB Output is correct
23 Correct 5 ms 1016 KB Output is correct
24 Correct 5 ms 892 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 380 KB Output is correct
2 Correct 5 ms 376 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 508 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 5 ms 632 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 2 ms 504 KB Output is correct
15 Correct 5 ms 508 KB Output is correct
16 Correct 5 ms 760 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 100 ms 102264 KB Output is correct
19 Correct 53 ms 61944 KB Output is correct
20 Correct 34 ms 32888 KB Output is correct
21 Correct 50 ms 58360 KB Output is correct
22 Correct 62 ms 75768 KB Output is correct
23 Incorrect 24 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 380 KB Output is correct
2 Correct 5 ms 376 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 508 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 5 ms 632 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 2 ms 504 KB Output is correct
15 Correct 5 ms 508 KB Output is correct
16 Correct 5 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 632 KB Output is correct
20 Correct 5 ms 764 KB Output is correct
21 Correct 5 ms 1016 KB Output is correct
22 Correct 5 ms 636 KB Output is correct
23 Correct 5 ms 1016 KB Output is correct
24 Correct 5 ms 892 KB Output is correct
25 Incorrect 5 ms 1016 KB Output isn't correct
26 Halted 0 ms 0 KB -