oj.uz

Submission #100071

# Submission time Handle Problem Language Result Execution time Memory
100071 2019-03-09T08:10:18 Z ryansee Semiexpress (JOI17_semiexpress) C++14
48 / 100
 1000 ms 512 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 424 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 428 KB Output is correct
8 Correct 2 ms 432 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 424 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 428 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 408 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 400 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 424 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 428 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 408 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 400 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Execution timed out 1062 ms 512 KB Time limit exceeded
20 Halted 0 ms 0 KB -