oj.uz

Submission #590336

# Submission time Handle Problem Language Result Execution time Memory
590336 2022-07-05T20:55:22 Z Gilwall Semiexpress (JOI17_semiexpress) C++14
100 / 100
 10 ms 356 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))

#define MOO(i,a,b) for (int i=a; i<b; i++)
#define M00(i,a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)

#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)

#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _<< " _ " <<

#define int long long

typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;

const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 1e9+7;

int POW(int b, int e) {
	int r = 1;
	while(e) {
		if(e % 2 == 1) {
			r *= b;
			r %= MOD;
		}
		e /= 2;
		b *= b;
		b %= MOD;
	}
	return r;
}
int gcd(int a, int b) {
	if(b > a) return gcd(b,a);
	if(b == 0) return a;
	return gcd(b, a % b);
}
int INV(int a) {
	return POW(a, MOD-2);
}
//Constants and Variables here
int n, m, k;
int A, B, C;
int T;
vi express;

vector<bool> added(3000, false);
int tot = 0;

int f(int e, int numstop) {
	int l = express[e];
	int r = express[e+1];
	vi semi;
	semi.pb(l);
	if(!added[e]) {
		int time = T - (l-1) * B;
		int loc = time / A;
		int delta = min(r-1, l + loc) - l + 1;
		if(time < 0) delta = 0;
		tot += delta;
		added[e] = true;
	}
	M00(i, numstop) {
		int semistop = semi.back();
		int time = T - (l-1) * B - (semistop - l) * C;
		int loc = time / A;
		if(time < A) {
			loc = 0;
		}
		semi.pb(semistop + loc + 1);
	}
	int semistop = semi.back();
	int time = T - (l-1) * B - (semistop - l) * C;
	int loc = time / A;
	//semi stop to semistop  + loc
	int extra = max(0ll, min(r-1, semistop + loc) - semistop + 1);
	if(time < 0) extra = 0;
	return extra;
}


int32_t main() { FAST
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n >> m >> k >> A >> B >> C >> T;
	express.resize(m);
	M00(i, m) cin >> express[i];
	express.pb(n+1);



	priority_queue<pi> Q;
	vi nums(m, 1);
	M00(i, m) {
		Q.push(mp(f(i, 1), i));
	}
	M00(i, k - m) {
		auto p = Q.top();
		Q.pop();
		tot += p.f;
		int e = p.s;
		nums[e] += 1;
		Q.push(mp(f(e, nums[e]), e));
	}
	cout << tot-1 << endl;
}

Compilation message

semiexpress.cpp:29:9: warning: ISO C++11 requires whitespace after the macro name
   29 | #define _<< " _ " <<
      |         ^

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 324 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 324 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 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 340 KB Output is correct
20 Correct 4 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 3 ms 356 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 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 10 ms 340 KB Output is correct