Submission #1212323

#TimeUsernameProblemLanguageResultExecution timeMemory
1212323biankSemiexpress (JOI17_semiexpress)C++20
100 / 100
470 ms14124 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define fst first #define snd second #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<ll> vll; typedef vector<int> vi; typedef pair<int,int> ii; struct range{ ll cost,len; ll cant(ll a, ll t){ if(cost>t) return 0LL; ll k=(t-cost)/a+1; if(k>len) return len; return k; } pair<range,range> split(ll a, ll c, ll t){ ll k=cant(a,t); range left,right; left.cost=cost; left.len=k; right.cost=cost+c*k; right.len=len-k; return {left,right}; } }; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll n,m,k,a,b,c,t; cin>>n>>m>>k>>a>>b>>c>>t; vll s(m+1); forn(i,m){ cin>>s[i]; --s[i]; } s[m]=n; k-=m; vector<vll> cnt(m); forn(i,m){ range curr; curr.cost=s[i]*b; curr.len=s[i+1]-s[i]; ll tot=0; forn(_,k+1){ tot+=curr.cant(a,t); cnt[i].pb(tot); curr=curr.split(a,c,t).snd; } } vll dp(k+1,0); forn(i,m){ vll nxt_dp(k+1,0); forn(j,k+1) forn(p,k+1-j){ nxt_dp[p+j]=max(nxt_dp[p+j],dp[j]+cnt[i][p]); } swap(dp,nxt_dp); } cout<<dp[k]-1<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...