| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 100082 | ryansee | Semiexpress (JOI17_semiexpress) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
int n, m, k, a, b, c,TT,A[5006],dp[2][3006],val[3006];
ll T;
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;
// }
// }
ll at = from; ll ol = left;
while(x)
{
at += (left/a); left %= a;
if(at >= to - 1) return to-1;
left = ol-((at+1)-from)*c; if(left < 0) return at;
--x; at ++;
}
return min(at+(left/a),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; 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";
}