Submission #245820

#	Time	Username	Problem	Language	Result	Execution time	Memory
245820		Atill83	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	202 ms	263672 KiB

ho_t3

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 405;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, l;
pii stm[MAXN];
int x[MAXN], t[MAXN];
int dp[MAXN][MAXN][205][2];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>l;

    for(int i = 0; i < n; i++) {
        cin>>x[2*i];
        x[2*i + 1] = x[2*i] - l;
    }

    stm[2*n] = {0, 0};
    for(int i = 0; i < n; i++){
        cin>>t[i];
        stm[2*i] = {x[2*i], t[i]};
        stm[2*i + 1] = {x[2*i + 1], t[i]};
    }

    sort(stm, stm + 2*n + 1);
    int idx = 0;
    for(int i = 0; i <= 2*n; i++){
        if(stm[i] == make_pair(0, 0))
            idx = i;
        //cout<<stm[i].ff<<" "<<stm[i].ss<<endl;
    }
    memset(dp, 0x7f, sizeof(dp));
    dp[idx][idx][0][0] = dp[idx][idx][0][1] = 0;
    int ans = 0;
    for(int i = 2; i <= n + 1; i++){
        for(int j = idx - i + 1; j <= idx; j++){
            dp[j][j + i - 1][0][0] = 2*stm[j + i - 1].ff - stm[j].ff;
            dp[j][j + i - 1][0][1] = -2*stm[j].ff + stm[j + i - 1].ff;
            for(int l = 1; l <= i; l++){
                int &r = dp[j][j + i - 1][l][0];
                r = min(r, dp[j + 1][j + i - 1][l][0] + stm[j + 1].ff - stm[j].ff);
                r = min(r, dp[j + 1][j + i - 1][l][1] + stm[j + i - 1].ff - stm[j].ff);
                if(stm[j + 1].ff - stm[j].ff + dp[j + 1][j + i - 1][l - 1][0] <= stm[j].ss){
                    r = min(r, stm[j + 1].ff - stm[j].ff + dp[j + 1][j + i - 1][l - 1][0]);
                }
                if(dp[j + 1][j + i - 1][l - 1][1] + stm[j + i - 1].ff - stm[j].ff <= stm[j].ss){
                    r = min(r, dp[j + 1][j + i - 1][l - 1][1] + stm[j + i - 1].ff - stm[j].ff);
                }

                int &rr = dp[j][j + i - 1][l][1];

                rr = min(rr, dp[j][j + i - 2][l][0] + stm[j + i - 1].ff - stm[j].ff);
                rr = min(rr, dp[j][j + i - 2][l][1] + stm[j + i - 1].ff - stm[j + i - 2].ff);

                if(dp[j][j + i - 2][l - 1][0] + stm[j + i - 1].ff - stm[j].ff <= stm[i + j - 1].ss){
                    rr = min(rr, dp[j][j + i - 2][l - 1][0] + stm[j + i - 1].ff - stm[j].ff);
                }

                if(dp[j][j + i - 2][l - 1][1] + stm[j + i - 1].ff - stm[j + i - 2].ff <= stm[i + j - 1].ss){
                    rr = min(rr, dp[j][j + i - 2][l - 1][1] + stm[j + i - 1].ff - stm[j + i - 2].ff);
                }

                if(r <= 2e9 || rr <= 2e9){
                    ans = max(ans, l);
                }
            }
        }
    }
    ans = min((int)n, ans);
    //cout<<dp[4][5][1][0]<<" "<<dp[4][5][1][1]<<endl;

    cout<<ans<<endl;

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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