oj.uz

Submission #371531

# Submission time Handle Problem Language Result Execution time Memory
371531 2021-02-26T20:35:34 Z ritul_kr_singh Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 1 ms 364 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

int n, l, x[202], t[202];

int d(int i, int j){
    if(i>j) swap(i, j);
    return min(x[j]-x[i], l-(x[j]-x[i]));
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> l;
    for(int i=1; i<=n; ++i) cin >> x[i];
    for(int i=1; i<=n; ++i) cin >> t[i];
    x[0] = 0, x[n+1] = l;
    t[0] = -1, t[n+1] = -1;
    int dp[n+2][n+2][n+1][2];
    for(int i=0; i<n+2; ++i)
        for(int j=0; j<n+2; ++j)
            for(int k=0; k<=n; ++k)
                dp[i][j][k][0] = dp[i][j][k][1] = 1e10;
    dp[0][n+1][0][0] = 0;
    dp[0][n+1][0][1] = 0;
    int ans = 0;
    for(int k=1; k<=n; ++k){
        for(int i=0; i<=n+1; ++i){
            for(int j=n+1; j>i; --j){
                if(i){
                    dp[i][j][k][0] = min(dp[i][j][k][0], dp[i-1][j][k-1][0] + d(i, i-1));
                    dp[i][j][k][0] = min(dp[i][j][k][0], dp[i-1][j][k-1][1] + d(i, j));
                    if(dp[i][j][k][0]<=t[i]) ans = k;
                    else dp[i][j][k][0] = 1e10;
                    dp[i][j][k][0] = min(dp[i][j][k][0], dp[i-1][j][k][0] + d(i, i-1));
                    dp[i][j][k][0] = min(dp[i][j][k][0], dp[i-1][j][k][1] + d(i, j));
                }
                if(j<=n){
                    dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j+1][k-1][1] + d(j+1, j));
                    dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j+1][k-1][0] + d(i, j));
                    if(dp[i][j][k][1]<=t[j]) ans = k;
                    else dp[i][j][k][1] = 1e10;
                    dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j+1][k][1] + d(j+1, j));
                    dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j+1][k][0] + d(i, j));
                }
            }
        }
    }
    cout << ans nl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -