Submission #890551

#	Time	Username	Problem	Language	Result	Execution time	Memory
890551		zeta7532	Cigle (COI21_cigle)	C++17	100 / 100	266 ms	98644 KiB

cigle

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = int;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)
 
int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    vector<vector<ll>> dp(N,vector<ll>(N,0));
    rep(i,N-1){
        vector<ll> l;
        vector<ll> r;
        ll sum_l=0;
        ll sum_r=0;
        for(ll j=i;j>=0;j--){
            sum_l+=A[j];
            l.push_back(sum_l);
        }
        for(ll j=i+1;j<N;j++){
            sum_r+=A[j];
            r.push_back(sum_r);
        }
        vector<pair<ll,ll>> P;
        ll now_l=0;
        ll now_r=0;
        while(now_l+1<l.size()&&now_r+1<r.size()){
            if(l[now_l]<r[now_r]){
                now_l++;
                continue;
            }
            if(l[now_l]>r[now_r]){
                now_r++;
                continue;
            }
            if(l[now_l]==r[now_r]){
                P.push_back({now_l,now_r});
                now_l++;
                now_r++;
                continue;
            }
        }
        reverse(all(P));
        rep(j,P.size()) P[j].fi=i-1-P[j].fi,P[j].se=i+2+P[j].se;
        ll now_j=0;
        ll cum=0;
        rep(j,i){
            if(now_j==P.size()) break;
            cum=max(cum,dp[j][i]);
            if(j==P[now_j].fi){
                dp[i+1][P[now_j].se]=cum+P.size()-now_j;
                now_j++;
            }
        }
        rep(j,N-1){
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j]);
        }
    }
    ll ans=0;
    rep(j,N) ans=max(ans,dp[j][N-1]);
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:36:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(now_l+1<l.size()&&now_r+1<r.size()){
      |               ~~~~~~~^~~~~~~~~
cigle.cpp:36:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(now_l+1<l.size()&&now_r+1<r.size()){
      |                                 ~~~~~~~^~~~~~~~~
cigle.cpp:10:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define rep(i,n) for(ll i=0;i<n;i++)
......
   53 |         rep(j,P.size()) P[j].fi=i-1-P[j].fi,P[j].se=i+2+P[j].se;
      |             ~~~~~~~~~~        
cigle.cpp:53:9: note: in expansion of macro 'rep'
   53 |         rep(j,P.size()) P[j].fi=i-1-P[j].fi,P[j].se=i+2+P[j].se;
      |         ^~~
cigle.cpp:57:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if(now_j==P.size()) break;
      |                ~~~~~^~~~~~~~~~

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