fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MAXD 1001
  3. #define TEST 1550
  4.  
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC optimize("inline")
  7. #pragma GCC optimize("-ffast-math")
  8. #pragma GCC optimize("unroll-loops")
  9. #pragma GCC optimize("inline-small-functions")
  10. #pragma GCC optimize("-finline-small-functions")
  11. #pragma GCC optimize("-fexpensive-optimizations")
  12. //#pragma GCC optimize("-funsafe-loop-optimizations")
  13. #pragma GCC optimize("inline-functions-called-once")
  14. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")?
  15.  
  16. using namespace std;
  17.  
  18. int C, D, Y;
  19. int M[MAXD], P[MAXD], total, optimal[TEST];
  20.  
  21. inline int get_int()
  22. {
  23.     int n = 0; 
  24.     char c = getchar_unlocked();
  25.     while(c >= '0')
  26.     {
  27.         n = 10*n+c-'0';
  28.         c = getchar_unlocked();
  29.     }
  30.  
  31.     return n;
  32. }
  33.  
  34. int main()
  35. {
  36.     //freopen("input.txt", "r", stdin);
  37.     //freopen("output.txt", "w", stdout);
  38.  
  39.     int n = 0; 
  40.     char c = getchar_unlocked();
  41.     while(c >= '0')
  42.     {
  43.         n = 10*n+c-'0';
  44.         c = getchar_unlocked();
  45.     }
  46.     C = n;
  47.  
  48.     n = 0; 
  49.     c = getchar_unlocked();
  50.     while(c >= '0')
  51.     {
  52.         n = 10*n+c-'0';
  53.         c = getchar_unlocked();
  54.     }
  55.     D = n;
  56.  
  57.  
  58.     n = 0; 
  59.     c = getchar_unlocked();
  60.     while(c >= '0')
  61.     {
  62.         n = 10*n+c-'0';
  63.         c = getchar_unlocked();
  64.     }
  65.     Y = n;
  66.  
  67.     for(int i = 1; i <= D; i++)
  68.     {
  69.         n = 0; 
  70.     c = getchar_unlocked();
  71.     while(c >= '0')
  72.     {
  73.         n = 10*n+c-'0';
  74.         c = getchar_unlocked();
  75.     }
  76.         M[i] = n;
  77.     }
  78.  
  79.     for(int i = 1; i <= D; i++)
  80.     {
  81.         n = 0; 
  82.     c = getchar_unlocked();
  83.     while(c >= '0')
  84.     {
  85.         n = 10*n+c-'0';
  86.         c = getchar_unlocked();
  87.     }
  88.         P[i] = n;
  89.     }
  90.  
  91.     D = min(D, Y);
  92.  
  93.         //fill_optimal
  94.  
  95.         for(int i = 1; i <= D; i++)
  96.         {
  97.             total += M[i]+P[i-1]-P[i];
  98.             int minimo = total+C;  
  99.             for(int j = 1; j <= i/2; j++)
  100.                 minimo = fmin(minimo, optimal[j]+optimal[i-j]);
  101.  
  102.             optimal[i] = minimo;
  103.              printf("%d", minimo);
  104.         }
  105.         for(int i = D+1; i <= TEST; i++)
  106.         {
  107.             int minimo = optimal[1]+optimal[i-1];
  108.             for(int j = 2; j <= i/2; j++)
  109.                 minimo = min(minimo, optimal[j]+optimal[i-j]);
  110.  
  111.             optimal[i] = minimo;
  112.         }
  113.  
  114.     int minimo = Y*optimal[1];
  115.  
  116.     for(int i = 2; i <= TEST; i++)
  117.         minimo = min(minimo, Y/i*optimal[i] + optimal[Y%i]);
  118.  
  119.     printf("%d", minimo); 
  120. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
10 5 6
1 2 2 5 2
5 4 3 5 4
stdout
copy 
6912151824
https://ideone.com/UxfZL7
language:
C++ (gcc 8.3)
created:
2 days 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!