oj.uz

Submission #335055

# Submission time Handle Problem Language Result Execution time Memory
335055 2020-12-11T02:56:52 Z ChrisT Semiexpress (JOI17_semiexpress) C++17
100 / 100
 1 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;
const int MN = 3e3 + 3;
int dp[MN][MN];
int main() {
	int n,m,k,a,b,c; long long t,ret=0;
	scanf ("%d %d %d %d %d %d %lld",&n,&m,&k,&a,&b,&c,&t); swap(a,b); swap(b,c);
	vector<int> s(m); k -= m;
	for (auto &au : s) scanf ("%d",&au);
	priority_queue<array<long long,3>> pq;
	for (int i = 0; i + 1 < m; i++) {
		long long exp = (long long)a * (s[i]-1), st = max((long long)s[i],((long long)c * (1 + s[i]) + t - exp) / c), ed = min((t - exp - (long long)b * (st - s[i]) + (long long)c * st) / c,(long long)s[i+1] - 1);
		pq.push({ed - st + 1, ed, i});
		ret += min(st,(long long)s[i+1]) - s[i];
	}
	ret += (long long)a * (n-1) <= t;
	for (int i = 0; i < k; i++) {
		auto [sz,oed,idx] = pq.top(); pq.pop();
		ret += max(0LL,sz);
		long long st = oed + 1, ed = min((t - (long long)a*(s[idx]-1) - (long long)b * (st - s[idx]) + (long long)c * st) / c,(long long)s[idx+1] - 1);
		pq.push({ed - st + 1, ed, idx});
	}
	printf ("%lld\n",ret-1);
	return 0;
}

Compilation message

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

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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