#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,s;
i64 k;
cin >> n >> s >> k;
vector<i64> d(n);
for(int i = 1;i < n;i++){
cin >> d[i];
d[i] += d[i - 1];
}
vector<int> v(n);
vector<i64> pref(n);
for(int i = 0;i < n;i++){
cin >> v[i];
pref[i] = v[i];
if(i) pref[i] += pref[i - 1];
}
vector<int> best(n); // what is the best node top put sheild if we want to take node i
vector<int> nx(n); // next empty node if we take index i
for(int i = 0;i < n;i++){
int ind = upper_bound(d.begin(),d.end(),d[i] + k) - d.begin();
nx[i] = ind;
ind --;
best[i] = ind;
}
auto S = [&](int l,int r){
if(l > r) return 0LL;
return pref[r] - (l ? pref[l - 1] : 0);
};
i64 ans = -1;
vector<int> fn;
vector<bool> vis(n,false);
for(int i = 0;i < n;i++){
if(vis[i]) continue;
int cur = i;
i64 tot = 0;
vector<pair<int,i64>> res;
while(cur < n){
vis[cur] = true;
int sh = best[cur];
int af = nx[sh];
tot += S(cur,af - 1);
res.emplace_back(cur,S(cur,af - 1));
cur = af;
}
i64 cv = 0;
for(int j = 0;j < min(s,(int)res.size());j++){
cv += res[j].second;
}
i64 mv = cv;
int mi = 0;
for(int j = 1;j < (int)res.size();j++){
cv -= res[j - 1].second;
if(j + s - 1 < (int) res.size()) cv += res[j + s - 1].second;
if(cv > mv){
mv = cv;
mi = j;
}
}
if(mv > ans){
ans = mv;
vector<int> my;
for(int j = mi;j < min(mi + s,(int)res.size());j++){
my.push_back(best[res[j].first]);
}
fn = my;
}
}
cout << (int) fn.size() << '\n';
for(int &e : fn) cout << e + 1 << " ";
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |