QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252584 | #4590. Happy Travelling | lam | TL | 9ms | 34828kb | C++14 | 1.9kb | 2023-11-15 21:53:04 | 2023-11-15 21:53:05 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int dp[maxn],dp2[maxn];
int f[4*maxn];
int a[maxn],t[maxn];
int n,k,d;
priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>> > pq[maxn];
void update(int x, int lx, int rx, int l, int r, int val)
{
if (lx>r||rx<l) return;
if (lx>=l&&rx<=r)
{
f[x]=max(f[x],val);
return;
}
int mid=(lx+rx)/2;
update(2*x,lx,mid,l,r,val);
update(2*x+1,mid+1,rx,l,r,val);
}
int get(int x, int lx, int rx, int idx)
{
if (lx==rx) return f[x];
int mid=(lx+rx)/2;
if (idx<=mid) return max(f[x],get(2*x,lx,mid,idx));
else return max(f[x],get(2*x+1,mid+1,rx,idx));
}
signed main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k >> d;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int j = 1; j < n; j++) cin >> t[j];
fill_n(dp,n+1,-1e18);
fill_n(dp2,n+1,-1e18);
fill_n(f,4*n+1,-1e18);
update(1,1,n,1,1,0);
int mmax = -1;
for (int i = 1; i <= n; i++)
{
// while (!pq[i%k].empty() && i > pq[i%k].top().second) pq[i%k].pop();
// if (!pq[i%k].empty()) dp[i] = max(dp[i], -(i-1)/k*d + pq[i%k].top().first);
// int val2 = dp[i];
// update(1,1,n,i,i+k-1,val2);
dp[i] = max(dp[i], get(1,1,n,i));
dp[i] += a[i];
int val = dp[i];
// cout << dp[i] << " \n";
if (i == n) continue;
mmax = max(mmax, i+t[i]);
int lo = (mmax - i) / k * k;
update(1,1,n,i+lo,mmax,dp[i] - d * (lo / k));
for (int j = 0; j < lo; j += k) update(1,1,n,i+j,i+j+k-1,dp[i] - d * (j / k));
// cout << i << " : " << i + k - 1 << " & " << lo << '\n';
// if (lo > 0) update(1,1,n,i+1,i+k-1,val);
// pq[i%k].push({dp[i]+(i-1)/k*d,i+lo-1});
}
cout << dp[n] << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 34824kb
input:
6 2 1 8 -7 -8 9 0 2 5 3 3 2 1
output:
18
result:
ok single line: '18'
Test #2:
score: 0
Accepted
time: 4ms
memory: 34644kb
input:
8 8 8 10 -5 -5 -5 -5 -5 -5 10 5 2 5 3 2 1 1
output:
15
result:
ok single line: '15'
Test #3:
score: 0
Accepted
time: 9ms
memory: 34656kb
input:
13 2 2 -5 -4 -4 -1 7 -6 -5 -4 -3 -2 -1 5 -7 3 10 9 8 7 6 5 4 3 2 1 1
output:
-9
result:
ok single line: '-9'
Test #4:
score: 0
Accepted
time: 7ms
memory: 34828kb
input:
2 1 0 -10000 10000 1
output:
0
result:
ok single line: '0'
Test #5:
score: -100
Time Limit Exceeded
input:
98987 4 3 -8225 -8961 -5537 -5621 -8143 -5214 -5538 -6912 -6601 -8839 -7872 -7867 -9553 -9793 -7333 -7360 -5820 -7459 -8824 -9716 -9757 -5846 -5300 -5912 -7953 -8360 -7609 -5937 -5525 -9748 -7326 -8311 -9979 -9292 -8542 -7589 -7939 -5914 -7985 -9999 -9212 -8274 -8084 -6620 -5991 -7826 -6327 -5228 -6...