oj.uz

Submission #123666

# Submission time Handle Problem Language Result Execution time Memory
123666 2019-07-02T02:04:41 Z wilwxk Semiexpress (JOI17_semiexpress) C++14
100 / 100
 2 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=3e4+5;
priority_queue<tuple<ll, ll, ll> > pq;
int n, m, k;
ll x, y, z, q;
ll v[MAXN], custo[MAXN];
int respf;

int main() {
	scanf("%d %d %d", &n, &m, &k);
	scanf("%lld %lld %lld", &x, &y, &z);
	scanf("%lld", &q);
	for(int i=1; i<=m; i++) {
		scanf("%lld", &v[i]);
		custo[i]=(v[i]-1)*y;
		if(custo[i]<=q) respf++;
		if(i!=1) {
			if(custo[i-1]>=q) continue;
			ll posso=(q-custo[i-1])/x;
			ll sobrou=v[i]-v[i-1]-1;
			posso=min(posso, sobrou);
			respf+=posso;
			ll fcusto=custo[i-1]+z*(posso+1);
			ll fposso=(q-fcusto)/x+1;
			fposso=min(fposso, sobrou-posso);
			// printf("%d:: %lld %lld // (%lld %lld %lld) -- respf %d\n", i, posso, sobrou, fposso, fcusto, sobrou-posso, respf);
			if(fposso>0&&fcusto<=q) pq.push({fposso, fcusto, sobrou-posso});
		}
	}

	// printf("tenho %d\n", respf);
	// while(pq.size()) printf("(%lld %lld %lld)\n", get<0>(pq.top()), get<1>(pq.top()), get<2>(pq.top())), pq.pop();

	k-=m;
	while(k--) {
		if(pq.empty()) break;
		ll fposso, fcusto, fsobrou;
		tie(fposso, fcusto, fsobrou)=pq.top(); pq.pop();
		respf+=fposso;
		fsobrou-=fposso;
		fcusto+=fposso*z;
		fposso=(q-fcusto)/x+1;
		fposso=min(fposso, fsobrou);
		// printf("add %lld %lld %lld\n", fposso, fcusto, fsobrou);
		if(fposso>0&&fcusto<=q) pq.push({fposso, fcusto, fsobrou});
	}

	printf("%d\n", respf-1);
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld", &x, &y, &z);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &q);
  ~~~~~^~~~~~~~~~~~
semiexpress.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &v[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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