oj.uz

Submission #62249

# Submission time Handle Problem Language Result Execution time Memory
62249 2018-07-27T23:45:13 Z kingpig9 Semiexpress (JOI17_semiexpress) C++11
100 / 100
 24 ms 980 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using ordset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int MAXM = 3010;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

ll N;
int M, K;
ll A, B, C;
ll T;
ll S[MAXM];
ll ext[MAXM];	//first one where you run out of gas

int main() {
	scanf("%lld %d %d %lld %lld %lld %lld", &N, &M, &K, &A, &B, &C, &T);
	assert(B < C && C < A);	//B = express, C = semiexpress, A = local
	//stations are in range[0, N - 1)
	for (int i = 0; i < M; i++) {
		scanf("%lld", &S[i]);
		S[i]--;
	}
	assert(S[0] == 0);
	assert(S[M - 1] == N - 1);

	K -= M;	//we add K more stations
	for (int i = 0; i < M - 1; i++) {
		ll nleft = T - B * S[i];
		if (nleft >= 0) {
			ext[i] = min(nleft / A + 1, S[i + 1] - S[i]);	//how many can it go - including this one?
			debug("ext[%d] = %lld\n", i, ext[i]);
		}
	}

	for (int as = 0; as < K; as++) {
		pair<ll, int> fav(0ll, 0);	//favorite - max one
		for (int i = 0; i < M - 1; i++) {
			//how much does this add?
			//remember -- ext = how much you lead to after this one.
			//if you install a semiexp at this station, then how much?
			ll nleft = T - B * S[i] - C * ext[i];
			//if even this can't reach you here then I don't know what would...
			//how much does this add?
			debug("i = %d. nleft = %lld.\n", i, nleft);
			if (nleft >= 0) {
				ll nadd = min(nleft / A + 1, S[i + 1] - (S[i] + ext[i]));
				fav = max(fav, make_pair(nadd, i));
				debug("nadd = %lld.\n", nadd);
			}
		}

		//ok this is the favorite now!
		debug("FAV: %lld %d\n", fav.fi, fav.se);
		ext[fav.se] += fav.fi;
	}

	for (int i = 0; i < M - 1; i++) {
		debug("ext[%d] = %lld\n", i, ext[i]);
	}

	printf("%lld\n", accumulate(ext, ext + M - 1, 0ll) + ((N - 1) * B <= T) - 1);
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %d %d %lld %lld %lld %lld", &N, &M, &K, &A, &B, &C, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &S[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 3 ms 408 KB Output is correct
5 Correct 3 ms 428 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 3 ms 544 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 3 ms 408 KB Output is correct
5 Correct 3 ms 428 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 3 ms 548 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 3 ms 676 KB Output is correct
13 Correct 3 ms 676 KB Output is correct
14 Correct 3 ms 676 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 676 KB Output is correct
17 Correct 2 ms 676 KB Output is correct
18 Correct 4 ms 688 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 3 ms 408 KB Output is correct
5 Correct 3 ms 428 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 3 ms 548 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 3 ms 676 KB Output is correct
13 Correct 3 ms 676 KB Output is correct
14 Correct 3 ms 676 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 676 KB Output is correct
17 Correct 2 ms 676 KB Output is correct
18 Correct 4 ms 688 KB Output is correct
19 Correct 7 ms 692 KB Output is correct
20 Correct 9 ms 752 KB Output is correct
21 Correct 3 ms 900 KB Output is correct
22 Correct 5 ms 964 KB Output is correct
23 Correct 24 ms 964 KB Output is correct
24 Correct 3 ms 964 KB Output is correct
25 Correct 4 ms 964 KB Output is correct
26 Correct 5 ms 964 KB Output is correct
27 Correct 3 ms 964 KB Output is correct
28 Correct 4 ms 964 KB Output is correct
29 Correct 8 ms 980 KB Output is correct
30 Correct 6 ms 980 KB Output is correct