oj.uz

Submission #158104

# Submission time Handle Problem Language Result Execution time Memory
158104 2019-10-14T18:50:38 Z ZwariowanyMarcin Semiexpress (JOI17_semiexpress) C++14
100 / 100
 550 ms 67028 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)	
	
		
using namespace std;

int n, m, k;
int a, b, c;
ll T;
int s[3005];
ll ans = 0;

multiset <ll> secik;
					
int main() {	
	scanf("%d %d %d", &n, &m, &k);
	k = k - m;
	scanf("%d %d %d", &a, &b, &c);
	scanf("%lld", &T);
	FOR(i, 1, m)
		scanf("%d", &s[i]);
	FOR(i, 1, m) {
		ll cash = (ll) (s[i] - 1) * b;
		if(cash <= T && i > 1)
			ans += 1;
		if(i == m)
			break;
		ll ile = s[i + 1] - s[i] - 1;
		ll happy = min(ile, max(1LL * 0, (T - cash) / a));
		ile -= happy;
		ans += happy;
		ll people = happy;
		FOR(j, 1, k) {
			ll all = cash + (people + 1) * c;
			happy = min(ile, max(1LL * 0, (T - all) / a + (all <= T)));
			//cout << i << " " << j << " " << happy << " " << ile << " " << people << endl;
			secik.insert(happy);
			ile -= happy;
			people += happy;
		}		
	}
	//cout << ans << endl;
	while(k--) {
		ll e = *(--secik.end());
		ans += e;
		secik.erase(--secik.end());
	}
	printf("%lld\n", ans);
			
		
	
	
				
	return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:28: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:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &a, &b, &c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &T);
  ~~~~~^~~~~~~~~~~~
semiexpress.cpp:33: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 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 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 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 2 ms 252 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 508 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 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 2 ms 252 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 508 KB Output is correct
19 Correct 224 ms 30456 KB Output is correct
20 Correct 550 ms 67028 KB Output is correct
21 Correct 3 ms 504 KB Output is correct
22 Correct 49 ms 8184 KB Output is correct
23 Correct 229 ms 50296 KB Output is correct
24 Correct 4 ms 632 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 3 ms 504 KB Output is correct
28 Correct 3 ms 500 KB Output is correct
29 Correct 68 ms 14332 KB Output is correct
30 Correct 46 ms 9136 KB Output is correct