結果
問題 | No.1096 Range Sums |
ユーザー | siumaidayo |
提出日時 | 2020-08-04 14:34:46 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 7,061 bytes |
コンパイル時間 | 503 ms |
コンパイル使用メモリ | 36,864 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 15:38:57 |
合計ジャッジ時間 | 1,422 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 19 ms
5,376 KB |
testcase_11 | AC | 19 ms
5,376 KB |
testcase_12 | AC | 18 ms
5,376 KB |
testcase_13 | AC | 19 ms
5,376 KB |
testcase_14 | AC | 19 ms
5,376 KB |
ソースコード
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<stdbool.h> #include<assert.h> #include<time.h> #include<ctype.h> typedef long long ll; typedef long double ld; #define rep(i,l,r)for(ll i=(l);i<(r);i++) #define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k)) #define rrep(i,l,r)for(ll i=(l);i>=(r);i--) #define INF (1LL<<62) #define MOD1 1000000007 #define MOD2 998244353 #define MAX_N (1 << 20) #define YES printf("Yes\n") #define NO printf("No\n") #define PN printf("\n") #define charsize 100005 //10^5+5 #define PI 3.141592653589793238 void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a= c;} void cin(ll *n){ scanf("%lld",&(*n)); } ll max2(ll a,ll b){return a>=b?a:b;} ll min2(ll a,ll b){return a>=b?b:a;} ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;} ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;} ll minn(ll n, ll a[]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;} ll maxn(ll n, ll a[]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;} ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;} double POW_d(double a, double b){double c=1;rep(i,0,b) c*=a;return c;} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll mod_MOD1(ll n){n+= n<0?((-n)/MOD1+1)*MOD1:0; return n%=MOD1;} ll mod_p(ll n ,ll p){n+= n<0?((-n)/p+1)*p:0; return n%=p;} ll change_into_num(char s[] , ll len, ll p){ return !p ? 0 : POW(10,p-1)*(s[len-p]-'0') + change_into_num(s,len,p-1); } ll digits(ll a, ll b){return a/b?1+digits(a/b,b):1;} ll base(ll n, ll a, ll i){return i==1?n%a:base(n/a,a,i-1);} ll is_inArr1(ll x, ll n){ return ( x<0 || x>=n ) ? 0 : 1 ; } ll is_inArr2(ll y, ll x, ll h, ll w){ return ( y<0 || y>=h || x<0 || x>=w ) ? 0 : 1 ; } void lr_lower( int *l, int *r, ll am, ll val , int type ){ (type<3) ? ( am < val ? ( *l = (*l+*r)/2 ) : ( *r= (*l+*r)/2 ) ) : ( am <= val ? ( *l = (*l+*r)/2 ) : ( *r= (*l+*r)/2 ) ); } void lr_upper( int *l, int *r, ll am, ll val , int type ){ (type<3) ? ( am <= val ? ( *l = (*l+*r)/2 ) : ( *r= (*l+*r)/2 ) ) : ( am < val ? ( *l = (*l+*r)/2 ) : ( *r= (*l+*r)/2 ) ); } int cmp_lower( ll a, ll b, int type ){ return (type==1) ? ( a==b ? 1 : 0 ) : (type==2) ? ( a>=b ? 1 : 0 ) : ( a>b ? 1 : 0 ) ; } int cmp_upper( ll a, ll b, int type ){ return (type==1) ? ( a==b ? 1 : 0 ) : (type==2) ? ( a<=b ? 1 : 0 ) : ( a<b ? 1 : 0 ) ; } // return smallest p which meets a[p]==val :1 >=:2 >:3 ll lower_bound( ll a[], int l, int r, ll val , int type ){ while(r-l>1) lr_lower(&l,&r,a[ (l+r)/2 ],val,type); return cmp_lower(a[l],val,type) ? l : cmp_lower(a[r],val,type) ? r : -1; } // return biggest p which meets a[p]==val :1 <=:2 <:3 ll upper_bound( ll a[], int l, int r, ll val , int type ){ while(r-l>1) lr_upper(&l,&r,a[ (l+r)/2 ],val,type); return cmp_upper(a[r],val,type) ? r : cmp_upper(a[l],val,type) ? l : -1; } // count i which meets ai==x ll count(ll a[], int l, int r, ll x){ int p = lower_bound(a,l,r,x,1); return p==-1 ? 0 : upper_bound(a,p,r,x,1)-p+1; } ll *factors[2] , fac_cnt=0 , is_factor_prepared=0; ll factor_pre(){ rep(i,0,1){ if(is_factor_prepared++) return 0; } ll tmp=(1e6)/2+1, fac_tmp[tmp]; rep(i,0,tmp){fac_tmp[i]=i?2*i+1:2;} rep(i,1,tmp){if(fac_tmp[i]){ repp(j,3,tmp/(2*i+1)+1,2 ){ if( j*(2*i+1)<tmp ) fac_tmp[ (j*(2*i+1)-1)/2 ]=0; } }else continue;} rep(i,0,tmp){if(fac_tmp[i]){ rep(j,0,2){ factors[j] = realloc( factors[j] , sizeof(ll)*( fac_cnt +1 ) ); factors[j][j?fac_cnt++:fac_cnt]=j?0:fac_tmp[i]; } } } return 0; } ll factor(ll n, ll new_common_plus){ factor_pre(); rep(i,0,fac_cnt){ ll cnt=0; rep(j,0,1){ while( ( cnt+= n %factors[0][i]==0 ? 1 : 0 ) && (n/=factors[0][i]) %factors[0][i]==0 ) continue; } factors[1][i]= new_common_plus==1 ? cnt : new_common_plus==2 ? max2(factors[1][i],cnt) : factors[1][i]+cnt ; if( factors[0][i]> n ) break; } return n; } ll judge_prime(ll n){ factor_pre(); rep(i,0,fac_cnt){ if(n<factors[0][i]*factors[0][i] || n==factors[0][i]) break; else if(n%factors[0][i]==0) n/=n; } return n==1?0:1; } ll *mf_arr,*inv_arr,*finv_arr,is_minv_made=0,is_mf_made=0,num_of_inv=2*1e6+10; ll makeinv(ll n , ll mod){ rep(i,0,1){if(is_minv_made++) return 0;} inv_arr = realloc(inv_arr, sizeof(ll)*2 ); finv_arr = realloc(finv_arr, sizeof(ll)*2 ); inv_arr[1]=1;finv_arr[0]=finv_arr[1]=1; rep(i,2,n+1){ inv_arr = realloc(inv_arr, sizeof(ll)*(i+1) ); finv_arr = realloc(finv_arr, sizeof(ll)*(i+1) ); inv_arr[i]= mod - inv_arr[mod%i] * (mod / i) % mod; finv_arr[i] = finv_arr[i - 1] * inv_arr[i] % mod; } return 0; } ll make_mf(ll n, ll mod){ rep(i,0,1){ if(is_mf_made++) return 0; } mf_arr = realloc(mf_arr, sizeof(ll)*2 ); ll x=1; mf_arr[0]=mf_arr[1]=x; rep(i,2,n+1){ x=x*i%mod; mf_arr = realloc(mf_arr, sizeof(ll)*(i+1) ); mf_arr[i]=x; } return 0; } ll m_inv(ll x, ll mod, ll is_fac ){ makeinv(num_of_inv,mod); return is_fac?finv_arr[x]:inv_arr[x]; } ll m_f(ll x, ll mod){ make_mf(num_of_inv,mod); return mf_arr[x]; } ll mod_nck(ll n, ll k, ll mod){ return m_f(n,mod)*m_inv(k,mod,1)%mod*m_inv(n-k,mod,1)%mod; } ll m_p(ll r,ll n,ll mod){ ll t=1,s=r; while(n>0){ t = (n&1) ? t*s%mod : t; s=s*s%mod; n>>=1; } return r?t:0; } ll m_mul2(ll a, ll b, ll mod){ return a*b%mod; } ll m_mul3(ll a, ll b, ll c, ll mod){ return m_mul2(a*b%mod,c,mod); } ll m_mul4(ll a, ll b, ll c, ll d, ll mod){ return m_mul3(a*b%mod,c,d,mod); } ll m_mul5(ll a, ll b, ll c, ll d, ll e, ll mod){ return m_mul4(a*b%mod,c,d,e,mod); } int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;} int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;} int cmp_string( const void * a , const void * b ) { return strcmp( (char *)a , (char *)b ); } // qsort((void*)s,n,sizeof(s[0]),int_sort ); int cmp_char(const void * a, const void * b) { return *(char *)a - *(char *)b;} void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);} void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);} void sort_string(int n,int size,char s[][size]){ qsort( (void*)s , n , sizeof(s[0]) , cmp_string ); } void sort_char(char *s){ qsort( (void *)s , strlen(s) , sizeof(char) , cmp_char ); } ll unique_string(ll n ,ll size, char s[][size]){ ll ans=1; rep(i,1,n) if( strcmp(s[i],s[i-1]) ) ans++; return ans; } ll unique_num(ll n , ll a[]){ ll ans=1; rep(i,1,n) if( a[i]!=a[i-1] ) ans++; return ans; } typedef struct{ ll a , b;}fr; int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;} int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;} void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);} void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);} char s[1151154]; int main(void){ // fgets(s,sizeof(s),stdin); ll n; ll ans=0; cin(&n); // scanf("%s",s); ll a; rep(i,0,n){ cin(&a); ans+=a*(n-i)*(i+1); } printf("%lld\n",ans); return 0; } /* while (ng + 1 < ok) { int p = ng + (ok - ng) / 2; int cnt = 0; for (i = 0; i < n; i++) { cnt += (a[i] + p - 1) / p - 1; } if (cnt <= k) ok = p; else ng = p; } */