Submission #906208

#	Time	Username	Problem	Language	Result	Execution time	Memory
906208		HorizonWest	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	89 ms	134228 KiB

ho_t3

#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e13 + 7, Inf = 1e15 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

int dp[205][205][205][2];

void solve()
{
    int n, l; cin >> n >> l; 
    vector <int> v(n+2), t(n+2);
    _for(i, n) cin >> v[i+1]; 
    _for(i, n) cin >> t[i+1]; 

    int ans = 0; 

    _for(i, n+2) _for(j, n+2) _for(k, n+2){
        dp[i][j][k][0] = dp[i][j][k][1] = Inf; 
    }

    dp[0][n+1][0][0] = dp[0][n+1][0][1] = 0; v[n+1] = l; 
    
    for(int i = 0; i <= n; i++)
    {//cerr << endl << "I -> " << i << endl;
        for(int j = n+1; j > i+1; j--)
        {
            for(int k = 0; k <= n; k++)
            {
                //cerr << (dp[i][j][k][1] > Max ? -1 : dp[i][j][k][1]) << " ";

                int a = min(dp[i][j][k][0] + min(abs(v[i+1] - v[i]), v[i] + (l - v[i+1])), 
                            dp[i][j][k][1] + min(abs(v[i+1] - v[j]), v[i+1] + (l - v[j])));
                
                int b = min(dp[i][j][k][1] + min(abs(v[j] - v[j-1]), v[j-1] + (l - v[j])),
                            dp[i][j][k][0] + min(abs(v[j-1] - v[i]), v[i] + (l - v[j-1]))); 

               /* if(b < 0)
                {
                    cout << "WA: " << v[j-1] - v[j] << endl;
                }*/

                dp[i+1][j][k + (a <= t[i+1])][0] = min(dp[i+1][j][k + (a <= t[i+1])][0], a); 
                dp[i][j-1][k + (b <= t[j-1])][1] = min(dp[i][j-1][k + (b <= t[j-1])][1], b); 
            }//cerr << endl;
        }
         
    }

    _for(i, n+1) _for(j, n+1) _for(k, n+1)
    { 
        //if(dp[i][j][k] < Inf) cerr << dp[i][j][k]<< endl;
        if(dp[i][j][k][0] < Max) ans = max(ans, k); 
        if(dp[i][j][k][1] < Max) ans = max(ans, k); 
    }

    cout << ans << endl; 
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75