QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21630 | #2841. 赛艇 | Mr_Eight# | AC ✓ | 5642ms | 965872kb | C++14 | 14.6kb | 2022-03-07 17:10:39 | 2022-05-08 03:44:17 |
Judging History
answer
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
template<class T>
inline void read(T &x) {
x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
if(fu)x=-x;
}
inline int read() {
int x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
return fu?-x:x;
}
template<class T,class... Args>
inline void read(T& t,Args&... args) {
read(t);
read(args...);
}
char _n_u_m_[40];
template<class T>
inline void write(T x ) {
if(x==0) {
putchar('0');
return;
}
T tmp = x > 0 ? x : -x ;
if( x < 0 ) putchar('-') ;
register int cnt = 0 ;
while( tmp > 0 ) {
_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
tmp /= 10 ;
}
while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
}
template<class T>
inline void write(T x ,char ch) {
write(x);
putchar(ch);
}
}
using namespace fastIO;
#define mod 469762049
#define MOD mod
#define P mod
#define inv2 (469762049+1>>1)
#define EXP 1
//快速幂
inline long long pw(long long x,long long p) {
long long res=1;
for(; p; p>>=1,x=x*x%mod)
if(p&1)res=res*x%mod;
return res;
}
//分数取模
inline long long getm(long long top,long long bot) {
return (top*pw(bot,mod-2))%mod;
}
namespace getinv {
int *inv,*fac,*ifac;//逆元,阶乘,阶乘逆元
//预处理逆元函数,若需使用多项式积分/ln/exp/快速幂等,则需在main函数开头调用
void init_inv(int n) {
inv=new int[n+1];
inv[0]=1;
inv[1]=1;
for(register int i=2; i<=n; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
//预处理逆元,阶乘,阶乘逆元
void init_inv_with_fac(int n) {
inv=new int[n+1];
fac=new int[n+1];
ifac=new int[n+1];
inv[0]=fac[0]=ifac[0]=1;
inv[1]=1;
for(register int i=2; i<=n; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(register int i=1; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;
for(register int i=1; i<=n; ++i) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
}
}
using namespace getinv;
namespace Poly {
int *w[30];//单位根
//预处理单位根函数,需在main函数开头调用
void NTT_set(int MAXN) {
for(int i=2,t=0; i<2*MAXN; i<<=1,t++) {
w[t]=new int[i>>1];
ll wn=pw(3,(MOD-1)/i);
w[t][0]=1;
for(int j=1; j<(i>>1); j++) w[t][j]=w[t][j-1]*wn%MOD;
}
}
struct poly {
vector<int>a;//f=a[0]+a[1]*x+a[2]*x^2+...+a[n]*x^n
//n次多项式size为n,其中a.size()=n+1
/*--------------------构造函数--------------------*/
poly() {
}
poly(int sz) {
a.resize(sz+1);
}
#if __cplusplus >= 201103L
poly(initializer_list<int>x) {
a=x;
}
#endif
poly(vector<int>vec) {
a=vec;
}
template<class T>
poly(T s,T t) {
//含左边界,不含右边界
a=vector<int>(s,t);
}
poly(const poly &x) {
a=x.a;
}
/*--------------------基本操作--------------------*/
inline int size() {
return a.size()-1;
}
inline void resize(int x) {
a.resize(x+1);
}
inline int& operator[](int pos) {
return a[pos];
}
inline poly subpoly(int l,int r) {
//含左边界,不含右边界
return poly(&a[l],&a[r]);
}
/*--------------------快速数论变换--------------------*/
//NTT变换
inline void NTT() {
int N=a.size(),len=1;//N=多项式次数+1
while(len<N)len<<=1;
if(N<len) {
resize(len-1);
}
unsigned ll A[len];
F(i,0,len-1)A[i]=a[i];
register int j=len>>1;
for(register int i=1; i<len-1; i++) {
if (i<j) swap(A[i],A[j]);
int k=len>>1;
while (j>=k) {
j-=k;
k>>=1;
}
j+=k;
}
for(register int i=2,t=0; i<=len; i<<=1,t++) {
if(t==17)for(register int j=0; j<len; ++j)A[j]%=MOD;
for(register int j=0; j<len; j+=i)
for(register int k=j; k<j+(i>>1); k++) {
unsigned ll u=A[k];
unsigned ll v=w[t][k-j]*A[k+(i>>1)]%MOD;
A[k]=u+v;
A[k+(i>>1)]=u-v+mod;
}
}
F(i,0,len-1)a[i]=A[i]%mod;
}
//NTT逆变换
inline void UNTT() {
int N=a.size(),len=1;//N=多项式次数+1
while(len<N)len<<=1;
if(N<len) {
resize(len-1);
}
unsigned ll A[len];
F(i,0,len-1)A[i]=a[i];
register int j=len>>1;
for(register int i=1; i<len-1; i++) {
if (i<j) swap(A[i],A[j]);
int k=len>>1;
while (j>=k) {
j-=k;
k>>=1;
}
j+=k;
}
for(register int i=2,t=0; i<=len; i<<=1,t++) {
if(t==17)for(register int j=0; j<len; ++j)A[j]%=MOD;
for(register int j=0; j<len; j+=i)
for(register int k=j; k<j+(i>>1); k++) {
unsigned ll u=A[k];
unsigned ll v=w[t][k-j]*A[k+(i>>1)]%MOD;
A[k]=u+v;
A[k+(i>>1)]=u-v+mod;
}
}
reverse(A+1,A+len);
ll nev=pw(len,MOD-2);
for(int i=0; i<len; i++) a[i]=(A[i]%MOD)*nev%MOD;
}
/*--------------------多项式运算--------------------*/
//多项式加法
inline poly operator+(poly b) {
register int n=size(),bn=b.size();
if(n>=bn) {
poly rt(a);
for(register int i=0; i<=bn; ++i)rt.a[i]=(a[i]+b.a[i])%mod;
return rt;
}
poly rt(b);
for(register int i=0; i<=n; ++i)rt.a[i]=(a[i]+b.a[i])%mod;
return rt;
}
//多项式减法
inline poly operator-(poly b) {
register int n=size(),bn=b.size();
if(n>=bn) {
poly rt(a);
for(register int i=0; i<=bn; ++i)rt.a[i]=(a[i]-b.a[i]+mod)%mod;
return rt;
}
poly rt(bn);
for(register int i=0; i<=n; ++i)rt.a[i]=(a[i]-b.a[i]+mod)%mod;
for(register int i=n+1; i<=bn; ++i)rt.a[i]=(mod-b.a[i])%mod;
return rt;
}
//负多项式
inline poly operator-() {
register int n=size();
poly rt(n);
for(register int i=0; i<=n; ++i)rt.a[i]=(mod-a[i])%mod;
return rt;
}
//多项式乘法
inline poly operator*(poly b) {
int n=size(),bn=b.size();
int len=n+bn;
if(1ll*n*bn<=10000) {
poly rt(len);
for(register int i=0; i<=n; ++i) {
for(register int j=0; j<=bn; ++j) {
rt.a[i+j]=(rt.a[i+j]+1ll*a[i]*b.a[j])%mod;
}
}
return rt;
}
poly A(a),B(b.a);
A.resize(len);
B.resize(len);
A.NTT();
B.NTT();
poly rt(A.size());
for(register int i=0; i<=A.size(); ++i)rt.a[i]=1ll*A.a[i]*B.a[i]%mod;
rt.UNTT();
rt.resize(len);
return rt;
}
//多项式乘法(保留次数为左侧多项式次数)
inline poly operator&(poly b) {
int n=size(),bn=b.size();
int len=n+bn;
if(1ll*n*bn<=10000) {
poly rt(n);
for(register int i=0; i<=n; ++i) {
for(register int j=0; j<=min(bn,n-i); ++j) {
rt.a[i+j]=(rt.a[i+j]+1ll*a[i]*b.a[j])%mod;
}
}
return rt;
}
poly A(a),B(b.a);
A.resize(len);
B.resize(len);
A.NTT();
B.NTT();
poly rt(A.size());
for(register int i=0; i<=A.size(); ++i)rt.a[i]=1ll*A.a[i]*B.a[i]%mod;
rt.UNTT();
rt.resize(n);
return rt;
}
//多项式卷积的转置运算(res[i-j]+=f[i]*g[j])
inline poly operator^(poly b) {
poly temp=b.rev();
temp=(*this)*temp;
temp.a.erase(temp.a.begin(),temp.a.begin()+b.size());
return temp;
}
//多项式求逆
inline poly inv() {
if(size()==0) {
return poly(vector<int>(1,getm(1,a[0])));
}
poly sub(size()>>1),temp;
int ss=sub.size();
for(register int i=0; i<=ss; ++i)sub.a[i]=a[i];
sub=sub.inv();
temp=(*this)&(sub*sub);
F(i,0,ss)sub[i]=(sub[i]<<1)%mod;
return sub-temp;
}
//多项式开根(需保证多项式常数项为1)
inline poly sqrt() {
if(size()==0) {
return poly(vector<int>(1,1));
}
poly sub(size()>>1);
int ss=sub.size();
for(register int i=0; i<=ss; ++i)sub.a[i]=a[i];
sub=sub.sqrt();
sub.resize(size());
sub=((*this)&sub.inv())+sub;
ss=size();
for(register int i=0; i<=ss; ++i)sub.a[i]=1ll*sub.a[i]*inv2%mod;
return sub;
}
//多项式系数翻转
inline poly rev() {
poly rt(a);
reverse(rt.a.begin(),rt.a.end());
return rt;
}
//多项式除法
inline poly operator/(poly b) {
if(b.size()>size())return poly();
poly temp=b.rev();
temp.resize(size());
poly rt=rev()&temp.inv();
rt.resize(size()-b.size());
return rt.rev();
}
//多项式取模
inline poly operator%(poly b) {
if(b.size()>size())return *this;
poly rt=(*this)-(*this)/b*b;
rt.resize(b.size()-1);
return rt;
}
//多项式求导
inline poly dev() {
int n=size();
poly rt(n-1);
for(register int i=1; i<=n; ++i)rt.a[i-1]=1ll*i*a[i]%mod;
return rt;
}
//多项式积分
inline poly inter() {
int n=size();
poly rt(n+1);
for(register int i=0; i<=n; ++i)rt.a[i+1]=1ll*a[i]*getinv::inv[i+1]%P;
return rt;
}
//多项式积分(舍弃最高位)
inline poly inter2() {
int n=size();
poly rt(n);
for(register int i=0; i<n; ++i)rt.a[i+1]=1ll*a[i]*getinv::inv[i+1]%P;
return rt;
}
//多项式对数函数(需常数项为1)
inline poly ln() {
return (inv()&dev()).inter2();
}
//分治求解多项式指数函数子函数:分治FFT
inline void exp_solve(int l,int r,vector<int> &op,int rr) {
if(l==r)return;
int mid=(l+r)>>1;
exp_solve(l,mid,op,rr);
if(mid>=rr)return;
poly sub(a.begin(),a.begin()+r-l+1),temp(op.begin()+l,op.begin()+mid+1);
sub=sub&temp;
for(int i=mid-l+1,iend=min(r,rr)-l; i<=iend; ++i)op[i+l]=(op[i+l]+1ll*getinv::inv[i+l]*sub[i])%mod;
exp_solve(mid+1,r,op,rr);
}
//分治求解多项式指数函数(需常数项为0)(复杂度O(nlog^2n),常数较小,实测比牛顿迭代略快)
#if EXP==1
inline poly exp() {
#else
inline poly exp2() {
#endif
unsigned int k=1;
int temp=a.size();
while(k<a.size())k<<=1;
a.resize(k);
for(int i=1; i<temp; ++i)a[i]=1ll*a[i]*i%mod;
vector<int>res(a.size(),0);
res[0]=1;
exp_solve(0,size(),res,temp-1);
for(int i=1; i<temp; ++i)a[i]=1ll*a[i]*getinv::inv[i]%mod;
a.resize(temp);
res.resize(temp);
return poly(res);
}
//牛顿迭代求解多项式指数函数(需常数项为0)(复杂度O(nlogn),常数较大)
#if EXP!=1
inline poly exp() {
#else
inline poly exp2() {
#endif
if(size()==0) {
return poly(vector<int>(1,1));
}
poly sub(size()>>1),temp;
int ss=sub.size();
for(register int i=0; i<=ss; ++i)sub.a[i]=a[i];
sub=sub.exp();
temp=sub;
temp.resize(size());
temp=*this-temp.ln();
temp.a[0]=(temp.a[0]+1)%mod;
return temp⊂
}
/*--------------------多项式功能--------------------*/
//多项式快速幂(x为指数)
inline poly power(ll x) {
vector<int>temp=a;
int t1=0,t2=0,n=size();
for(register int i=0; i<=n; ++i) {
if(a[i]) {
t1=i,t2=a[i];
for(register int j=i; j<=n; ++j)a[j]=getm(a[j],t2);
a.erase(a.begin(),a.begin()+i);
break;
}
}
if((x>=mod&&t1)||!t2) {
a=temp;
return poly(n);
}
ll xx=x%(mod-1);
x%=mod;
if(t1*x>n) {
a=temp;
return poly(n);
}
t2=pw(t2,xx);
*this=ln();
for(register int i=0; i<=n; ++i)a[i]=a[i]*x%mod;
*this=exp();
for(register int i=0; i<=n; ++i)a[i]=1ll*a[i]*t2%mod;
a.insert(a.begin(),t1*x,0);
swap(a,temp);
return temp;
}
//多项式快速幂(x为指数对mod取模的结果,xx为指数对mod-1取模的结果)
inline poly power(ll x,ll xx,bool exc=false) {
vector<int>temp=a;
int t1=0,t2=0,n=size();
for(register int i=0; i<=n; ++i) {
if(a[i]) {
t1=i,t2=a[i];
for(register int j=i; j<=n; ++j)a[j]=getm(a[j],t2);
a.erase(a.begin(),a.begin()+i);
break;
}
}
if((exc&&t1)||t1*x>n||!t2) {
a=temp;
return poly(n);
}
t2=pw(t2,xx);
*this=ln();
for(register int i=0; i<=n; ++i)a[i]=a[i]*x%mod;
*this=exp();
for(register int i=0; i<=n; ++i)a[i]=1ll*a[i]*t2%mod;
a.insert(a.begin(),t1*x,0);
swap(a,temp);
return temp;
}
//多项式多点求值子函数一;求每段多项式乘积
inline void multieva_getpoly(int *bg,int *ed,int p,poly *op) {
if(bg+1==ed) {
op[p]=poly(1);
op[p][1]=1;
op[p][0]=mod-*bg;
return;
}
multieva_getpoly(bg,bg+((ed-bg)>>1),p<<1,op);
multieva_getpoly(bg+((ed-bg)>>1),ed,p<<1|1,op);
op[p]=op[p<<1]*op[p<<1|1];
}
//多项式多点求值子函数二:进行分治求解
inline void multieva_solve(int *bg,int *ed,poly *mul,int p,int *op) {
if(bg+1==ed) {
*op=a[0];
return;
}
poly t1=(*this)%mul[p<<1],t2=(*this)%mul[p<<1|1];
t1.multieva_solve(bg,bg+((ed-bg)>>1),mul,p<<1,op);
t2.multieva_solve(bg+((ed-bg)>>1),ed,mul,p<<1|1,op+((ed-bg)>>1));
}
//多项式多点求值
inline void multieva(int *bg,int *ed,int *op) {
vector<poly>temp((ed-bg+1)<<2);
multieva_getpoly(bg,ed,1,&temp[0]);
multieva_solve(bg,ed,&temp[0],1,op);
}
} f,g;
//多个多项式相乘
template<class T>
inline poly multi(T bg,T ed) {
//含左边界,不含右边界
if(bg+1==ed)return *bg;
return multi(bg,bg+((ed-bg)>>1))*multi(bg+((ed-bg)>>1),ed);
}
}
using namespace Poly;
bool vis[3002][1502];
int x=1500,y=0,n,m,k;
inline char orz(){
char ch=getchar();
while(ch!='0'&&ch!='1'&&(ch<'a'||ch>'z'))ch=getchar();
return ch;
}
int main() {
// freopen("data.txt","r",stdin);
NTT_set(20500000);
cin>>n>>m>>k;
g.resize((n+1505)*m*2);
f.resize(g.size());
for(auto &i:f.a)i=1;
F(i,1,n)F(j,1,m){
f[i*m*2+j+m]=orz()-'0';
}
g[x*m*2+y]=1;
F(i,1,k){
char ch=orz();
if(ch=='a')++y;
else if(ch=='d')--y;
else if(ch=='w')++x;
else --x;
g[x*m*2+y]=1;
}
f=f*g;
int ans=0;
F(i,1500+1,1500+n)F(j,1,m){
ans+=(f[i*m*2+j+m]==0);
// if(f[i*m*2+j]==0)cerr<<i-1500<<" "<<j<<endl;
}
cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 145ms
memory: 135120kb
input:
5 5 5 00000 10000 00000 00000 01001 awdsw
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 666ms
memory: 255344kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
77549
result:
ok single line: '77549'
Test #3:
score: 0
Accepted
time: 658ms
memory: 255240kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #4:
score: 0
Accepted
time: 666ms
memory: 255268kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #5:
score: 0
Accepted
time: 619ms
memory: 255284kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #6:
score: 0
Accepted
time: 742ms
memory: 255420kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #7:
score: 0
Accepted
time: 2544ms
memory: 560100kb
input:
1000 1000 300000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
83496
result:
ok single line: '83496'
Test #8:
score: 0
Accepted
time: 2551ms
memory: 559996kb
input:
1000 1000 1000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
63001
result:
ok single line: '63001'
Test #9:
score: 0
Accepted
time: 2569ms
memory: 560024kb
input:
1000 1000 1500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
62500
result:
ok single line: '62500'
Test #10:
score: 0
Accepted
time: 5642ms
memory: 965760kb
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
141376
result:
ok single line: '141376'
Test #11:
score: 0
Accepted
time: 5217ms
memory: 965872kb
input:
1500 1500 5000000 100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110...
output:
22801
result:
ok single line: '22801'
Test #12:
score: 0
Accepted
time: 138ms
memory: 135008kb
input:
2 2 4 00 01 dada
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 5400ms
memory: 965664kb
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
141376
result:
ok single line: '141376'
Test #14:
score: 0
Accepted
time: 5082ms
memory: 965780kb
input:
1500 1500 2250 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
140625
result:
ok single line: '140625'
Test #15:
score: 0
Accepted
time: 187ms
memory: 148160kb
input:
50 60 20 000000000000000000000000010000000000000000000010000000000000 000000000000000000000000000000000000000000000000010000000000 000000000000000000000000000000000000000000010000000000001000 000000000000000000000000000000000100000000000000010000000000 00000000010000000000000000000000000000000000000...
output:
1633
result:
ok single line: '1633'
Test #16:
score: 0
Accepted
time: 192ms
memory: 147356kb
input:
60 50 500 00000000000000000000001000000000000000000100000000 00000000000000000000000010000000001000000000000000 00000000000000000000000000000000000000000000100000 00000000000000000000000000001000000000000010000000 00000000010000000000000000000000000000000000000000 00000000000000000000000000000000000...
output:
3
result:
ok single line: '3'
Test #17:
score: 0
Accepted
time: 720ms
memory: 255332kb
input:
500 500 500000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15876
result:
ok single line: '15876'
Test #18:
score: 0
Accepted
time: 769ms
memory: 257360kb
input:
500 500 500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
228475
result:
ok single line: '228475'
Test #19:
score: 0
Accepted
time: 719ms
memory: 255260kb
input:
500 500 1000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
53530
result:
ok single line: '53530'
Test #20:
score: 0
Accepted
time: 698ms
memory: 255312kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 669ms
memory: 255336kb
input:
500 500 100000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
9699
result:
ok single line: '9699'