Submission #319648

#	Time	Username	Problem	Language	Result	Execution time	Memory
319648		arnold518	Long Distance Coach (JOI17_coach)	C++14	100 / 100	573 ms	49872 KiB

coach

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 4e5;
 
ll X, W, T;
int N, M, K;
 
vector<pll> V;
ll SS[MAXN+10];
pll C[MAXN+10];
ll A[MAXN+10];
 
ll dp[MAXN+10];
map<ll, ll> MM;

ll S[MAXN+10], TT[MAXN+10];

struct Line
{
	ll a, b;
};

long double cross(Line p, Line q) { return (long double)(q.b-p.b)/(p.a-q.a); }

struct CHT
{
	vector<Line> S;
	void push(Line p)
	{
		if(!S.empty() && S.back().a==p.a)
		{
			if(S.back().b<=p.b) return;
			S.pop_back();
		}
		while(S.size()>1 && cross(S[S.size()-1], p)>=cross(S[S.size()-2], S[S.size()-1])) S.pop_back();
		S.push_back(p);
	}
	ll query(ll x)
	{
		int lo=0, hi=S.size();
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(cross(S[mid], S[mid-1])>=x) lo=mid;
			else hi=mid;
		}
		return S[lo].a*x+S[lo].b;
	}
}cht;
 
int main()
{
	scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
 
	for(int i=1; i<=N; i++) scanf("%lld", &SS[i]);
	sort(SS+1, SS+N+1, greater<ll>());
 
	{
		ll x, y;
		x=X%T; y=X/T;
		MM[x]=-y;
	}
	for(int i=1; i<=N; i++)
	{
		ll x, y;
		x=SS[i]%T; y=SS[i]/T;
		MM[x]=-y;
	}
 
	for(int i=1; i<=M; i++)
	{
		scanf("%lld%lld", &C[i].first, &C[i].second);
		dp[0]+=C[i].second;
		MM[C[i].first]=C[i].second;
 
		dp[0]+=W*(X/T);
		if(C[i].first<=X%T) dp[0]+=W;
	}
	dp[0]+=W*(X/T+1);
 
	K=MM.size();
	int t=1, P;
	for(auto it : MM)
	{
		if(it.first==X%T) P=t;
		A[t++]=it.second;
	}
 
	for(int i=1; i<=K; i++)
	{
		if(A[i]>0)
		{
			S[i]=S[i-1]+X/T;
			TT[i]=TT[i-1]+1;
			if(i<=P) S[i]++;
		}
		else
		{
			S[i]=S[i-1];
			TT[i]=TT[i-1];
		}
	}

	for(int i=1; i<=K; i++)
	{
		cht.push({TT[i-1], W*S[i-1]+dp[i-1]});
		if(A[i]>0)
		{
			dp[i]=dp[i-1]-A[i];
		}
		else
		{
			dp[i]=cht.query(W*A[i])-W*(A[i]*TT[i]+S[i]);
		}
	}
 
	printf("%lld\n", dp[K]);
}

Compilation message (stderr)

coach.cpp: In member function 'll CHT::query(ll)':
coach.cpp:48:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |    int mid=lo+hi>>1;
      |            ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:60:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  for(int i=1; i<=N; i++) scanf("%lld", &SS[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~
coach.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%lld%lld", &C[i].first, &C[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:100:4: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |    if(i<=P) S[i]++;
      |    ^~

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