fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. #include <ext/pb_ds/detail/standard_policies.hpp>
  6. using namespace __gnu_pbds;
  7. using namespace std;
  8.  
  9.  
  10. #define LETS_GET_SCHWIFTY ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
  11. #define ff              first
  12. #define ss              second
  13. #define int             long long
  14. #define ll              long long
  15. #define pb              push_back
  16. #define pii             pair<int,int>
  17. #define vi              vector<int>
  18. #define pqb             priority_queue<int>
  19. #define pqs             priority_queue<int,vi,greater<int> >
  20. #define setbits(x)      __builtin_popcountll(x)
  21. #define zerobits(x)      __builtin_ctzll(x)
  22. #define mod             998244353
  23. #define inf             1e18
  24. #define ps(x,y)         fixed<<setprecision(y)<<x
  25. #define vpii            vector<pair<int,int> >
  26. #define all(x)          x.begin(),x.end()
  27. #define matrixprint(arr,a,b,c,d) for(int i=a;i<=c;i++){for(int j=b;j<=d;j++){cout<<arr[i][j]<<" ";}cout<<"\n";}
  28. #define show(arr,x,y)   for(int i=x;i<=y;i++){cout<<arr[i]<<" ";}cout<<"\n"
  29. #define sz(x)           (int)x.size()
  30. #define db(x)           cout<<x<<"\n";
  31.  
  32. typedef tree<
  33. int,
  34. null_type,
  35. less<int>,
  36. rb_tree_tag,
  37. tree_order_statistics_node_update>
  38. ordered_set;
  39.  
  40. //insert,find_by_order,order_of_key,lower_bound,upper_bound;
  41.  
  42. #define TRACE
  43. #ifdef TRACE
  44. #define deb(...) __f(#__VA_ARGS__, __VA_ARGS__)
  45. template <typename Arg1>
  46. void __f(const char* name, Arg1&& arg1) {
  47.     cout << name << " : " << arg1 << std::endl;
  48. }
  49. template <typename Arg1, typename... Args>
  50. void __f(const char* names, Arg1&& arg1, Args&&... args) {
  51.     const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
  52. }
  53. #else
  54. #define deb(...)
  55. #endif
  56.  
  57.  
  58. //////////////////////////////code//////////////////////////////
  59.  
  60. const int N = 200;
  61.  
  62. int arr[22][22];
  63.  
  64. int n,m;
  65. int a,b,c,d,w;
  66.  
  67.  
  68. int sol(int x,int y)
  69. {
  70. 		int dp[n+1];
  71. 		dp[0] = 0;
  72.  
  73. 		for(int i = 1;i <= n; i++)
  74. 			dp[i] = inf;
  75.  
  76. 		for(int i = 1;i <= n; i++)
  77. 		{
  78. 				for(int j = 1; j <= i ;j++)
  79. 				{
  80. 						int cnt = 0,cost = 0;
  81.  
  82. 						for(int k = j; k <= i ;k++)
  83. 						{
  84. 								for(int l = x ; l <= y ; l++)
  85. 									if(arr[k][l])
  86. 										cnt++;
  87. 						}
  88.  
  89. 						if(cnt > 3)
  90. 							continue;
  91.  
  92. 						if(cnt == 0)
  93. 							cost += a;
  94. 						else if(cnt == 1)
  95. 							cost += b;
  96. 						else if(cnt == 2)
  97. 							cost += c;
  98. 						else
  99. 							cost += d;
  100.  
  101.                         if(j-1 != 0)
  102. 						cost += (y-x+1)*w;
  103.  
  104. 					  int curr1 = dp[j-1]+cost;
  105.  
  106.                      dp[i] = min(curr1,dp[i]);
  107.  
  108.  
  109. 				}
  110. 		}
  111.  
  112. 		return dp[n];
  113. }
  114.  
  115.  
  116. void solve()
  117. {
  118.  
  119. 	cin >> a >> b >> c >> d >> w;
  120. 	cin >> n >> m;
  121.  
  122.  
  123. 	for(int i = 1;i <= n; i++)
  124. 		for(int j = 1;j <= m; j++)
  125. 			cin >> arr[i][j];
  126.  
  127.     int dp[m+1];
  128.     dp[0] = 0;
  129.  
  130.     for(int i = 1;i <= m; i++)
  131.     	dp[i] = inf;
  132.  
  133.     for(int i = 1;i <= m; i++)
  134.     {
  135.     		for(int j = 1;j <= i; j++)
  136.     		{			
  137.     				int curr = dp[j-1]+sol(j,i);
  138.  
  139.     				if(j-1 != 0)
  140.     					curr += n*w;
  141.  
  142.     				dp[i] = min(curr,dp[i]);
  143.  
  144.  
  145.     		}
  146.     }
  147.  
  148.  
  149.     db(dp[m])
  150.  
  151.  
  152. }
  153.  
  154. int32_t main()
  155. {   
  156.  
  157.     LETS_GET_SCHWIFTY;
  158.  
  159.      #ifndef ONLINE_JUDGE
  160.      freopen("INP.txt", "r", stdin);
  161.      freopen("out.txt", "w", stdout);
  162.      #endif  
  163.  
  164.  
  165.     int t = 1;
  166.   // cin >> t;
  167.  
  168.     while (t--)
  169.         solve();
  170.  
  171. }
  172.  
  173. // check out for following mistakes-
  174. // if using pb operation on vector and then trying to access index..check if sizeof that vec could remain 0 only
  175. // is using prime sieve make sure it fits
  176. // when using factorial template or combinatorics make sure that you edit fillfac fun values and array values
  177.  
  178.  
Success #stdin #stdout 0s 4880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/InFQ4d
language:
C++14 (gcc 8.3)
created:
3 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!