Submission #332857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332857	2020-12-03T19:03:25 Z	limabeans	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	15 ms	4600 KB

semiexpress

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;






ll n,m,k;
ll a,b,c;
ll t;
vector<ll> s;




vector<ll> w;
ll solve(ll l, ll r) {
    ll res = 0;
    ll cnt = 0;
    ll at = l;
    ll time = b*l;
    
    while (at<r && cnt<=k-m) {
	if (t-time<0) break;
	
	ll dist = (t-time)/a;
	ll to = min(r,at+dist+1);
	
	if (l==at) {
	    res = to-at;
	} else {
	    w.push_back(to-at);
	}

	cnt++;
	time += (to-at)*c;
	at = to;
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>t;
    s.resize(m);
    for (int i=0; i<m; i++) {
	cin>>s[i];
	--s[i];
    }

    ll res = 0;
    if (b*s[m-1] <= t) res=1;

    for (int i=0; i+1<m; i++) {
	res += solve(s[i],s[i+1]);
    }

    sort(w.rbegin(), w.rend());
    
    for (int i=0; i<k-m && i<(int)w.size(); i++) {
	res += w[i];
    }

    res--; //except station 1
    cout<<res<<endl;
    
    return 0;
}

Subtask #1

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	376 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	376 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	0 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	236 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct

Subtask #3

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	376 KB	Output is correct
9	Correct	0 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	0 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	236 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	15 ms	4600 KB	Output is correct
24	Correct	1 ms	492 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Correct	1 ms	364 KB	Output is correct
29	Correct	11 ms	4580 KB	Output is correct
30	Correct	7 ms	2536 KB	Output is correct