P1725琪露诺100WA求调

ZHANGGUIZHI @ 2024-10-09 22:08:16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+3;
int n,m,L,R,trash,a[N];
int f[N],l=1,r,q[N],t[N],ans;
void insert(int i){
  while(l<=r&&q[r]<=f[i])r--;
  q[++r]=f[i],t[r]=i;
  while(l<=r&&i-t[l]>=m)l++;
}
signed main(){
  ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
  cin>>n>>L>>R>>trash;m=R-l+1;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=L;i<=n;i++){
    insert(i-L);
    f[i]=q[l]+a[i];
    if(i+R>n)ans=max(ans,f[i]);
  }
  cout<<ans<<'\n';
  return 0;
}

by Michael_114 @ 2024-10-09 22:10:53

#include<iostream>
#include<set>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
#define inf 210000000
int n,l,r;
int a[maxn],f[maxn],q[maxn];
int head = 0,tail = 0;
int ans = -inf;
int main(){
    cin>>n>>l>>r;
    for(int i = 0;i<=n;i++){
        cin>>a[i];
    }
    f[0] = 0;
    for(int i = 1;i<=n;i++){
        f[i] = -inf;
    }
    for(int i = l;i<=n;i++){
        while(head<tail&&f[i-l]>=f[q[tail-1]]){
            tail--;
        }
        q[tail++] = i-l;
        while(head<tail&&q[head]<i-r){
            head++;
        }
        f[i] = f[q[head]]+a[i];
        if(i+r>n){
            ans = max(ans,f[i]);
        }
    }
    cout<<ans;
    return 0;
}

AC代码奉上，AC记录

by Michael_114 @ 2024-10-09 22:12:01

求关一个，会壶关

by ZHANGGUIZHI @ 2024-10-09 22:17:51

@Michael_114 谢谢你，不过似乎我的问题还没有解决

by Elysialr @ 2024-10-09 22:39:21

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+3;
int n,m,L,R,trash,a[N];
int f[N],l=1,r,q[N],t[N],ans=-(1<<30);
void insert(int i){
  while(l<=r&&q[r]<f[i])r--;
  r++;q[r]=f[i],t[r]=i;
  while(l<=r&&i+L-t[l]>R)l++;
}
signed main(){
  ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
  cin>>n>>L>>R>>trash;m=R-l+1;
  for(int i=1;i<=n;i++){cin>>a[i];f[i]=-(1<<30);}
  f[0]=0;
  for(int i=L;i<=n;i++){
    insert(i-L);
    f[i]=q[l]+a[i];
    if(i+R>n)ans=max(ans,f[i]);
  }
  cout<<ans<<'\n';
  return 0;
}

by ZHANGGUIZHI @ 2024-10-10 08:18:09

@Elysialr thanks,已A