제출 #1341884

#제출 시각아이디문제언어결과실행 시간메모리
1341884cansu_mutluCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
224 ms131728 KiB
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,l;
    cin >> n>>l;
    vector<vector<vector<int>>> a(n+2,vector<vector<int>>(n+2,vector<int>(n+1,1e18))),b(n+2,vector<vector<int>>(n+2,vector<int>(n+1,1e18)));
    a[0][n+1][0] = b[0][n+1][0] = 0;
    vector<int> x(n+2,0),tim(n+2,-1);
    x[n+1] = l;
    for(int i=1;i<=n;i++) cin >> x[i];
    for(int i=1;i<=n;i++) cin >> tim[i];
    int ans = 0;
    for(int say = 0;say<=n;say++)
    {
        for(int i =0;i<=n+1;i++)
        {
            for(int j = n+1;j>=0;j--)
            {
                if(i>=j) continue;
                if(i>0)
                {
                     a[i][j][say] = min(a[i][j][say],a[i-1][j][say]+x[i]-x[i-1]);
                      a[i][j][say] = min(a[i][j][say],b[i-1][j][say]+x[i]+l-x[j]);
                }
                if(j<=n)
                {
                    b[i][j][say] = min(b[i][j][say],b[i][j+1][say]+x[j+1]-x[j]);
                    b[i][j][say] = min(b[i][j][say],a[i][j+1][say]+l-x[j]+x[i]);
                }
                if(say==0) continue;
                int cur;
                if(i>0)
                {
                    cur = a[i-1][j][say-1]+x[i]-x[i-1];
                if(cur<=tim[i])
                {
                    a[i][j][say] = min(a[i][j][say],cur);
                }
                cur = b[i-1][j][say-1]+x[i]+l-x[j];
                if(cur<=tim[i])
                {
                    a[i][j][say] = min(a[i][j][say],cur);
                }
                }
                if(j<=n)
                {
                    cur = b[i][j+1][say-1]+x[j+1]-x[j];
                if(cur<=tim[j])
                {
                    b[i][j][say] = min(b[i][j][say],cur);
                }
                cur = a[i][j+1][say-1]+x[i]+l-x[j];
                if(cur<=tim[j])
                {
                    b[i][j][say] = min(b[i][j][say],cur );
                }
                }
                if(a[i][j][say]<1e18 || b[i][j][say]<1e18)
                {
                     ans = max(ans,say);
                    // cout << ans << " "<<i << " "<< j<< " "<<a[i][j][say] << " "<< b[i][j][say] << endl;
                }
                //cout << i << " "<< j << " "<< say << " " << a[i][j][say] << " "<< b[i][j][say] << endl;
            }
        }
    }
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...