Submission #1031322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031322		lovrot	Long Distance Coach (JOI17_coach)	C++17	100 / 100	147 ms	21216 KiB

coach

#include <cstdio> 
#include <stack>
#include <algorithm>
#include <cstring>
#include <vector> 

using namespace std; 

typedef __int128 hl;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct point { 
	ll x, y;
	point() {}
	point(ll x, ll y) : x(x), y(y) {}
	hl operator * (const point &p) { return (hl) x * (hl) p.x + (hl) y * (hl) p.y; }
};

bool ccw(point a, point b, point c) { // return 1 ako je ccw ili kolinearno
	return ((hl) b.x - (hl) a.x) * ((hl) c.y - (hl) a.y) - ((hl) b.y - (hl) a.y) * ((hl) c.x - (hl) a.x) >= 0;
}

const int N = 2e5 + 10;

int n, m, ind[N];
ll w, t, prf[N], d[N], c[N];
vector<ll> s;

ll jmp[N];
vector<point> ch;
stack<int> stck;

hl dp[N];

int main() { 
	memset(jmp, -1, sizeof(jmp));

	ll X; scanf("%lld%d%d%lld%lld", &X, &n, &m, &w, &t);
	s.push_back(0ll);
	s.push_back(X);
	for(int i = 0; i < n; ++i) { 
		ll x; scanf("%lld", &x);
		s.push_back(x);
	}
	sort(s.begin(), s.end());
	n += 2;
	
	for(int i = 1; i <= m; ++i) { 	
		scanf("%lld%lld", d + i, c + i);
		ind[i] = i;
	}

	sort(ind + 1, ind + m + 1, [](int a, int b) { return d[a] < d[b]; });
	for(int i = 1; i <= m; ++i) { 
		prf[i] = prf[i - 1] + c[ind[i]];
//		printf("%lld\n", prf[i]);
	}

	for(int i = 1; i < n; ++i) { 
		ll k = s[i] / t, r = s[i] % t;
		int lo = 0, hi = m + 1;
		for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
			if(d[ind[mi]] < r) { lo = mi; }
			else { hi = mi; }
		}
		
		if(lo && jmp[lo] == -1 && s[i] / t * t + d[ind[lo]] > s[i - 1]) { 
			jmp[lo] = k;
//			printf("%d %lld\n", lo, k);
		}
	}
	
	for(int i = 0; i <= m; ++i) {
		dp[i] = ((X - d[ind[i]]) / t + 1ll) * w + (i ? dp[i - 1] : 0);

		if(i) { 
			point p = point(-w * i, dp[i - 1] - prf[i - 1]);
			for(; ch.size() >= 2 && !ccw(p, ch.back(), ch.end()[-2]); ch.pop_back()) { /*printf("- %d\n", stck.top()); */ }
			ch.push_back(p);
			stck.push(i);
//			printf("+ %d (%lld %lld)\n", i, ch.back().x, ch.back().y);
		}

		if(jmp[i] != -1) { 
			point q = point(jmp[i], 1);
			hl plus = (hl) prf[i] + (hl) jmp[i] * (hl) w * (hl) (i + 1);
//			printf("%lld = %lld + %lld * %lld * %lld\n", (ll) plus, (ll) prf[i], (ll) jmp[i], (ll) w, (ll) i + 1);

			int lo = -1, hi = (int) ch.size() - 1;
			for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
				if(q * ch[mi] > q * ch[mi + 1]) { lo = mi; }
				else { hi = mi; }
			}

			if(hi >= 0) { 
				dp[i] = min(dp[i], q * ch[hi] + plus); 
//				printf("j %d %d | %lld %lld %lld %lld %lld\n", i, hi, q.x, q.y, (ll) plus, ch[hi].x, ch[hi].y);
			}
		}

//		printf("%d: %lld %lld\n\n", i, (ll) dp[i], jmp[i]);
	}

	printf("%lld\n", (ll) dp[m]);
	return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:40:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  ll X; scanf("%lld%d%d%lld%lld", &X, &n, &m, &w, &t);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   ll x; scanf("%lld", &x);
      |         ~~~~~^~~~~~~~~~~~
coach.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%lld%lld", d + i, c + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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