oj.uz

Submission #297809

# Submission time Handle Problem Language Result Execution time Memory
297809 2020-09-12T01:52:09 Z balbit Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 73 ms 133368 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define MX(a,b) a=max(a,b)
#define MN(a,b) a=min(a,b)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

void GG(){cout<<-1<<endl; exit(0);}

const int maxn = 204;

ll n,L;
ll X[maxn], T[maxn];
ll dp[maxn][maxn][2][maxn]; // (l,r) is not explored, ,stamps)

signed main(){
    IOS();
    memset(dp, 0x3f, sizeof dp);
    cin>>n>>L;
    for (ll i = 1 ;i<=n; ++i) cin>>X[i];
    X[n+1] = L;
    for (ll i = 1 ;i<=n; ++i) cin>>T[i];
    ++n;
    dp[0][n][0][0]=0;
    dp[0][n][1][0]=0;
    T[0] = -1;
    ll re = 0;
    for (ll df = n-1; df >= 1; --df) {
        for (ll i = 0; i+df <= n; ++i) {
            ll j = i+df;
            for (ll g = 0; g <= n; ++g) {
                if (i)
                    MN(dp[i][j][0][g], dp[i-1][j][0][g] + X[i] - X[i-1]);
                if (j!=n)
                    MN(dp[i][j][1][g], dp[i][j+1][1][g] + X[j+1] - X[j]);
                if (g) {
                    if (i && dp[i-1][j][0][g-1] + X[i] - X[i-1] <= T[i])
                        MN(dp[i][j][0][g], dp[i-1][j][0][g-1] + X[i] - X[i-1]);

                    if (j != n && dp[i][j+1][0][g-1] + X[j+1] - X[j] <= T[j])
                        MN(dp[i][j][1][g], dp[i][j+1][1][g-1] + X[j+1] - X[j]);
                }
                MN(dp[i][j][0][g], dp[i][j][1][g] + L - X[j] + X[i]);
                MN(dp[i][j][1][g], dp[i][j][0][g] + L - X[j] + X[i]);
                if (min(dp[i][j][0][g],dp[i][j][1][g]) < 10000000000ll) {
                    MX(re, g);
                    bug(dp[i][j][0][g], i,j,g);
                }
            }

        }
    }

    cout<<re<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 133240 KB Output is correct
2 Correct 72 ms 133368 KB Output is correct
3 Correct 73 ms 133300 KB Output is correct
4 Incorrect 70 ms 133240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 133240 KB Output is correct
2 Correct 72 ms 133368 KB Output is correct
3 Correct 73 ms 133300 KB Output is correct
4 Incorrect 70 ms 133240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 133240 KB Output is correct
2 Correct 72 ms 133368 KB Output is correct
3 Correct 73 ms 133300 KB Output is correct
4 Incorrect 70 ms 133240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 133240 KB Output is correct
2 Correct 72 ms 133368 KB Output is correct
3 Correct 73 ms 133300 KB Output is correct
4 Incorrect 70 ms 133240 KB Output isn't correct
5 Halted 0 ms 0 KB -