Submission #1817988
Source Code Expand
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP priority_queue
#define heap(T) priority_queue<T,vector<T>,greater<T> >
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
const int BufferSize=1<<25;
char buffer[BufferSize],*Bufferhead,*Buffertail;
int Terminal;
inline char Getchar(){
if(Bufferhead==Buffertail){
int l=fread(buffer,1,BufferSize,stdin);
if(!l){Terminal=1;return 0;}
Buffertail=(Bufferhead=buffer)+l;
}
return *Bufferhead++;
}
template<class T> inline bool read(T &x){
x=0;char c=Getchar(),rev=0;
while(c<'0'||c>'9'){c=Getchar();rev|=c=='-';if(Terminal)return 0;}
while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
x=rev?-x:x;
return 1;
}
template<class T>inline void print(T x,const char c){
if(!x){putchar('0');putchar(c);return;}
if(x<0) putchar('-'),x=-x;
int m=0,a[10];
while(x) a[m++]=x%10,x/=10;
while(m--) putchar(a[m]+'0');
putchar(c);
}
//--------------------------------------head--------------------------------------
const int inf=0x3f3f3f3f;
const int N=100005,M=100005,mod=1e9+7;
inline void ch(int &x,int y){x=(x+y)%mod;}
inline int exp(int x,int y,int mod=::mod){
int ans=1;
while(y){
if(y&1) ans=(ll)ans*x%mod;
x=(ll)x*x%mod;y>>=1;
}return ans;
}
int n,dp[2][33];
int main(){
scanf("%d",&n);
clr(dp,0x3f);
dp[0][0]=0;
for(int i=1;i<=n;i++){
int x,maxx=0;scanf("%d",&x);
while((1<<maxx)<x) maxx++;
int L=maxx,R=maxx;
if((1<<maxx)!=x) L--;
//printf("%d %d\n",L,R);
for(int j=0;j<=30;j++)
dp[i&1][j]=inf;
for(int j=0;j<=30;j++){
gmin(dp[i&1][R],dp[i-1&1][j]+maxx-min(L,j));
gmin(dp[i&1][L],dp[i-1&1][j]+maxx-min(R,j));
}
}
int ans=inf;
for(int i=0;i<=30;i++)
gmin(ans,dp[n&1][i]);
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time
2017-11-30 18:50:04+0900
Task
F - Squeezing Slimes
User
rqgao2014
Language
C++14 (GCC 5.4.1)
Score
1600
Code Size
2397 Byte
Status
AC
Exec Time
26 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:68:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:72:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int x,maxx=0;scanf("%d",&x);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1600 / 1600
Status
Set Name
Test Cases
Sample
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt
Case Name
Status
Exec Time
Memory
0_00.txt
AC
1 ms
256 KB
0_01.txt
AC
1 ms
256 KB
0_02.txt
AC
1 ms
256 KB
0_03.txt
AC
1 ms
256 KB
1_00.txt
AC
1 ms
256 KB
1_01.txt
AC
1 ms
256 KB
1_02.txt
AC
19 ms
256 KB
1_03.txt
AC
25 ms
256 KB
1_04.txt
AC
22 ms
256 KB
1_05.txt
AC
26 ms
256 KB
1_06.txt
AC
26 ms
256 KB
1_07.txt
AC
26 ms
256 KB
1_08.txt
AC
26 ms
256 KB
1_09.txt
AC
26 ms
256 KB
1_10.txt
AC
26 ms
256 KB
1_11.txt
AC
26 ms
256 KB
1_12.txt
AC
26 ms
256 KB
1_13.txt
AC
26 ms
256 KB
1_14.txt
AC
26 ms
256 KB
1_15.txt
AC
26 ms
256 KB
1_16.txt
AC
26 ms
256 KB
1_17.txt
AC
26 ms
256 KB
1_18.txt
AC
26 ms
256 KB
1_19.txt
AC
26 ms
256 KB
1_20.txt
AC
26 ms
256 KB
1_21.txt
AC
23 ms
256 KB
1_22.txt
AC
24 ms
256 KB
1_23.txt
AC
23 ms
256 KB
1_24.txt
AC
24 ms
256 KB
1_25.txt
AC
24 ms
256 KB
1_26.txt
AC
23 ms
256 KB
1_27.txt
AC
23 ms
256 KB
1_28.txt
AC
24 ms
256 KB
1_29.txt
AC
24 ms
256 KB
1_30.txt
AC
24 ms
256 KB
1_31.txt
AC
23 ms
256 KB
1_32.txt
AC
24 ms
256 KB
1_33.txt
AC
24 ms
256 KB
1_34.txt
AC
23 ms
256 KB
1_35.txt
AC
23 ms
256 KB
1_36.txt
AC
23 ms
256 KB
1_37.txt
AC
23 ms
256 KB
1_38.txt
AC
24 ms
256 KB
1_39.txt
AC
24 ms
256 KB
1_40.txt
AC
24 ms
256 KB
1_41.txt
AC
24 ms
256 KB
1_42.txt
AC
24 ms
256 KB
1_43.txt
AC
24 ms
256 KB
1_44.txt
AC
24 ms
256 KB
1_45.txt
AC
23 ms
256 KB
1_46.txt
AC
24 ms
256 KB
1_47.txt
AC
24 ms
256 KB
1_48.txt
AC
24 ms
256 KB
1_49.txt
AC
24 ms
256 KB
1_50.txt
AC
24 ms
256 KB
1_51.txt
AC
23 ms
256 KB
1_52.txt
AC
24 ms
256 KB