oj.uz

Submission #678990

# Submission time Handle Problem Language Result Execution time Memory
678990 2023-01-07T06:54:27 Z sunwukong123 Cigle (COI21_cigle) C++14
0 / 100
 19 ms 13268 KB 
#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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 700 KB Output is correct
2 Incorrect 1 ms 696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 700 KB Output is correct
2 Incorrect 1 ms 696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13268 KB Output is correct
2 Incorrect 19 ms 13236 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 700 KB Output is correct
2 Incorrect 1 ms 696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 700 KB Output is correct
2 Incorrect 1 ms 696 KB Output isn't correct
3 Halted 0 ms 0 KB -