Submission #335055

#	Time	Username	Problem	Language	Result	Execution time	Memory
335055		ChrisT	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	492 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52