Submission #988513

#	Time	Username	Problem	Language	Result	Execution time	Memory
988513		DON_F	Tower (JOI24_tower)	C++14	5 / 100	74 ms	18040 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve(){
  	int n, q;
  	ll d, a, b;
  	cin >> n >> q >> d >> a >> b;
  	// normal jump a second / D steps take B
  	const int N = 1e6 + 6;
  	vector <int> p(N);
  	for (int i = 0; i < n; ++i){
		int l, r;
		cin >> l >> r;
		p[l]++;
		p[r + 1]--;
	}
	int cur = 0;
	for (int i = 0; i < N; ++i){
		cur += p[i];
		p[i] = cur;
	}
	const ll big = 1e18;
	vector <ll> dp(N, big);
	dp[0] = 0;
	for (int i = 1; i < N; ++i){
		if (p[i] != 0){
			continue;
		}
		dp[i] = min(dp[i], dp[i - 1] + a);
		if (i - d >= 0){
			dp[i] = min(dp[i], dp[i - d] + b);
		}
	}
	for (int i = 0; i < q; ++i){
		int x;
		cin >> x;
		cout << (dp[x] == big ? -1 : dp[x]) << "\n";
	}
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int T = 1;
  //cin >> T;
  while (T--){
	 solve();  
  }
}

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