Submission #1091819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091819		underwaterkillerwhale	Split the sequence (APIO14_sequence)	C++17	0 / 100	53 ms	131072 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define reb(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define se second
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;


mt19937_64 rd (chrono::steady_clock::now().time_since_epoch().count());
ll Rand (ll L, ll R) { return uniform_int_distribution<ll> (L, R)(rd); }

const int N = 2e3 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;

int n, m, K;
int a[N];
int Mn[N][N];
ll dp[N][N][2], pre[N][N], suf[N][N], g[N][N][2], pos[N];
int dd[N];
vector<ll> V = {0};

int cpr (int X) {
    return lower_bound(ALL(V), X) - V.begin();
}

void compress () {
    rep (i, 1, n) V.pb(a[i]);
    sort (ALL(V));
    V.resize(unique(ALL(V)) - V.begin());
    m = SZ(V) - 1;
}

void solution() {
    cin >> n >> K;
    rep (i, 1, n) cin >> a[i];
    rep (i, 1, n) {
        Mn[i][i] = a[i];
        rep (j, i + 1, n) Mn[i][j] = min(Mn[i][j - 1], a[j]);
    }
//    rep (i, 1, n) {
//        int de = 1;
//        while (a[i] == a[i + 1]) ++i, ++de;
////        if (a[i] == 2) cout << de <<"\n";
//    }
    ll res = 0;
    compress();

    memset(dp, -0x3f, sizeof dp);
    memset(pre, -0x3f, sizeof pre);
    memset(suf, -0x3f, sizeof suf);
    memset(g, -0x3f, sizeof g);
    rep (j, 1, m) suf[0][j] = 0;
    rep (j, 1, m) {
        dp[0][j][1] = 0;
    }

    rep (i, 1, n) {
        int bound = cpr(a[i]);
        rep (j, 1, bound) {
            if (i > K) {
                dp[i][j][1] = max(pre[i - 1][j] + V[j], dp[i][j][1]);
                dp[i][j][1] = max(g[i - K][j][0] + V[j], dp[i][j][1]);
            }
            else dp[i][j][1] = dp[i - 1][j][1] + V[j];
            if (i <= n - K + 1) {
                dp[i][j][0] = suf[i - 1][j] + V[j];
                if (i > K) dp[i][j][0] = max(g[i - K][j][1] + V[j], dp[i][j][0]);
            }
            else dp[i][j][0] = dp[i - 1][j][0] + V[j];
        }
        rep (j, 1, m) pre[i][j] = max(pre[i][j - 1], dp[i][j][1]);
        reb (j, m, 1) suf[i][j] = max(suf[i][j + 1], dp[i][j][0]);
        int mnp = cpr(Mn[i][i + K - 1]);
        rep (j, 1, mnp) {
            rep (k, 0, 1) {
                g[i][j][k] = max(g[i][j - 1][k], dp[i][j][k] + V[j] * (K - 1));
            }
        }
    }
//    cout << dp[K][1][1] <<" "<<1LL * a[1] * K <<"\n";
    cout << max(pre[n][m], suf[n][1]) <<"\n";
}


int main () {
    freopen("c.INP","r",stdin);
    freopen("c.OUT","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--) solution();
}

Compilation message (stderr)

sequence.cpp: In function 'void solution()':
sequence.cpp:53:8: warning: unused variable 'res' [-Wunused-variable]
   53 |     ll res = 0;
      |        ^~~
sequence.cpp: In function 'int main()':
sequence.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen("c.INP","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
sequence.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen("c.OUT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29