oj.uz

Submission #658800

# Submission time Handle Problem Language Result Execution time Memory
658800 2022-11-15T01:31:41 Z rsjw Long Distance Coach (JOI17_coach) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200110;
int s[N],f[N];
struct passenger {
	int d,c;
	bool operator < (const passenger &ri) const {
		return d<ri.d;
	}
} A[N];
int x,n,m,w,t;
bool cmp(int a,int b) {
	return a%t<b%t;
}
#define K(p) (-p*w)
#define B(p) (f[p]-A[p].c)
#define E(p,x) (K(p)*(x)+B(p))
#define itsec(k1,k2) (double)(B(k2)-B(k1))/(K(k1)-K(k2))
int h=1,top=1;//stack in fact 
int q[N];
int getmin(int x) {
	int l=1,r=top,mid;
	while(l<=r) {
		mid=(l+r)/2;
		if(itsec(mid,mid+1)<=x) {
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	return l-1;
}
signed main() {
	int i,j=1,Mn;
	freopen("1.in","r",stdin);
	cin>>x>>n>>m>>w>>t;
	for(i=1; i<=n; i++) cin>>s[i];
	for(i=1; i<=m; i++) cin>>A[i].d>>A[i].c;
	A[m+1].d=t,f[0]=0,s[++n]=x;
	sort(s+1,s+n+1,cmp),sort(A+1,A+m+1);
	for(i=1; i<=m; i++) A[i].c+=A[i-1].c;
	while(s[j]%t<=A[1].d&&j<=n) j++;
	for(i=1; i<=m; i++) {
		for(Mn=1e16; j<=n&&s[j]%t<=A[i+1].d; j++) Mn=min(Mn,s[j]/t);
		f[i]=f[i-1]+((x-A[i].d)/t+1)*w;
		if(Mn!=1e16) {
			int ans=1e16;
			for(int k=0; k<i; k++) ans=min(ans,E(k,Mn));
			assert(ans==E(getmin(Mn),Mn));
			
			f[i]=min(ans+A[i].c+i*w*Mn,f[i]);
			while(top-h>=2&&itsec(top-1,top-2)>=itsec(i,top-1)) top--;
			q[top++]=i;
		}
	}
	cout<<f[m]+(x/t+1)*w<<endl;
	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:36:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  freopen("1.in","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -