제출 #1162388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162388		hengliao	Tower (JOI24_tower)	C++20	5 / 100	49 ms	15688 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

const ll mxN=2e5+5;
const ll mxM=1e6+5;
const ll inf=2e18;

ll n, Q, d, a, b;

pll tep[mxN];
ll q[mxN];
ll dp[mxM];
bool good[mxM];

void solve(){
    cin>>n>>Q>>d>>a>>b;
    for(ll i=0;i<mxM;i++){
        good[i]=1;
    }
    for(ll i=0;i<n;i++){
        cin>>tep[i].F>>tep[i].S;
        for(ll j=tep[i].F;j<=tep[i].S;j++){
            good[j]=0;
        }
    }
    for(ll i=0;i<mxM;i++){
        dp[i]=inf;
    }
    if(a*d>=b){
        dp[0]=0;
        for(ll i=1;i<mxM;i++){
            if(!good[i]) continue;
            if(i-d>=0 && dp[i-d]!=inf){
                dp[i]=dp[i-d]+b;
            }
            else if(i-1>=0 && dp[i-1]!=inf){
                dp[i]=dp[i-1]+a;
            }
        }
    }
    else{
        dp[0]=0;
        for(ll i=1;i<mxM;i++){
            if(!good[i]) continue;
            
            if(i-1>=0 && dp[i-1]!=inf){
                dp[i]=dp[i-1]+a;
            }
            else if(i-d>=0 && dp[i-d]!=inf){
                dp[i]=dp[i-d]+b;
            }
        }
    }
    
    for(ll i=0;i<Q;i++){
        cin>>q[i];
        if(dp[q[i]]==inf){
            cout<<-1<<'\n';
        }
        else{
            cout<<dp[q[i]]<<'\n';
        }
    }
    // for(ll i=tep[n-1].F-1;i>=0;i--){
    //     if(!good[i]) continue;
    //     if(i+d<mxM && good2[i+d]){
    //         good2[i]=1;
    //     }
    //     else{
    //         good2[i]=0;
    //     }
    // }
    // memset(ans, -1, sizeof(ans));
    // ans[0]=0;
    // v[0].F=0;
    // v[0].S=tep[0].F-1;
    // for(ll i=0;i<n-1;i++){
    //     v[i+1].F=tep[i].S+1;
    //     v[i+1].S=tep[i+1].F-1;
    // }
    // v[n].F=tep[n-1].S+1;
    // v[n].S=mxM-1;
    // ll lef=v[n].F:
    // ll rig=v[n].S;
    // for(ll i=)
}

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

    solve();

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 38
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32