Submission #1102047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102047		Pacybwoah	Tower (JOI24_tower)	C++17	5 / 100	91 ms	16328 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cassert>
#include<set>
using namespace std;
typedef long long ll;
ll inf = 8e18;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    ll d, a, b;
    cin >> d >> a >> b;
    vector<pair<int, int>> vec;
    for(int i = 0; i < n; i++){
        ll l, r;
        cin >> l >> r;
        vec.emplace_back(l, r);
        assert(r <= 1000000);
    }
    vector<ll> dp(1000001, inf);
    dp[0] = 0;
    for(auto &[l, r]: vec){
        for(int i = l; i <= r; i++) dp[i] = -1;
    }
    for(int i = 1; i <= 1000000; i++){
        if(dp[i] == -1) continue;
        if(dp[i - 1] != -1) dp[i] = min(dp[i], dp[i - 1] + a);
        if(i >= d && dp[i - d] != -1) dp[i] = min(dp[i], dp[i - d] + b);
    }
    for(int i = 0; i < q; i++){
        int x;
        cin >> x;
        if(dp[x] == inf || dp[x] == -1) cout << "-1\n";
        else cout << dp[x] << "\n";
    }
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run tower.cpp

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