Advertisement
Guest User

Untitled

a guest
Mar 25th, 2015
400
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. /*
  2. */
  3.  
  4. //#pragma comment(linker, "/STACK:16777216")
  5. #include <fstream>
  6. #include <iostream>
  7. #include <string>
  8. #include <complex>
  9. #include <math.h>
  10. #include <set>
  11. #include <vector>
  12. #include <map>
  13. #include <queue>
  14. #include <stdio.h>
  15. #include <stack>
  16. #include <algorithm>
  17. #include <list>
  18. #include <ctime>
  19. #include <memory.h>
  20. #include <ctime>
  21.  
  22. #define y0 sdkfaslhagaklsldk
  23. #define y1 aasdfasdfasdf
  24. #define yn askfhwqriuperikldjk
  25. #define j1 assdgsdgasghsf
  26. #define tm sdfjahlfasfh
  27. #define lr asgasgash
  28.  
  29. #define eps 1e-9
  30. //#define M_PI 3.141592653589793
  31. #define bs 1000000007
  32. #define bsize 256
  33. #define right adsgasgadsg
  34. #define free adsgasdg
  35. #define count adsgasdgasdg
  36.  
  37. using namespace std;
  38.  
  39. long n;
  40. long iterations;
  41.  
  42. vector<long> g[1<<20];
  43. long sub[1<<20];
  44. long k;
  45.  
  46. void dfs(long v)
  47. {
  48. vector<long> sons;
  49. for (int i=0;i<g[v].size();i++)
  50. {
  51. long id=g[v][i];
  52. dfs(id);
  53. sons.push_back(id);
  54. }
  55.  
  56. for (int i=0;i<sons.size();i++)
  57. {
  58. iterations+=k*sub[v];
  59. sub[v]+=sub[sons[i]];
  60. if (sub[v]>k)sub[v]=k;
  61. }
  62. sub[v]++;
  63. }
  64.  
  65. int main(){
  66. //freopen("k.in","r",stdin);
  67. //freopen("k.out","w",stdout);
  68. //freopen("C:/input.txt","r",stdin);
  69. //freopen("C:/output.txt","w",stdout);
  70. ios_base::sync_with_stdio(0);
  71. //cin.tie(0);
  72.  
  73. cin>>n;
  74. cin>>k;
  75.  
  76. for (int i=1;i<=k;i++)
  77. {
  78. g[i].push_back(i+1);
  79. }
  80.  
  81. for (int i=k+2;i<=n;i++)
  82. {
  83. g[1].push_back(i);
  84. }
  85.  
  86. dfs(1);
  87.  
  88. cout<<iterations<<endl;
  89. /*
  90. for (int i=1;i<=n;i++)
  91. cout<<sub[i]<<" ";*/
  92.  
  93. cin.get();cin.get();
  94. return 0;}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement