Submission #26931

#	Time	Username	Problem	Language	Result	Execution time	Memory
26931		kajebiii	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	0 ms	2204 KiB

semiexpress

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef tuple<int, int, int> ti;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 3e3 + 10;

ll L, B, C, A, T;
int N, P, Nr[MAX_N];
struct DT {
	ll t; int ix, r, p;
	DT() {}
	DT(ll tt, int i, int rr) : t(tt), ix(i), r(rr), p(min(1ll*r, t/C + 1)) {}
	DT next() {
		int nextE = Nr[lower_bound(Nr, Nr+N, ix+1) - Nr];
		if(nextE <= ix + p) DT(-1, -1, -1);
		ll nt = t - p * B;
		return DT(nt, ix + p, nextE - (ix+p));
	}
	bool operator<(const DT &o) const {return p < o.p;}
};
ll ans = 0;
priority_queue<DT> Q;
void add(ll t, int ix) {
	if(t >= 0) ans++;
	if(t < B) return;
	if(ix == L) return;
	int nextE = Nr[lower_bound(Nr, Nr+N, ix+1) - Nr];
	int r = min(1ll*nextE - 1, ix + (t / C));
	ans += (r - ix);
//	printf("%lld\n", ans);
	t -= (r+1 - ix) * B;
	ix = r+1;
	Q.push(DT(t, ix, nextE - ix));
}
int main() {
	cin >> L >> N >> P; P -= N; cin >> C >> A >> B >> T;
	for(int i=0; i<N; i++) scanf("%d", &Nr[i]);

	for(int i=0; i<N; i++) add(T - A * (Nr[i] - 1), Nr[i]);
	while(!Q.empty() && P-- > 0) {
		DT temp = Q.top(); Q.pop();
		if(temp.t < 0 || temp.p <= 0) continue;
//		printf("%lld %d %d %d\n", temp.t, temp.ix, temp.r, temp.p);
		ans += temp.p;
		temp = temp.next();
		if(temp.ix == -1) continue;
		Q.push(temp);
	}
	printf("%lld\n", ans-1);
	return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:49:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%d", &Nr[i]);
                                            ^

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52