oj.uz

Submission #100986

# Submission time Handle Problem Language Result Execution time Memory
100986 2019-03-15T18:37:22 Z KLPP Akvizna (COCI19_akvizna) C++14
65 / 130
 1500 ms 1024 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 508 KB Output is correct
2 Correct 603 ms 412 KB Output is correct
3 Correct 627 ms 504 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 384 KB Output is correct
2 Correct 657 ms 504 KB Output is correct
3 Correct 554 ms 504 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 400 KB Output is correct
2 Correct 401 ms 504 KB Output is correct
3 Correct 475 ms 504 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 384 KB Output is correct
2 Correct 552 ms 504 KB Output is correct
3 Correct 433 ms 504 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 384 KB Output is correct
2 Correct 525 ms 384 KB Output is correct
3 Correct 628 ms 384 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 504 KB Output is correct
2 Correct 581 ms 512 KB Output is correct
3 Correct 525 ms 384 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 384 KB Output is correct
2 Correct 607 ms 384 KB Output is correct
3 Correct 524 ms 504 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 504 KB Output is correct
2 Correct 536 ms 404 KB Output is correct
3 Correct 442 ms 384 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 504 KB Output is correct
2 Correct 549 ms 504 KB Output is correct
3 Correct 529 ms 504 KB Output is correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 1024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1546 ms 1020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1546 ms 888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1570 ms 936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1561 ms 868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1559 ms 976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1565 ms 924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1556 ms 1016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1566 ms 1024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #25
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #26
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1559 ms 928 KB Time limit exceeded
2 Halted 0 ms 0 KB -