Submission #678990

#	Time	Username	Problem	Language	Result	Execution time	Memory
678990		sunwukong123	Cigle (COI21_cigle)	C++14	0 / 100	19 ms	13268 KiB

cigle

#include <bits/stdc++.h>

using namespace std;
# 24 "cigle.cpp"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
# 34 "cigle.cpp"
typedef pair <long long, long long> pi;
typedef tuple<long long,long long,long long> ti3;
typedef tuple<long long,long long,long long,long long> ti4;
long long rand(long long a, long long b) { return a + rng() % (b-a+1); }
const long long MOD = 1e9 + 7;
const long long inf = (long long)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const long long MAXN = 5005;
long long n;
long long A[MAXN];
long long dp[MAXN][MAXN];
long long prefix[MAXN][MAXN];
struct fw {
 long long fw[MAXN];

 long long getmax(long long x) {
  long long r=0;
  for(;x;x-=x&-x)chmax(r,fw[x]);
  return r;
 }
 void update(long long x, long long nval) {
  for(;x<MAXN;x+=x&-x)chmax(fw[x], nval);
 }
} BIT[MAXN];
long long ans = 0;
int32_t main()
{
 cin >> n;

 for(long long i = 1; i <= (long long)n; ++i) cin >> A[i];
 for(long long i = 1; i <= (long long)n; ++i) {
  long long pre=i-1;
  long long sum=0;
  long long psum=0;
  long long cost = 0;
  bool fi=1;
  long long mxpre=0;
  for(long long j = i; j <= (long long)n; ++j) {
   sum+=A[j];
   chmax(mxpre,BIT[i-1].getmax(pre) + cost);
   while(pre>0 && psum+A[pre]<=sum) {
    psum+=A[pre];
    --pre;
   }

   if(sum == psum) {
    chmax(mxpre,BIT[i-1].getmax(pre) + cost);
    chmax(dp[i][j], mxpre);

    BIT[j].update(i, dp[i][j]);
    ++cost;
   } else {

    chmax(dp[i][j], mxpre);
    BIT[j].update(i, dp[i][j]);
   }

  }
 }
 for(long long i = 1; i <= (long long)n; ++i) {
  chmax(ans, dp[i][n]);
 }
 cout << ans;
}

Compilation message (stderr)

cigle.cpp: In function 'int32_t main()':
cigle.cpp:71:8: warning: unused variable 'fi' [-Wunused-variable]

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 52