Submission #100986

#	Time	Username	Problem	Language	Result	Execution time	Memory
100986		KLPP	새로운 문제 (COCI19_akvizna)	C++14	65 / 130	1570 ms	1024 KiB

Main

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
double DP[1000001];
int partitions[1000001];
int main(){
  int n,k;
  scanf("%d %d",&n,&k);
  double lo,hi;
  lo=-1000000;
  hi=1000000;
  while(hi-lo>1E-12){
    double mid=(hi+lo)/2;
    DP[0]=0;
    partitions[0]=0;
    for(int i=1;i<=n;i++){
      DP[i]=-10000000000000;
      for(int j=0;j<i;j++){
	if(DP[i]<DP[j]+(double)(i-j)/i+mid){
	  partitions[i]=partitions[j]+1;
	  DP[i]=DP[j]+(double)(i-j)/i+mid;
	}
      }
    }
    //for(int i=0;i<=n;i++)cout<<partitions[i]<<" ";
    //cout<<endl;
    //cout<<lo<<" "<<hi<<" "<<endl;
    if(partitions[n]<k){
      lo=mid;
    }else hi=mid;
  }
  //printf("%lf %lf\n",lo,hi);
  DP[0]=0;
  partitions[0]=0;
  for(int i=1;i<=n;i++){
     DP[i]=-10000000000000;
     for(int j=0;j<i;j++){
       if(DP[i]<DP[j]+(double)(i-j)/i+lo){
	 partitions[i]=partitions[j]+1;
	 DP[i]=DP[j]+(double)(i-j)/i+lo;
       }
    }
  }
  //cout<<DP[n]<<endl;
  printf("%.10lf\n",DP[n]-k*lo);
  return 0;
}

Compilation message (stderr)

akvizna.cpp: In function 'int main()':
akvizna.cpp:9:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&k);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5
• Subtask 24: 0 / 5
• Subtask 25: 0 / 5
• Subtask 26: 0 / 5