fork download
copy 
  1. /*
  2. *DIV 2 C.
  3. *LINK:
  4. *nilabja10201992
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define inf (1<<30)
  10. #define INF (int)1e9
  11. #define EPS 1e-9
  12. #define PI 3.1415926535897932384626433832795
  13. #define MOD 1000000007
  14. #define MAX 1000000
  15.  
  16. #define write(x) freopen(x,"w",stdout);
  17. #define read(x) freopen(x,"r",stdin);
  18. #define D(x)        cerr << #x " = " << (x) <<endl;
  19.  
  20. inline int setBit(int N, int pos) { return N = N | (1<<pos);}
  21. inline int resetBit(int N, int pos) { return N = N & ~(1<<pos);}
  22. inline bool checkBit(int N, int pos) { return (bool) (N & ( 1<<pos));}
  23.  
  24. //int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
  25. //int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};
  26.  
  27. typedef long long ll;
  28. typedef unsigned long long ui64;
  29. typedef string st;
  30. typedef long long int lli;
  31. typedef vector<int> vi;
  32. typedef vector<st> vs;
  33. typedef map<int,int> mii;
  34. typedef map<st,int> msi;
  35. typedef set<int> si;
  36. typedef set<st> ss;
  37. typedef pair<int,int> pii;
  38. typedef vector<pii> vpii;
  39. typedef vector<ll> vll;
  40. int arr[110];
  41. pair<int,int> dp[110][110];
  42. pii f(int i,int j){
  43. 	if(i==j)
  44. 		return dp[i][j]={arr[j],0};
  45.  
  46. 	if(dp[i][j].first!=-1 && dp[i][j].second!=-1)
  47. 		return dp[i][j];
  48. 		dp[i][j]={INT_MAX,INT_MAX};
  49. 	//	cout<<dp[i][j].first<<" "<<dp[i][j].second<<" ";
  50. 		for(int k=i;k<j;k++){
  51. 			pii val1=f(i,k);
  52. 			pii val2=f(k+1,j);
  53. 			if(dp[i][j].second>val1.second + val2.second + val1.first*val2.first){
  54. 				dp[i][j].first = (val1.first + val2.first)%100;
  55. 				dp[i][j].second = val1.second + val2.second + val1.first*val2.first;
  56. 			}
  57. 		}
  58. 	//	cout<<dp[i][j].first<<" "<<dp[i][j].second<<" ";
  59. 			return dp[i][j];
  60. }
  61. int main() {
  62.       ios_base::sync_with_stdio(false);
  63.       cin.tie(NULL);
  64. 	int n;
  65. 	while(cin>>n){
  66. 		memset(dp,-1,sizeof(dp));
  67. 		memset(arr,0,sizeof(arr));
  68. 		for(int i=0;i<n;i++)
  69. 			cin>>arr[i];
  70. 	//	cout<<dp[0]<<endl;
  71. 		cout<<f(0,n-1).second<<endl;
  72. 	/*	for(int i=0;i<n;i++){
  73. 			for(int j=0;j<n;j++)
  74. 				cout<<dp[i][j].first<<" "<<dp[i][j].second<<" ";
  75. 			cout<<endl;
  76. 		}*/
  77. 	//	cout<<dp[0][n-1].second<<endl;
  78. 	}
  79. 	//cout<<"Execution time : "<<tick();
  80.       return 0;
  81. }
  82.  
Success #stdin #stdout 0s 16160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HCzOzt
problem MIXTURES, based on SPOJ submission 18858095 (CPP14), 2017-02-27 18:52:24
language:
C++14 (gcc 8.3)
created:
7 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!