oj.uz

Submission #670452

# Submission time Handle Problem Language Result Execution time Memory
670452 2022-12-09T07:07:02 Z NothingXD Semiexpress (JOI17_semiexpress) C++17
100 / 100
 7 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
    ull q = (ull)((L(m) * a) >> 64);
    ull r = a - q * b; // can be proven that 0 <= r < 2*b
    return r >= b ? r - b : r;
  }
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e3 + 10;

ll n, A[maxn], idx[maxn], m, k, a, b, c;
ll t;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m >> k >> a >> b >> c >> t;

	int ans = 0;

	for (int i = 1; i <= m; i++){
		cin >> A[i];
		A[i]--;
		if (A[i] * b <= t) ans++;
	}


	for (int i = 1; i < m; i++){
		if (A[i] * b > t) break;
		ll tmp = t - A[i] * b;
		tmp = min(tmp / a, A[i+1] - A[i] - 1);
		ans += tmp;
		idx[i] = A[i] + tmp + 1;
	}

	for (int i = 1; i <= k-m; i++){
		ll res = 0;
		ll ptr = 0;
		for (int j = 1; j < m; j++){
			if (A[j] * b > t) break;
			if (idx[j] == A[j+1]) continue;
			if (A[j] * b + (idx[j] - A[j]) * c > t) continue;
			ll cnt = 1;
			ll tmp = t - A[j] * b - (idx[j] - A[j]) * c;
			cnt += min(tmp / a, A[j+1] - idx[j] - 1);
			if (res < cnt){
				res = cnt;
				ptr = j;
			}
		}
		ans += res;
		if (ptr != 0){
			idx[ptr] += res;
		}
	}

	cout << ans - 1 << '\n';

	return 0;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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