fork download
copy 
  1. #include <stdio.h>
  2.  
  3. int find_index(int target, int ps[], int ptrs[], int n){
  4.   int cur=ps[ptrs[n]]-ps[0];
  5.   while(cur<target){
  6.     ptrs[n]++;
  7.     cur=ps[ptrs[n]]-ps[0];
  8.   }
  9.   return ptrs[n];
  10. }
  11.  
  12. int find_window(int d, int min, int ps[], int ptrs[]){
  13.   int cur=ps[ptrs[d]+d-1]-ps[ptrs[d]-1];
  14.   while(cur<=min){
  15.     ptrs[d]++;
  16.     cur=ps[ptrs[d]+d-1]-ps[ptrs[d]-1];
  17.   }
  18.   return ptrs[d];
  19. }
  20.  
  21. int main(void){
  22.   int a1, a2, n, i;
  23.   int args = scanf("%d %d %d",&a1, &a2, &n);
  24.   if (args != 3)
  25.     printf("Failed to read input.\n");
  26.  
  27.   int a[n];
  28.   a[0]=a1;
  29.   a[1]=a2;
  30.  
  31.   int ps[n+1];
  32.   ps[0]=0;
  33.   ps[1]=a[0];
  34.   ps[2]=a[0]+a[1];
  35.   for (i=3; i<n+1; i++)
  36.     ps[i] = 1000000;
  37.  
  38.   int ptrs[n+1];
  39. for(i=0;i<n+1;i++)
  40.     ptrs[i]=1;
  41.  
  42.   for(i=2;i<n;i++){
  43.     int target=a[i-1]+1;
  44.     int max_len=find_index(target,ps, ptrs, n);
  45.     int cur=ps[max_len]-ps[0];
  46.     int best=cur;
  47.  
  48.     for(int d=max_len-1;d>1;d--){
  49.       int l=find_window(d, a[i-1], ps, ptrs);
  50.       int cur=ps[l+d-1]-ps[l-1];
  51.  
  52.       if(cur==target){
  53.         best=cur;
  54.         break;
  55.       }
  56.  
  57.       if(cur>a[i-1]&&cur<best)
  58.         best=cur;
  59.     }
  60.     a[i]=best;
  61.     ps[i+1]=a[i]+ps[i];
  62.   }
  63.  
  64.   printf("%d",a[n-1]);
  65. }
  66.  
  67.  
Success #stdin #stdout 0.04s 10472KB
comments (?)
stdin
copy 
2 3 100000
stdout
copy 
101856
https://ideone.com/wN5fGm
language:
C (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!