fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ii pair <int , int>
  9. #define iii pair <int , ii>
  10. #define se second
  11. #define fi first
  12. #define all(v) (v).begin() , (v).end()
  13. #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
  14. #define bit(x,i) (((x) >> (i)) & 1LL)
  15. #define flip(x,i) ((x) ^ (1LL << (i)))
  16. #define ms(d,x) memset(d , x , sizeof(d))
  17. #define exist __exist
  18. #define ends __ends
  19. #define visit visited
  20. #define left __left
  21. #define right __right
  22. #define sitingfake 1
  23. #define orz 1
  24. //constant
  25.  
  26. const long long mod = 1e9 + 7;
  27. const long long linf = 4557430888798830399LL;
  28. const long long nlinf = -4485090715960753727LL;
  29. const int inf = 1061109567;
  30. const int ninf = -1044266559;
  31. const int dx[] = {0 , -1 , 0 , 1};
  32. const int dy[] = {-1 , 0 , 1 , 0};
  33.  
  34. template<typename T> bool maximize(T &a, const T &b)
  35. {
  36.     if(a < b) {a = b; return 1;}
  37.     return 0;
  38. }
  39.  
  40. template<typename T> bool minimize(T &a, const T &b)
  41. {
  42.     if(a > b) {a = b; return 1;}
  43.     return 0;
  44. }
  45.  
  46. void Plus(ll & a ,ll b)
  47. {
  48.     b %= mod;
  49.     a += b;
  50.     if(a < 0) a += mod;
  51.     a %= mod;
  52.     return;
  53. }
  54.  
  55. void Mul(ll & a, ll b)
  56. {
  57.     (a *= (b % mod)) %= mod;
  58.     return;
  59. }
  60.  
  61. //code
  62. const int maxn = 303;
  63.  
  64. int c[maxn][maxn];
  65.  
  66. int n , m;
  67.  
  68. ll dp[2][maxn];
  69.  
  70. void solve(void)
  71. {
  72.     cin >> n >> m;
  73.     for(int i = 1; i <= n; i++)
  74.     {
  75.         for(int j = 1; j <= m; j++)
  76.         {
  77.             cin >> c[i][j];
  78.         }
  79.         sort(c[i] + 1 , c[i] + m + 1);
  80.         for(int j = 1; j <= m; j++) c[i][j] += c[i][j - 1];
  81.     }
  82.     ms(dp , 0x3f);
  83.     dp[0][0] = 0;
  84.     for(int i = 1; i <= n; i++)
  85.     {
  86.         int cur = i & 1;
  87.         int pre = !cur;
  88.         ms(dp[cur] , 0x3f);
  89.         for(int j = 0; j <= min(n , m); j++)
  90.         {
  91.             for(int k = 0; k + j - 1 <= n; k++)
  92.             {
  93.                 if(j + k) minimize(dp[cur][j + k - 1] , dp[pre][k] + c[i][j] + 1ll * j * j);
  94.             }
  95.         }
  96.     }
  97.  
  98.     cout << dp[n & 1][0];
  99. }
  100. /**
  101. **/
  102. signed main()
  103. {
  104.    ios_base::sync_with_stdio(0);
  105.    cin.tie(0);
  106.    cout.tie(0);
  107.  
  108.    #define task "pie"
  109.  
  110.    if(fopen(task".inp","r"))
  111.    {
  112.        freopen(task".inp","r",stdin);
  113.        freopen(task".out","w",stdout);
  114.    }
  115.  
  116.    int tc = 1;
  117. //   cin >> tc;
  118.    while(tc--) solve();
  119.  
  120. //   execute;
  121. }
  122.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mxLCLE
language:
C++14 (clang 8.0)
created:
3 days 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!