oj.uz

Submission #821537

# Submission time Handle Problem Language Result Execution time Memory
821537 2023-08-11T11:19:09 Z AdamGS Long Distance Coach (JOI17_coach) C++17
16 / 100
 193 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct item * pitem;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
struct item {
	pitem l=nullptr, r=nullptr;
	ll a=0, b=INF;
};
ll T[LIM], dp[LIM], kiedy[LIM], pref[LIM], x, n, m, w, t, N=1;
pair<ll,ll>P[LIM];
void upd(pitem v, ll l, ll r, ll a, ll b) {
	if(l==r) {
		if(v->a*l+v->b>a*l+b) {
			v->a=a;
			v->b=b;
			return;
		}
	}
	if(a==0 && b==INF) return;
	ll mid=(l+r)/2;
	if(v->a*mid+v->b>a*mid+b) {
		swap(v->a, a);
		swap(v->b, b);
	}
	if(a<v->a) {
		if(!v->r) v->r=new item();
		upd(v->r, mid+1, r, a, b);
	} else {
		if(!v->l) v->l=new item();
		upd(v->l, l, mid, a, b);
	}
}
ll cnt(pitem v, ll l, ll r, ll x) {
	if(!v) return INF;
	ll ans=v->a*x+v->b, mid=(l+r-1)/2;
	if(l==r) return ans;
	if(x<=mid) ans=min(ans, cnt(v->l, l, mid, x));
	else ans=min(ans, cnt(v->r, mid+1, r, x));
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> x >> n >> m >> w >> t;
	rep(i, 40) N*=2;
	rep(i, n) cin >> T[i];
	T[n]=x; ++n;
	rep(i, m) cin >> P[i].st >> P[i].nd;
	sort(T, T+n);
	sort(P, P+m);
	rep(i, m) {
		kiedy[i]=INF;
		pref[i]=P[i].nd;
		if(i) pref[i]+=pref[i-1];
	}
	rep(i, n) {
		ll po=0, ko=m-1;
		while(po<ko) {
			ll sr=(po+ko+1)/2;
			if(P[sr].st>T[i]%t) ko=sr-1; else po=sr;
		}
		if(P[po].st>T[i]%t) continue;
		kiedy[po]=min(kiedy[po], T[i]/t);
	}
	pitem root=new item();
	rep(i, m) {
		ll ile=w*(x/t);
		if(x%t>P[i].st) ile+=w;
		dp[i]=ile;
		if(i) dp[i]+=dp[i-1];
		if(kiedy[i]!=INF) {
			dp[i]=min(dp[i], pref[i]+i*kiedy[i]*w+cnt(root, -N+1, 0, -kiedy[i]));
			dp[i]=min(dp[i], pref[i]+(i+1)*kiedy[i]*w);
		}
		upd(root, -N+1, 0, i*w, dp[i]-pref[i]);
	}
	cout << dp[m-1]+w*(x/t+1) << '\n';
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 280 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 280 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Runtime error 193 ms 262144 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 280 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Runtime error 193 ms 262144 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 280 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Runtime error 193 ms 262144 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -