oj.uz

Submission #46821

# Submission time Handle Problem Language Result Execution time Memory
46821 2018-04-23T16:42:09 Z golub Semiexpress (JOI17_semiexpress) C++14
100 / 100
 20 ms 2156 KB 
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX_M = 3000;

int N, M, K;
long long A, B, C;
long long T;
int s[MAX_M];

int nums[3000 * 3000];
int c = 0;

int getNums(int l, int r){
	int res = 0;
	long long t = B * l;
	int id = l;
	int cnt = 0;
	while(id < r){
		long long x = T - t;
		if(x < 0) break;
		x /= A;
		long long nxt = id + x + 1;
		nxt = min((long long)r, nxt);
		if(id == l) res = nxt - id;
		else nums[c++] = nxt - id;
		t += C * (nxt - id);
		id = nxt;
		cnt++;
		if(cnt > K - M) break;
	}
	return res;
}


int solve(){
	int ans = B * s[M - 1] <= T ? 1 : 0;
	for(int i = 0; i < M - 1; ++i){
		ans += getNums(s[i], s[i + 1]);
	}
	sort(nums, nums + c);
	reverse(nums, nums + c);
	for(int i = 0; i < K - M; ++i){
		ans += nums[i];
	}
	return ans - 1;
}

void input(){
	scanf("%d%d%d", &N, &M, &K);
	scanf("%lld%lld%lld", &A, &B, &C);
	scanf("%lld", &T);
	for(int i = 0; i < M; ++i){
		scanf("%d", s + i);
		s[i]--;
	}
}

int main(){
	input();
	int ans = solve();
	printf("%d\n", ans);
	return 0;
}

Compilation message

semiexpress.cpp: In function 'void input()':
semiexpress.cpp:53: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:54: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:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &T);
  ~~~~~^~~~~~~~~~~~
semiexpress.cpp:57: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 380 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 2 ms 608 KB Output is correct
8 Correct 2 ms 608 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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