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.             optimal[i] = minimo;
  102.         }
  103.         for(int i = D+1; i <= TEST; i++)
  104.         {
  105.             int minimo = optimal[1]+optimal[i-1];
  106.             for(int j = 2; j <= i/2; j++)
  107.                 minimo = min(minimo, optimal[j]+optimal[i-j]);
  108.               printf("%d", minimo,' '); 
  109.             optimal[i] = minimo;
  110.         }
  111.  
  112.     int minimo = Y*optimal[1];
  113.  
  114.     for(int i = 2; i <= TEST; i++)
  115.         minimo = min(minimo, Y/i*optimal[i] + optimal[Y%i]);
  116.  
  117.     printf("%d", minimo); 
  118. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10 5 6
1 2 2 5 2
5 4 3 5 4
stdout
copy 
24273033364245485154606366697278818487909699102105108114117120123126132135138141144150153156159162168171174177180186189192195198204207210213216222225228231234240243246249252258261264267270276279282285288294297300303306312315318321324330333336339342348351354357360366369372375378384387390393396402405408411414420423426429432438441444447450456459462465468474477480483486492495498501504510513516519522528531534537540546549552555558564567570573576582585588591594600603606609612618621624627630636639642645648654657660663666672675678681684690693696699702708711714717720726729732735738744747750753756762765768771774780783786789792798801804807810816819822825828834837840843846852855858861864870873876879882888891894897900906909912915918924927930933936942945948951954960963966969972978981984987990996999100210051008101410171020102310261032103510381041104410501053105610591062106810711074107710801086108910921095109811041107111011131116112211251128113111341140114311461149115211581161116411671170117611791182118511881194119712001203120612121215121812211224123012331236123912421248125112541257126012661269127212751278128412871290129312961302130513081311131413201323132613291332133813411344134713501356135913621365136813741377138013831386139213951398140114041410141314161419142214281431143414371440144614491452145514581464146714701473147614821485148814911494150015031506150915121518152115241527153015361539154215451548155415571560156315661572157515781581158415901593159615991602160816111614161716201626162916321635163816441647165016531656166216651668167116741680168316861689169216981701170417071710171617191722172517281734173717401743174617521755175817611764177017731776177917821788179117941797180018061809181218151818182418271830183318361842184518481851185418601863186618691872187818811884188718901896189919021905190819141917192019231926193219351938194119441950195319561959196219681971197419771980198619891992199519982004200720102013201620222025202820312034204020432046204920522058206120642067207020762079208220852088209420972100210321062112211521182121212421302133213621392142214821512154215721602166216921722175217821842187219021932196220222052208221122142220222322262229223222382241224422472250225622592262226522682274227722802283228622922295229823012304231023132316231923222328233123342337234023462349235223552358236423672370237323762382238523882391239424002403240624092412241824212424242724302436243924422445244824542457246024632466247224752478248124842490249324962499250225082511251425172520252625292532253525382544254725502553255625622565256825712574258025832586258925922598260126042607261026162619262226252628263426372640264326462652265526582661266426702673267626792682268826912694269727002706270927122715271827242727273027332736274227452748275127542760276327662769277227782781278427872790279627992802280528082814281728202823282628322835283828412844285028532856285928622868287128742877288028862889289228952898290429072910291329162922292529282931293429402943294629492952295829612964296729702976297929822985298829942997300030033006301230153018302130243030303330363039304230483051305430573060306630693072307530783084308730903093309631023105310831113114312031233126312931323138314131443147315031563159316231653168317431773180318331863192319531983201320432103213321632193222322832313234323732403246324932523255325832643267327032733276328232853288329132943300330333063309331233183321332433273330333633393342334533483354335733603363336633723375337833813384339033933396339934023408341134143417342034263429343234353438344434473450345334563462346534683471347434803483348634893492349835013504350735103516351935223525352835343537354035433546355235553558356135643570357335763579358235883591359435973600360636093612361536183624362736303633363636423645364836513654366036633666366936723678368136843687369036963699370237053708371437173720372337263732373537383741374437503753375637593762376837713774377737803786378937923795379838043807381038133816382238253828383138343840384338463849385238583861386438673870387638793882388538883894389739003903390639123915391839213924393039333936393939423948395139543957396039663969397239753978398439873990399339964002400540084011401440204023402640294032403840414044404740504056405940624065406840744077408040834086409240954098410141044110411341164119412241284131413441374140414641494152415541584164416741704173417641824185418841914194420042034206420942124218422142244227423042364239424242454248425442574260426342664272427542784281428442904293429642994302430843114314431743204326432943324335433843444347435043534356436243654368437143744380438343864389439243984401440444074410441644194422442544284434443744404443444644524455445844614464447044734476447944824488449144944497450045064509451245154518452445274530453345364542454545484551455445604563456645694572457845814584458745904596459946024605460846144617462046234626463246354638464146444650465346564659466246684671467446774680468646894692469546984704470747104713471647224725472847314734474047434746474947524758476147644767477047764779478247854788479447974800480348064812481548184821482448304833483648394842484848514854485748604866486948724875487848844887489048934896490249054908491149144920492349264929493249384941494449474950495649594962496549684974497749804983498649924995499850015004501050135016501950225028503150345037504050465049505250555058506450675070507350765082508550885091509451005103510651095112511851215124512751305136513951425145514851545157516051635166517251755178518151845190519351965199520252085211521452175220522652295232523552385244524752505253525652625265526852715274528052835286528952925298530153045307531053165319532253255328533453375340534353465352535553585361536453705373537653795382538853915394539754005406540954125415541854245427543054335436544254455448545154545460546354665469547254785481548454875490549654995502550555085514551755205523552655325535553855415544555055535556555955625568557155745577558024
https://ideone.com/UPhd7d
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!