fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int NUM=2000+10;
  27. const int INF=2000000000;
  28.  
  29. int m,n;
  30. int a[NUM];
  31. int f[NUM][NUM],sum[NUM];
  32. //f[i][j]=f[k][j-1] + sum[k][j-1]-sum[i][j]
  33.  
  34. void update(int& a,int b)
  35. {
  36. 	if(b==-1)
  37. 		return;
  38. 	if(a==-1 || b<a)
  39. 		a=b;
  40. }
  41.  
  42. int calc(int a,int b)
  43. {
  44. 	return sum[b]-sum[a-1]+b-a;
  45. }
  46.  
  47. int main()
  48. {
  49. 	int i,j;
  50. 	scanf("%d%d",&m,&n);
  51. 	REP(i,1,n)
  52. 	{
  53. 		cin>>a[i];
  54. 		sum[i]=sum[i-1]+a[i];
  55. 	}
  56. 	memset(f,-1,sizeof f);
  57. 	REP(i,1,n)
  58. 		if(calc(1,i)<=m)
  59. 			f[1][i]=0;
  60. 	REP(i,2,n)
  61. 	{
  62. 		int l=i-1,mm=INF;
  63. 		REP(j,i,n)
  64. 		{
  65. 			int Me=calc(i,j);
  66. 			if(Me>m)
  67. 				break;
  68. 			for(;l>=1 && calc(l,i-1)<=Me;--l)
  69. 				if(f[l][i-1]!=-1)
  70. 					mm=min(f[l][i-1]-calc(l,i-1),mm);
  71. 			if(mm==INF)
  72. 				continue;
  73. 			update(f[i][j],mm+Me);
  74. 		}
  75. 		l=1,mm=INF;
  76. 		for(j=n;j>=i;--j)
  77. 		{
  78. 			int Me=sum[j]-sum[i-1]+j-i;
  79. 			if(Me>m)
  80. 				continue;
  81. 			for(;l<=i-1 && calc(l,i-1)>=Me;++l)
  82. 				if(f[l][i-1]!=-1)
  83. 					mm=min(f[l][i-1]+calc(l,i-1),mm);
  84. 			if(mm==INF)
  85. 				continue;
  86. 			update(f[i][j],mm-Me);
  87. 		}
  88. 	}
  89. 	int ans=-1;
  90. 	REP(i,1,n)
  91. 		update(ans,f[i][n]);
  92. 	printf("%d\n",ans);
  93. 	return 0;
  94. }
Success #stdin #stdout 0.02s 19144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/Ra35z0
POI 13 est
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!