Submission #62249

#	Time	Username	Problem	Language	Result	Execution time	Memory
62249		kingpig9	Semiexpress (JOI17_semiexpress)	C++11	100 / 100	24 ms	980 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52