# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
220349 | 2020-04-07T18:09:40 Z | DodgeBallMan | Semiexpress (JOI17_semiexpress) | C++14 | 5 ms | 512 KB |
#include <bits/stdc++.h> using namespace std; const int N = 3e3+5; struct item { long long cnt, idx; int pos; item( long long cnt, long long idx, int pos ) : cnt( cnt ), idx( idx ), pos( pos ) {} friend bool operator<( const item &a, const item &b ) { return a.cnt < b.cnt; } }; priority_queue<item> q; int n, m, k; long long a, b, c, t, ans; long long st[N], dist[N]; long long get_cnt( int i, long long l, long long r ) { long long ti = ( l - st[i] ) * c + dist[i]; if( ti > t ) return 0; return min( ( t - ti ) / a + 1, r - l + 1 ); } int main() { scanf("%d %d %d",&n,&m,&k); scanf("%lld %lld %lld %lld",&a,&b,&c,&t); for( int i = 1 ; i <= m ; i++ ) { scanf("%lld",&st[i]); if( i > 1 ) dist[i] = b*( st[i] - st[i-1] ) + dist[i-1]; } for( int i = 1 ; i < m ; i++ ) if( dist[i] <= t ) { if( dist[i] + ( st[i+1] - st[i] - 1 ) * a <= t ) { ans += st[i+1] - st[i]; continue ; } long long add = ( t - dist[i] ) / a + 1; ans += add; q.emplace( get_cnt( i, st[i] + add, st[i+1] - 1 ), st[i] + add, i ); } k -= m; for( int i = 1 ; i <= k ; i++ ) if( !q.empty() ) { item now = q.top(); q.pop(); ans += now.cnt; long long pos = now.idx + now.cnt; if( pos >= st[now.pos + 1] ) continue; q.emplace( get_cnt( now.pos, pos, st[now.pos + 1] - 1), pos, now.pos ); } if( dist[m] < t ) ans++; printf("%lld\n", ans-1); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 256 KB | Output is correct |
5 | Correct | 4 ms | 256 KB | Output is correct |
6 | Correct | 5 ms | 256 KB | Output is correct |
7 | Correct | 5 ms | 256 KB | Output is correct |
8 | Correct | 4 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 256 KB | Output is correct |
5 | Correct | 4 ms | 256 KB | Output is correct |
6 | Correct | 5 ms | 256 KB | Output is correct |
7 | Correct | 5 ms | 256 KB | Output is correct |
8 | Correct | 4 ms | 256 KB | Output is correct |
9 | Correct | 5 ms | 256 KB | Output is correct |
10 | Correct | 5 ms | 256 KB | Output is correct |
11 | Correct | 5 ms | 256 KB | Output is correct |
12 | Correct | 5 ms | 384 KB | Output is correct |
13 | Correct | 4 ms | 256 KB | Output is correct |
14 | Correct | 4 ms | 256 KB | Output is correct |
15 | Correct | 5 ms | 384 KB | Output is correct |
16 | Correct | 5 ms | 256 KB | Output is correct |
17 | Correct | 5 ms | 384 KB | Output is correct |
18 | Correct | 5 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 256 KB | Output is correct |
5 | Correct | 4 ms | 256 KB | Output is correct |
6 | Correct | 5 ms | 256 KB | Output is correct |
7 | Correct | 5 ms | 256 KB | Output is correct |
8 | Correct | 4 ms | 256 KB | Output is correct |
9 | Correct | 5 ms | 256 KB | Output is correct |
10 | Correct | 5 ms | 256 KB | Output is correct |
11 | Correct | 5 ms | 256 KB | Output is correct |
12 | Correct | 5 ms | 384 KB | Output is correct |
13 | Correct | 4 ms | 256 KB | Output is correct |
14 | Correct | 4 ms | 256 KB | Output is correct |
15 | Correct | 5 ms | 384 KB | Output is correct |
16 | Correct | 5 ms | 256 KB | Output is correct |
17 | Correct | 5 ms | 384 KB | Output is correct |
18 | Correct | 5 ms | 256 KB | Output is correct |
19 | Correct | 5 ms | 384 KB | Output is correct |
20 | Correct | 5 ms | 384 KB | Output is correct |
21 | Correct | 5 ms | 384 KB | Output is correct |
22 | Correct | 5 ms | 384 KB | Output is correct |
23 | Correct | 5 ms | 512 KB | Output is correct |
24 | Correct | 5 ms | 384 KB | Output is correct |
25 | Correct | 5 ms | 384 KB | Output is correct |
26 | Correct | 5 ms | 384 KB | Output is correct |
27 | Correct | 5 ms | 384 KB | Output is correct |
28 | Correct | 5 ms | 384 KB | Output is correct |
29 | Correct | 5 ms | 384 KB | Output is correct |
30 | Correct | 5 ms | 384 KB | Output is correct |