求助为什么不能用双指针呢,80分
  • 板块P1714 切蛋糕
  • 楼主loliconsk
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/14 20:18
  • 上次更新2023/11/14 21:47:10
查看原帖
求助为什么不能用双指针呢,80分
455712
loliconsk楼主2023/11/14 20:18
// LUOGU_RID: 109908298
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<deque>
#include<bitset>
#include<unordered_map>
#include <chrono>
using namespace std;
#define ULL unsigned long long
#define mest(x,y) memset(x,y,sizeof x)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first 
#define se second 
#define ppb pop_back
#define pb push_back
#define rep(i, l, r) for(int i = l; i <= (r); ++ i)
#define per(i, r, l) for(int i = r; i >= (l); -- i)
#define reps(i, l, r, d) for(int i = l; i <= (r); i += d)
#define pers(i, r, l, d) for(int i = r; i >= (l); i -= d)
typedef pair<int,int>PII;
typedef pair<int,char>PIC;
typedef pair<int,pair<int,int> > PPI;
const int N = 1e6+10,M=N*2;
const int MOD = 2147493647;
const int INF = 0x3f3f3f3f3f3f3f3f;
const ULL mask = std::chrono::steady_clock::now().time_since_epoch().count();
const int MAT = 10;
struct Matrix
{
  int mat[MAT][MAT];
  int r,c;

  void init()
  {
    mest(mat,0);
    for(int i = 0;i<MAT;i++)mat[i][i] = 1;
  }
  void print()
  {
    for(int i = 1;i<=r;i++)
    {
      for(int j = 1;j<=c;j++)
      {
        cout << mat[i][j]<<" ";
      }
      cout << endl;
    }
  }
};
Matrix mul_mat(Matrix a,Matrix b)
{
  Matrix res;
  int res_r = a.r,res_c = b.c;
  res.r = a.r,res.c = b.c;
  mest(res.mat,0);
  for(int i = 1;i<=res_r;i++)
  {
    for(int j = 1;j<=res_c;j++)
    {
      for(int k = 1;k<=res_r;k++)
      {
        res.mat[i][j] = (res.mat[i][j]+a.mat[i][k]*b.mat[k][j]%MOD)%MOD;
      }
    }
  }
  return res;
}
Matrix qmi(Matrix a,int b)
{
  Matrix res;
  res.r = a.r;
  res.c = a.c;
  res.init();
  while(b)
  {
    if(b&1)res = mul_mat(a,res);
    b>>=1;
    a = mul_mat(a,a);
  }
  return res;
}
ULL shift(ULL x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= mask;
  return x;
}
vector<int> add(vector<int> a,vector<int> b)
{
  int t = 0;
  vector<int> c;
  for(int i = 0;i<max(a.size(),b.size());i++)
  {
    if(i<a.size())t+=a[i];
    if(i<b.size())t+=b[i];
    c.pb(t%10);
    t/=10;
  }
  while(t)c.pb(t%10),t/=10;
  return c;
}
int a[N];
void solve()
{
    int n,m;cin>>n>>m;
    int ans = -INF;
    for(int i= 1;i<=n;i++)
    {
      cin>>a[i];
      ans = max(ans,a[i]);
    }
    int res = 0;
    for(int i = 1,j = 1;j<=n;j++)
    {
      res+=a[j];
      // cout << res <<endl;
      while(i<=j && (a[i]<=0||res<=0 || j-i+1>m))
      {
        // cout << a[i]<<"**"<<endl;
        res-=a[i];
        i++;
      }
      if(j-i+1>=1 && j-i+1 <= m)ans = max(ans,res);
    }
    cout << ans <<endl;
    return ;
}
signed main()
{
    IOS;
    int t = 1;
    // cin>>t;
    // scanf("%lld",&t);
    while(t--)
    {
      solve();
    }
    return 0;
}
/*
5 3
-1 7 -10 5 5
*/
2023/11/14 20:18
加载中...