oj.uz

Submission #750715

# Submission time Handle Problem Language Result Execution time Memory
750715 2023-05-30T07:57:30 Z Sami_Massah Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 39 ms 74884 KB 
#include <bits/stdc++.h>
using namespace std;



const int maxn = 200 + 12, inf = 1e9 + 12;
int n, L, dist[maxn], t[maxn], dp[maxn][maxn][maxn][2];
int get_dist(int a, int b){
    if(a == n - 1 && b == 0)
        return L - dist[a];
    return abs(dist[a] - dist[b]);

}
int find_ans(int a, int b, int c, int d){
    if(c < 0)
        return inf;
    if(dp[a][b][c][d] != -1)
        return dp[a][b][c][d];
    dp[a][b][c][d] = inf;
    //cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
    if(d == 0){
        if(a != 0){
            dp[a][b][c][d] = min(dp[a][b][c][d], find_ans((a + 1) % n, b, c, d) + get_dist(a, a + 1));
            int x = find_ans((a + 1) % n, b, c - 1, d) + get_dist(a, a + 1);
            if(x <= t[a])
                dp[a][b][c][d] = min(dp[a][b][c][d], x);
        }
        if(a != 0){
            dp[a][b][c][d] = min(dp[a][b][c][d], find_ans((a + 1) % n, b, c, d ^ 1) + L - dist[a] + dist[b]);
            int x = find_ans((a + 1) % n, b, c - 1, d ^ 1) + L - dist[a] + dist[b];
            if(x <= t[a])
                dp[a][b][c][d] = min(dp[a][b][c][d], x);
        }
    }
    if(d == 1){
        if(b != 0){
            dp[a][b][c][d] = min(dp[a][b][c][d], find_ans(a, b - 1, c, d) + get_dist(b, b - 1));
            int x = find_ans(a, b - 1, c - 1, d) + get_dist(b, b - 1);
            if(x <= t[b])
                dp[a][b][c][d] = min(dp[a][b][c][d], x);
        }
        if(b != 0){
            dp[a][b][c][d] = min(dp[a][b][c][d], find_ans(a, b - 1, c, d ^ 1) + L - dist[a] + dist[b]);
            int x = find_ans(a, b - 1, c - 1, d ^ 1) + L - dist[a] + dist[b];
            if(x <= t[b])
                dp[a][b][c][d] = min(dp[a][b][c][d], x);
        }

    }

    return dp[a][b][c][d];



}

int main(){
    memset(dp, -1, sizeof dp);
    cin >> n >> L;
    for(int i = 1; i <= n; i++)
        cin >> dist[i];
    for(int i = 1; i <= n; i++)
        cin >> t[i];
    t[0] = 0;
    dist[0] = 0;
    n += 1;
    dp[0][0][0][0] = 0;
    dp[0][0][1][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][1][1] = 0;
    int ans = 0;

    for(int i = 0; i <= n; i++)
        for(int j = 0; j < i; j++)
            for(int c = 0; c <= n; c++)
                for(int d = 0; d < 2; d++){
                    find_ans(i, j, c, d);
                    if(dp[i][j][c][d] != inf)
                        ans = max(ans, c);
            }
    for(int j = 0; j <= n; j++)
        for(int c = 0; c <= n; c++)
            for(int d = 0; d < 2; d++){
                find_ans(0, j, c, d);
                if(dp[0][j][c][d] != inf)
                    ans = max(ans, c);
            }
    cout << ans - 1 << endl;

}

Compilation message

ho_t3.cpp: In function 'int _Z8find_ansiiii.part.0(int, int, int, int)':
ho_t3.cpp:10:26: warning: array subscript -1 is below array bounds of 'int [212]' [-Warray-bounds]
   10 |         return L - dist[a];
      |                    ~~~~~~^
ho_t3.cpp:7:11: note: while referencing 'dist'
    7 | int n, L, dist[maxn], t[maxn], dp[maxn][maxn][maxn][2];
      |           ^~~~
ho_t3.cpp:10:26: warning: array subscript -1 is below array bounds of 'int [212]' [-Warray-bounds]
   10 |         return L - dist[a];
      |                    ~~~~~~^
ho_t3.cpp:7:11: note: while referencing 'dist'
    7 | int n, L, dist[maxn], t[maxn], dp[maxn][maxn][maxn][2];
      |           ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 74836 KB Output is correct
2 Correct 30 ms 74804 KB Output is correct
3 Correct 33 ms 74884 KB Output is correct
4 Correct 31 ms 74824 KB Output is correct
5 Correct 31 ms 74868 KB Output is correct
6 Correct 36 ms 74816 KB Output is correct
7 Correct 33 ms 74812 KB Output is correct
8 Correct 28 ms 74864 KB Output is correct
9 Correct 30 ms 74864 KB Output is correct
10 Correct 33 ms 74872 KB Output is correct
11 Correct 33 ms 74868 KB Output is correct
12 Correct 32 ms 74776 KB Output is correct
13 Correct 39 ms 74836 KB Output is correct
14 Correct 31 ms 74836 KB Output is correct
15 Correct 31 ms 74828 KB Output is correct
16 Incorrect 34 ms 74836 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 74836 KB Output is correct
2 Correct 30 ms 74804 KB Output is correct
3 Correct 33 ms 74884 KB Output is correct
4 Correct 31 ms 74824 KB Output is correct
5 Correct 31 ms 74868 KB Output is correct
6 Correct 36 ms 74816 KB Output is correct
7 Correct 33 ms 74812 KB Output is correct
8 Correct 28 ms 74864 KB Output is correct
9 Correct 30 ms 74864 KB Output is correct
10 Correct 33 ms 74872 KB Output is correct
11 Correct 33 ms 74868 KB Output is correct
12 Correct 32 ms 74776 KB Output is correct
13 Correct 39 ms 74836 KB Output is correct
14 Correct 31 ms 74836 KB Output is correct
15 Correct 31 ms 74828 KB Output is correct
16 Incorrect 34 ms 74836 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 74836 KB Output is correct
2 Correct 30 ms 74804 KB Output is correct
3 Correct 33 ms 74884 KB Output is correct
4 Correct 31 ms 74824 KB Output is correct
5 Correct 31 ms 74868 KB Output is correct
6 Correct 36 ms 74816 KB Output is correct
7 Correct 33 ms 74812 KB Output is correct
8 Correct 28 ms 74864 KB Output is correct
9 Correct 30 ms 74864 KB Output is correct
10 Correct 33 ms 74872 KB Output is correct
11 Correct 33 ms 74868 KB Output is correct
12 Correct 32 ms 74776 KB Output is correct
13 Correct 39 ms 74836 KB Output is correct
14 Correct 31 ms 74836 KB Output is correct
15 Correct 31 ms 74828 KB Output is correct
16 Incorrect 34 ms 74836 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 74836 KB Output is correct
2 Correct 30 ms 74804 KB Output is correct
3 Correct 33 ms 74884 KB Output is correct
4 Correct 31 ms 74824 KB Output is correct
5 Correct 31 ms 74868 KB Output is correct
6 Correct 36 ms 74816 KB Output is correct
7 Correct 33 ms 74812 KB Output is correct
8 Correct 28 ms 74864 KB Output is correct
9 Correct 30 ms 74864 KB Output is correct
10 Correct 33 ms 74872 KB Output is correct
11 Correct 33 ms 74868 KB Output is correct
12 Correct 32 ms 74776 KB Output is correct
13 Correct 39 ms 74836 KB Output is correct
14 Correct 31 ms 74836 KB Output is correct
15 Correct 31 ms 74828 KB Output is correct
16 Incorrect 34 ms 74836 KB Output isn't correct
17 Halted 0 ms 0 KB -