2 solutions

  • 6
    @ 2024-12-21 15:54:43
    #include<bits/stdc++.h>
    using namespace std;
    int N,M,area,marea=1e9;
    void dfs(int v,int m,int r,int h){
    	if((m*(m-1)/2)*(m*(m-1)/2)>v||r<m||h<m)return;
    	if(m==0){
    		if(v==0)marea=min(marea,area);
    		return;
    	}
    	for(int rr=r;rr>=m;rr--){
    		if(m==M)area=rr*rr;
    		for(int hh=h;hh>=m;hh--){
    			int t=0;
    			for(int i=0;i<m;i++)t+=(r-i)*(r-i)*(h-i);
    			if(t<v)break;
    			area+=2*rr*hh;
    			if(area>=marea){area-=2*rr*hh;continue;}
    			dfs(v-rr*rr*hh,m-1,rr-1,hh-1);
    			area-=2*rr*hh;
    		}
    	}
    }
    int main(){
    	cin>>N>>M;
    	dfs(N,M,sqrt((N-(M*(M-1)/2)*(M*(M-1)/2))/M),(N-(M*(M-1)/2)*(M*(M-1)/2))/M/M);
    	if(marea==1e9)cout<<0;
    	else cout<<marea;
     	return 0;
    }
    
    
    • 0
      @ 2026-3-18 19:41:36
      #include<bits/stdc++.h>
      using namespace std;
      
      int n,m,ans=INT_MAX;
      int minv[25],mins[25];
      
      void dfs(int d,int r,int h,int v,int s){
          if(d==0){
              if(v==n) ans=min(ans,s);
              return;
          }
          if(v+minv[d]>n) return;
          if(s+mins[d]>=ans) return;
          
          int maxv=v;
          for(int i=1;i<=d;i++)
              maxv+=(r-i)*(r-i)*(h-i);
          if(maxv<n) return;
          
          for(int i=r-1;i>=d;i--){
              if(i*i>n-v) continue;
              for(int j=h-1;j>=d;j--){
                  if(v+i*i*j>n) continue;
                  if(s+2*i*j>=ans) continue;
                  dfs(d-1,i,j,v+i*i*j,s+2*i*j);
              }
          }
      }
      
      int main(){
          cin>>n>>m;
          
          for(int i=1;i<=m;i++){
              minv[i]=minv[i-1]+i*i*i;
              mins[i]=mins[i-1]+2*i*i;
          }
          
          for(int r=m;r*r<=n;r++){
              int maxh=(n-minv[m-1])/(r*r);
              for(int h=m;h<=maxh;h++){
                  dfs(m-1,r,h,r*r*h,2*r*h+r*r);
              }
          }
          
          if(ans==INT_MAX) ans=0;
          cout<<ans;
          return 0;
      }
      
      
      • 1

      Information

      ID
      20
      Time
      1000ms
      Memory
      512MiB
      Difficulty
      8
      Tags
      # Submissions
      105
      Accepted
      14
      Uploaded By