oj.uz

답안 #967379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967379 2024-04-22T03:44:39 Z 12345678 Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 1 ms 4444 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=205;

ll n, d, a[nx], t[nx], dp[nx][nx][nx][2], res;

ll dist(ll a, ll b)
{
    if (a>b) swap(a, b);
    return min(b-a, a+d-b);
}

ll nxt(ll x)
{
    if (x+1>n) return x+1-n;
    return x+1;
}

ll prv(ll x)
{
    if (x-1>0) return x-1;
    return x-1+n;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>d;
    for (int i=1; i<=n; i++) cin>>a[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=1; k<=n; k++) dp[i][j][k][0]=dp[i][j][k][1]=1e18;
    for (int i=1; i<=n; i++) dp[i][i][0][0]=dp[i][i][0][1]=dist(0, a[i]);
    for (int i=1; i<=n; i++) if (dist(0, a[i])<=t[i]) dp[i][i][1][0]=dp[i][i][1][1]=dist(0, a[i]);
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            ll l=j, r=j+i;
            if (r>n) r-=n;
            dp[l][r][0][0]=dist(0, a[l]);
            dp[l][r][0][1]=dist(0, a[r]);
            for (int k=1; k<=i+1; k++)
            {
                dp[l][r][k][0]=min({dp[l][r][k][0], dp[nxt(l)][r][k][0]+dist(a[l], a[nxt(l)]), dp[nxt(l)][r][k][1]+dist(a[l], a[r])});
                if (dp[nxt(l)][r][k-1][0]+dist(a[nxt(l)], a[l])<=t[l]) dp[l][r][k][0]=min(dp[l][r][k][0], dp[nxt(l)][r][k-1][0]+dist(a[nxt(l)], a[l]));
                if (dp[nxt(l)][r][k-1][1]+dist(a[l], a[r])<=t[l]) dp[l][r][k][0]=min(dp[l][r][k][0], dp[nxt(l)][r][k-1][1]+dist(a[l], a[r]));
                dp[l][r][k][1]=min({dp[l][r][k][1], dp[l][prv(r)][k][0]+dist(a[l], a[r]), dp[l][prv(r)][k][1]+dist(a[prv(r)], a[r])});
                if (dp[l][prv(r)][k-1][0]+dist(a[l], a[r])<=t[r]) dp[l][r][k][1]=min(dp[l][r][k][1], dp[l][prv(r)][k-1][0]+dist(a[l], a[r]));
                if (dp[l][prv(r)][k-1][1]+dist(a[prv(r)], a[r])<=t[r]) dp[l][r][k][1]=min(dp[l][r][k][1], dp[l][prv(r)][k-1][1]+dist(a[prv(r)], a[r]));
                //cout<<"debug "<<l<<' '<<r<<' '<<k<<' '<<dp[l][r][k][0]<<' '<<dp[l][r][k][1]<<'\n';
            }
        }
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=n; k++) for (int t=0; t<2; t++) if (dp[i][j][k][t]<1e18) res=max(res, (ll)k);
    cout<<res;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -