fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <climits>
  5. #include <cstring>
  6. #include <utility>
  7. #include <vector>
  8. #include <string>
  9. #include <cstdio>
  10. #include <bitset>
  11. #include <ctime>
  12. #include <cmath>
  13. #include <stack>
  14. #include <list>
  15. #include <set>
  16. #include <map>
  17.  
  18. using namespace std;
  19.  
  20. #define sci stack <int>
  21. #define vci vector <int>
  22. #define vcs vector <string>
  23. #define vcd vector <double>
  24. #define vci64 vector <long long>
  25. #define seti set <int>
  26. #define mseti multiset <int>
  27.  
  28. const int maxn = 100 + 5;
  29. const int maxm = 2 + 5;
  30. const int maxk = 10 + 5;
  31.  
  32. typedef unsigned int uint;
  33. typedef long long int64;
  34. typedef unsigned long long uint64;
  35.  
  36. template <class T> inline T Sqr(const T & x) { return x * x; }
  37. template <class T> inline T Abs(const T & x) { return x > 0 ? x : -x; }
  38. template <class T> inline T Min(const T & a, const T & b) { return a < b ? a : b; }
  39. template <class T> inline T Max(const T & a, const T & b) { return a > b ? a : b; }
  40. template <class T> inline T Ksm(const T & a, const T & b, const T & m) { T _ = 1; for (; b; b >>= 1, a = a * a % m) (b & 1) ? _ = _ * a % m : 0; return _ % m; }
  41. template <class T> inline void Swap(T & a, T & b) { T _; _ = a; a = b; b = _; }
  42.  
  43. int n, m, K;
  44. int s[maxn], s1[maxn], s2[maxn];
  45. int g[maxn][maxk], f[maxn][maxn][maxk];
  46.  
  47. int getint()
  48. {
  49.    char ch = getchar(); int result = 0, res = 1;
  50.    for (; '0' > ch || ch > '9'; ch = getchar()) ch == '-' ? res = -1 : 0;
  51.    for (; '0' <= ch && ch <= '9'; result = result * 10 + ch - '0', ch = getchar());
  52.    return result * res;
  53. }
  54.  
  55. int main()
  56. {
  57. #ifndef ONLINE_JUDGE
  58.    freopen("matrix.in", "r", stdin);
  59.    freopen("matrix.out", "w", stdout);
  60. #endif
  61.  
  62.    if (n = getint(), m = getint(), K = getint(), m == 1)
  63.    {
  64.       for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + getint();
  65.       for (int i = 1; i <= n; ++i)
  66.          for (int j = 1; j <= K; ++j)
  67.          {
  68.             g[i][j] = g[i - 1][j];
  69.             for (int k = i - 1; k >= 0; --k)
  70.                g[i][j] = Max(g[i][j], g[k][j - 1] + s[i] - s[k]);
  71.          }
  72.       return printf("%d", g[n][K]), 0;
  73.    }
  74.  
  75.    for (int i = 1; i <= n; ++i) s1[i] = s1[i - 1] + getint(), s2[i] = s2[i - 1] + getint();
  76.    for (int i = 1; i <= n; ++i)
  77.       for (int j = 1; j <= n; ++j)
  78.          for (int k = 1; k <= K; ++k)
  79.          {
  80.             f[i][j][k] = Max(f[i - 1][j][k], f[i][j - 1][k]);
  81.             for (int x = i - 1; x >= 0; --x)
  82.                f[i][j][k] = Max(f[i][j][k], f[x][j][k - 1] + s1[i] - s1[x]);
  83.             for (int y = j - 1; y >= 0; --y)
  84.                f[i][j][k] = Max(f[i][j][k], f[i][y][k - 1] + s2[j] - s2[y]);
  85.             if (i == j) for (int x = i - 1; x >= 0; --x)
  86.                f[i][j][k] = Max(f[i][j][k], f[x][x][k - 1] + s1[i] - s1[x] + s2[j] - s2[x]);
  87.          }
  88.    return printf("%d", f[n][n][K]), 0;
  89. }
Success #stdin #stdout 0.01s 3336KB
comments (?)
stdin
copy 
3 2 2
1 -3
2 3
-2 3
stdout
copy 
9
https://ideone.com/z3wayL
language:
C++ (gcc 8.3)
created:
12 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!