Submission #100071

#	Time	Username	Problem	Language	Result	Execution time	Memory
100071		ryansee	Semiexpress (JOI17_semiexpress)	C++14	48 / 100	1062 ms	512 KiB

semiexpress

#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890l
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define space " "
#define cbr cout << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, m, k, a, b, c,T,A[5006],dp[2][3006],val[3006];
ll bstar(ll x, ll from, ll to, ll left) // [from to)
{
	ll incur = 0;
	for(ll i = from+1; i < to; i++)
	{
		incur += a;
		if( incur > left)
		{
			if(x==0) return i-1;
			incur -= a;
			--x;
			incur = ((i-from)*c);
			if(incur > left) return i-1;
		}
	}
	return to-1;
}
int main()
{
	FAST
	cin>>n>>m>>k>>a>>b>>c>>T;
	FOR(i,0,m)cin>>A[i];
	A[m] = n+1;k-=m;
	for(ll i = 0; i < m; i++)
	{
		ll already = (A[i]-1)*b; if(T-already >= 0)
		dp[1][0]+=min(((T-already)/a + 1),A[i+1]-A[i]);
	}
	dp[1][0]--; // cerr << dp[1][0] << '\n';
	// cerr<<dp[1][0]<<'\n';
	for(ll i=1;i<=k;i++)dp[1][i]=dp[1][i-1];
	for(ll i = 0; i < m; i++)
	{
		ll already = (A[i]-1)*b;  mmst(val,0); ll far = min((T-already)/a+1,A[i+1]-A[i]); // cerr<<far<<' '<<A[i+1]<<' ' << A[i]<<'\n';assert(far>=1);
		// ll of=far; cerr<<already<<'\n';
		for(ll j = 1; j <= k; j++)
		{
			val[j] = bstar(j,A[i],A[i+1],T-already)-(far+A[i]-1);
			// cerr << j << ' ' << far+A[i]-1 << ' ' << T-already << '\n';
			// if(i==0&&j==1) cerr << "b:" << bstar(j,A[i],A[i+1],T-already)<<"\n";
		}
		// cerr << val[1] << '\n';
		// cerr << A[i] << ' ' << A[i]+far-1 << ' ' << val[1] << '\n';
		if(T-already >= 0)
		{
			// cerr << i << ' ' << val[1] << '\n';
			ll alt = i&1;
			for(ll j = 0; j <= k; j++)
			{
				for(ll w = k; w>=j; --w)
				{
					dp[alt][w]=max(dp[alt][w],dp[!alt][w-j]+val[j]);
				}
			}
		}
		for(ll j =0;j<=k;j++)dp[(i&1)][j]=max(dp[(i&1)][j],dp[!(i&1)][j]);
		mmst(dp[!(i&1)],0);
	}
	cout<<dp[(m-1)&1][k]<<"\n";
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 0 / 52