Submission #113105

#	Time	Username	Problem	Language	Result	Execution time	Memory
113105		Bruteforceman	Long Distance Coach (JOI17_coach)	C++11	0 / 100	2 ms	384 KiB

coach

#include "bits/stdc++.h"
using namespace std;
long long s[200010];
long long d[200010];
long long c[200010];
int N, M;
long long X, W, T;
typedef pair <long long, int> pii;
vector <pii> v;

int pos[200010];
long long dp[200010];

int main(int argc, char const *argv[])
{
	scanf("%lld %d %d %lld %lld", &X, &N, &M, &W, &T);
	for(int i = 1; i <= N; i++) {
		scanf("%lld", &s[i]);
	}
	s[++N] = X;
	for(int i = 1; i <= N; i++) {
		v.push_back(pii(s[i] % T, i));
	}  
	for(int i = 1; i <= M; i++) {
		scanf("%lld %lld", &d[i], &c[i]);
		v.push_back(pii(d[i], -i));
	}
	sort(v.begin(), v.end());

	int now = 0;
	for(auto i : v) {	
		if(i.second > 0) {
			pos[i.second] = now;
		}
		++now;
	}
	long long ans = (X / T) + 1;
	for(int i = 1; i <= M; i++) {
		ans += 1 + ((X - d[i]) / T);
	}
	ans *= W;

	dp[0] = 0;
	for(int i = 1; i < v.size(); i++) {
		if(v[i].second < 0) {
			dp[i] = dp[i - 1];
		} else {
			long long var = s[v[i].second] / T;
			long long cost = 0;
			for(int cur = i; cur >= 0; cur--) {
				if(v[cur].second > 0 && v[cur].second < v[i].second) {
					break;
				}
				if(v[cur].second < 0) {
					int id = -v[cur].second;
					cost += c[id];
					cost -= W * (1 + ((X - d[id]) / T));
					cost += W * var;
				}
				if(cur > 0) {
					dp[i] = min(dp[i], dp[cur - 1] + cost);
				} else {
					dp[i] = min(dp[i], cost);
				}
			}
		}
	}
	ans += dp[v.size() - 1];
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main(int, const char**)':
coach.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < v.size(); i++) {
                 ~~^~~~~~~~~~
coach.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %d %d %lld %lld", &X, &N, &M, &W, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &s[i]);
   ~~~~~^~~~~~~~~~~~~~~
coach.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &d[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29