oj.uz

Submission #26931

# Submission time Handle Problem Language Result Execution time Memory
26931 2017-07-07T08:00:15 Z kajebiii Semiexpress (JOI17_semiexpress) C++14
100 / 100
 0 ms 2204 KB 
#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

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.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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