답안 #285729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285729	2020-08-29T14:04:46 Z	TadijaSebez	Long Distance Coach (JOI17_coach)	C++11	16 / 100	1 ms	384 KB

coach

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll lim=1e12;
const ll inf=1e18;
struct Line{
	ll k,n;
	Line(){}
	Line(ll a,ll b):k(a),n(b){}
	ll Get(ll x){return x*k+n;}
};
const int N=200050;
int ls[N],rs[N],tsz,root;
Line line[N];
void AddLine(int&c,ll ss,ll se,Line k){
	if(!c){c=++tsz;line[c]=k;return;}
	ll A=line[c].Get(ss),B=k.Get(ss),C=line[c].Get(se),D=k.Get(se);
	if(A<=B&&C<=D)return;
	if(A>=B&&C>=D){line[c]=k;return;}
	ll mid=ss+se>>1;
	if(A>B)swap(line[c],k);
	if(line[c].Get(mid)<=k.Get(mid))AddLine(rs[c],mid+1,se,k);
	else swap(k,line[c]),AddLine(ls[c],ss,mid,k);
}
ll Get(int c,ll ss,ll se,ll qi){
	if(!c)return inf;
	ll ans=line[c].Get(qi);
	if(ss==se)return ans;
	ll mid=ss+se>>1;
	if(qi<=mid)return min(ans,Get(ls[c],ss,mid,qi));
	else return min(ans,Get(rs[c],mid+1,se,qi));
}
ll s[N],mn[N],dp[N],pre[N];
pair<ll,ll> a[N];
int main(){
	int n,m;ll x,t,w;
	scanf("%lld %i %i %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<=m;i++)scanf("%lld %lld",&a[i].first,&a[i].second),mn[i]=inf;
	sort(a+1,a+1+m);
	for(int i=1;i<=m;i++)pre[i]=pre[i-1]+a[i].second;
	for(int i=1;i<=n;i++){
		int j=upper_bound(a+1,a+1+m,(pair<ll,ll>){s[i]%t,inf})-a-1;
		mn[j]=min(mn[j],s[i]/t);
	}
	dp[0]=(x/t+1)*w;
	AddLine(root,0,lim,Line(0,dp[0]));
	for(int i=1;i<=m;i++){
		dp[i]=dp[i-1]+((x-a[i].first)/t+1)*w;
		if(mn[i]!=inf)dp[i]=min(dp[i],Get(root,0,lim,mn[i])+mn[i]*i*w+pre[i]);
		AddLine(root,0,lim,Line(-i*w,dp[i]-pre[i]));
	}
	printf("%lld\n",dp[m]);
	return 0;
}

Compilation message

coach.cpp: In function 'void AddLine(int&, long long int, long long int, Line)':
coach.cpp:20:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  ll mid=ss+se>>1;
      |         ~~^~~
coach.cpp: In function 'long long int Get(int, long long int, long long int, long long int)':
coach.cpp:29:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  ll mid=ss+se>>1;
      |         ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:38:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   38 |  for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
      |  ^~~
coach.cpp:38:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   38 |  for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
      |                                           ^
coach.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%lld %i %i %lld %lld",&x,&n,&m,&w,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:38:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
      |                       ~~~~~^~~~~~~~~~~~~~
coach.cpp:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  for(int i=1;i<=m;i++)scanf("%lld %lld",&a[i].first,&a[i].second),mn[i]=inf;
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	0 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	0 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	1 ms	384 KB	Output is correct
30	Correct	1 ms	384 KB	Output is correct
31	Incorrect	1 ms	384 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	0 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	1 ms	384 KB	Output is correct
30	Correct	1 ms	384 KB	Output is correct
31	Incorrect	1 ms	384 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #4
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	0 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	0 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	0 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	1 ms	384 KB	Output is correct
30	Correct	1 ms	384 KB	Output is correct
31	Incorrect	1 ms	384 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #285729

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 0 / 30.0

Subtask #3 0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
0 / 30.0

Subtask #3
0 / 25.0

Subtask #4
0 / 29.0