Submission #100978

#TimeUsernameProblemLanguageResultExecution timeMemory
100978KLPP새로운 문제 (COCI19_akvizna)C++14
20 / 130
1565 ms24848 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int lld; double DP[3001][3001]; int oper; void compute(int level,int lo_i,int hi_i, int lo_j, int hi_j){ if(lo_i>hi_i)return; oper+=hi_j-max(lo_j,level-1)+1; //cout<<level<<" "<<lo_i<<" "<<hi_i<<" "<<lo_j<<" "<<hi_j<<endl; int mid=(lo_i+hi_i); DP[mid][level]=0; int opt=-1; for(int i=max(lo_j,level-1);i<=hi_j && i<mid;i++){ if(DP[mid][level]<DP[i][level-1]+(double)(mid-i)/(mid)){ DP[mid][level]=DP[i][level-1]+(double)(mid-i)/(mid); opt=i; } //DP[mid][level]=max(DP[mid][level],DP[i][level-1]+(double)(mid-i)/(mid)); } compute(level,lo_i,mid-1,lo_j,opt); compute(level,mid+1,hi_i,opt,hi_j); } int main(){ int n,k; scanf("%d %d",&n,&k); for(int i=0;i<=n;i++)DP[i][0]=0; for(int i=1;i<=n;i++){ /* for(int j=1;j<=k && j<=i;j++){ DP[i][j]=0; //cout<<i<<" A "<<j<<endl; for(int l=j-1;l<i;l++){ double d=(double)(i-l)/i; //cout<<l<<" "<<d<<endl; DP[i][j]=max(DP[i][j],DP[l][j-1]+d); } //printf("%lf ",DP[i][j]); //cout<<endl; }//printf("\n");*/ } for(int i=1;i<=k;i++){oper=0; compute(i,0,n,0,n); //cout<<i<<" "<<oper<<endl; } printf("%.10lf\n",DP[n][k]); return 0; }

Compilation message (stderr)

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