Submission #1085896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085896		Persia	Feast (NOI19_feast)	C++14	59 / 100	137 ms	262144 KiB

feast

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define rep2(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define bit(i, x) (x >> i & 1)

using namespace std;
const int N = 3e5 + 3;
const int mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long l, long long r) {
  return uniform_int_distribution<long long>(l, r)(rng);
}

int n, k, a[N];
long long p[N];

namespace sub1{
  long long sol() {
    vector<vector<long long>> dp(n + 3, vector<long long>(k + 3, 0));
    vector<vector<long long>> mx(n + 3, vector<long long>(k + 3, 0));
    rep(i, 1, n) {
      rep(j, 1, k) {
        dp[i][j] = max(dp[i - 1][j], mx[i - 1][j - 1] + p[i]);
        dp[i][j] = max(dp[i][j], dp[i][j - 1]);
//        rep(l, 0, i - 1) {
//          dp[i][j] = max(dp[i][j], dp[l][j - 1] + p[i] - p[l]);
//        }
      }
      mx[i][0] = max(mx[i - 1][0], -p[i]);
      rep(j, 1, k - 1) {
        mx[i][j] = max(mx[i - 1][j], dp[i][j] - p[i]);
      }
    }
//    rep(i, 1, n) {
//      rep(j, 1, k) cout << dp[i][j] << " ";
//      cout << "\n";
//    }
    return dp[n][k];
  }
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

  // freopen("testing.txt", "r", stdin);
//  freopen("outputing.txt", "w", stdout);

  cin >> n >> k;
  rep(i, 1, n) {
    cin >> a[i];
    p[i] = p[i - 1] + a[i];
  }
//  rep(i, 1, n) cout << p[i] << " ";

  cout << sub1::sol();
//  sub1::sol();
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29