Submission #48312397

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define mz 998244353
using namespace std;
int a[250005];
long long sum[250005];
long long dp[250005],dps[250005];
int main(){
  int n;
  int l,r,mid,p1=0,p2=0;
  long long s,ans=0;
  scanf("%d%lld",&n,&s);
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    sum[i]=sum[i-1]+a[i];
  }
  a[n+1]=s+5;
  sum[n+1]=sum[n]+a[n+1]; 
  for(int i=1;i<=n;i++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define mz 998244353

using namespace std;

int a[250005];
long long sum[250005];
long long dp[250005],dps[250005];

int main(){
	int n;
	int l,r,mid,p1=0,p2=0;
	long long s,ans=0;
	scanf("%d%lld",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	a[n+1]=s+5;
	sum[n+1]=sum[n]+a[n+1]; 
	for(int i=1;i<=n;i++){
		dp[i]=1;
		if(sum[i]>s){
			while(sum[i]-sum[p2]>s)
				p2++;
			while(sum[i-1]-sum[p1]>s)
				p1++;
			dp[i]+=dps[p2]-dps[p1];
		}
		ans+=dp[i]*(n-i+1);
		dps[i]=dps[i-1]+dp[i];
		//cout<<i<<" "<<dp[i]<<endl;
	}
	printf("%lld\n",ans);
	return 0;
} 
/*
		0		1		2		3		4		5
0		1		1		1		1		1		1
1		0		1		2		3		4		5
2		0		1		3		6		10		15
3		0		1		4		10		20
4		0		1		5		15		35
d k
C(d+10^100-1,10^100-1)
C(a,b)=a!/(b!*(a-b)!)
=(d+10^100-1)!/((10^100-1)!*d!)
*/

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:12:13: warning: unused variable ‘l’ [-Wunused-variable]
   12 |         int l,r,mid,p1=0,p2=0;
      |             ^
Main.cpp:12:15: warning: unused variable ‘r’ [-Wunused-variable]
   12 |         int l,r,mid,p1=0,p2=0;
      |               ^
Main.cpp:12:17: warning: unused variable ‘mid’ [-Wunused-variable]
   12 |         int l,r,mid,p1=0,p2=0;
      |                 ^~~
Main.cpp:14:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |         scanf("%d%lld",&n,&s);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:16:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |                 scanf("%d",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~

Judge Result