oj.uz

Submission #83477

# Submission time Handle Problem Language Result Execution time Memory
83477 2018-11-08T09:09:30 Z ekrem Semiexpress (JOI17_semiexpress) C++
100 / 100
 3 ms 1024 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;

ll n, m, k, A, B, C, ans = 0, a[N];
ll t;
priority_queue < pair < ii , ii > > q;

void ekle(ll bas, ll son, ll kal){
	if(bas > son or kal < 0)
		return;
	ll bul = 0;
	ll git = kal / A;
	if(bas + git <= son)
		bul = git + 1;
	else
		bul = son - bas + 1;
	// cout << bas << " " << son << " -> " << bul << " , " << kal << endl;
	q.push(mp(mp(bul, kal), mp(bas, son)));
}

void sil(){
	pair < ii , ii > x = q.top();
	ans += x.st.st;
	q.pop();
	ll bas = x.nd.st;
	ll son = x.nd.nd;
	ll kal = x.st.nd;

	ll git = kal / A;
	// cout << x.st.st << " " << bas << " " << son << " " << kal << " " << git << endl;
	ekle(bas + git + 1, son, kal - (git + 1)*C);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld %lld %lld",&n ,&m ,&k); k -= m;
	scanf("%lld %lld %lld",&A ,&B ,&C);
	scanf("%lld",&t);
	for(ll i = 1; i <= m; i++)
		scanf("%lld",a + i);
	a[m + 1] = n + 1;
	for(ll i = 1; i <= m; i++){
		ll kal = t - (a[i] - 1)*B;
		if(kal < 0)
			break;
		ll git = kal / A;
		// cout << a[i] << " " << kal << " " << git << " " << a[i + 1] << endl;
		if(a[i] + git < a[i + 1]){
			ans += git + 1;
			// cout << "AMK = " << ans << endl;
			ekle(a[i] + git + 1, a[i + 1] - 1, kal - (git + 1)*C );
		}
		else
			ans += a[i + 1] - a[i];
	}
	// cout << "ans = " << ans << endl;
	// cout << endl << endl;
	while(!q.empty() and k--){
		sil();
	}
	printf("%lld\n", ans - 1);
	return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n ,&m ,&k); k -= m;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&A ,&B ,&C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&t);
  ~~~~~^~~~~~~~~~~
semiexpress.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",a + 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 384 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 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 384 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 2 ms 676 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct
13 Correct 2 ms 676 KB Output is correct
14 Correct 2 ms 676 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 676 KB Output is correct
17 Correct 2 ms 680 KB Output is correct
18 Correct 2 ms 684 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 384 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 2 ms 676 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct
13 Correct 2 ms 676 KB Output is correct
14 Correct 2 ms 676 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 676 KB Output is correct
17 Correct 2 ms 680 KB Output is correct
18 Correct 2 ms 684 KB Output is correct
19 Correct 2 ms 688 KB Output is correct
20 Correct 2 ms 704 KB Output is correct
21 Correct 2 ms 736 KB Output is correct
22 Correct 2 ms 772 KB Output is correct
23 Correct 3 ms 916 KB Output is correct
24 Correct 2 ms 948 KB Output is correct
25 Correct 2 ms 948 KB Output is correct
26 Correct 2 ms 948 KB Output is correct
27 Correct 2 ms 1008 KB Output is correct
28 Correct 2 ms 1024 KB Output is correct
29 Correct 2 ms 1024 KB Output is correct
30 Correct 2 ms 1024 KB Output is correct