oj.uz

Submission #81259

# Submission time Handle Problem Language Result Execution time Memory
81259 2018-10-24T09:25:24 Z farukkastamonuda Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 876 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 300005
#define mp make_pair
#define pb push_back
#define pi pair<lo int, int>
using namespace std;
int n, m, k, s[li], mx;
lo int a, b, c, t, rem[li], ans;
priority_queue< pair<lo int, int> > q;
lo int calc(int ind){
	lo int tut = (t - (s[ind] - 1) * b - (s[ind + 1] - s[ind] - 1 - rem[ind]) * c);
	if(tut < c) return 0;
	return min(rem[ind], (tut - c) / a + 1);
}
int main(){
	scanf("%d %d %d %lld %lld %lld %lld", &n, &m, &k, &a, &b, &c, &t);
	for(int i = 1; i <= m ; i ++){
		scanf("%d", &s[i]);
	}
	for(int i = 1; i < m ; i ++){
		if((s[i] - s[1]) * b > t) break; 
		mx = i;
	}
	for(int i = 1; i <= mx ; i ++){
		rem[i] = max(0ll, (s[i + 1] - s[i] - 1) - (t - (s[i] - 1) * b) / a);
		q.push(mp(calc(i), i));
	}
	k -= m;
	while(k --){
		int temp = q.top().fi;
		int ind = q.top().se;
		q.pop();
		rem[ind] -= temp;
		q.push(mp(calc(ind), ind));
	}
	for(int i = 1; i <= mx; i ++){
		ans += s[i + 1] - s[i] - rem[i];
	}
	if((s[m] - 1) * b <= t) ans ++;
	printf("%lld\n", ans - 1);
	return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %lld %lld %lld %lld", &n, &m, &k, &a, &b, &c, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 540 KB Output is correct
11 Correct 2 ms 544 KB Output is correct
12 Correct 2 ms 548 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 2 ms 740 KB Output is correct
15 Correct 2 ms 740 KB Output is correct
16 Correct 2 ms 740 KB Output is correct
17 Correct 2 ms 740 KB Output is correct
18 Correct 2 ms 740 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 540 KB Output is correct
11 Correct 2 ms 544 KB Output is correct
12 Correct 2 ms 548 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 2 ms 740 KB Output is correct
15 Correct 2 ms 740 KB Output is correct
16 Correct 2 ms 740 KB Output is correct
17 Correct 2 ms 740 KB Output is correct
18 Correct 2 ms 740 KB Output is correct
19 Correct 2 ms 740 KB Output is correct
20 Correct 3 ms 808 KB Output is correct
21 Correct 3 ms 808 KB Output is correct
22 Correct 2 ms 808 KB Output is correct
23 Correct 2 ms 808 KB Output is correct
24 Correct 2 ms 808 KB Output is correct
25 Correct 2 ms 808 KB Output is correct
26 Correct 3 ms 816 KB Output is correct
27 Correct 2 ms 836 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 2 ms 868 KB Output is correct
30 Correct 2 ms 876 KB Output is correct