oj.uz

Submission #498471

# Submission time Handle Problem Language Result Execution time Memory
498471 2021-12-25T09:11:35 Z xynex Split the sequence (APIO14_sequence) C++17
100 / 100
 581 ms 82528 KB 
/*
* Author: xynex
* Created: 25.12.2021 14:00
* Why am I so stupid? :c
* Slishkom slab
*/

#include <bits/stdc++.h>

 #pragma GCC optimize("inline")
 #pragma GCC optimize("-fgcse,-fgcse-lm")
 #pragma GCC optimize("-ftree-pre,-ftree-vrp")
 #pragma GCC optimize("-ffast-math")
 #pragma GCC optimize("-fipa-sra")
 #pragma GCC optimize("-fpeephole2")
 #pragma GCC optimize("-fsched-spec")
 #pragma GCC optimize("Ofast,no-stack-protector")
 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 #pragma GCC optimize("unroll-loops")

using namespace std;

#define ll long long
const int N = 1e5 + 1;
const int M = 201;
const ll INF = 1e9;

ll dp[N][2], pref[N];
int path[N][M];
int n, k;
bool get(ll x, ll y, ll z) {
    ll ind = dp[y][0] - dp[x][0];
//    print(ind);
    ll ind1 = (pref[n] - pref[z]) * (pref[y] - pref[x]);
//    print(ind1);
    return ind >= ind1;
}
bool get1(ll x, ll y, ll z) {
    ll ind = dp[y][0] - dp[x][0];
    ind *= pref[z] - pref[y];
//    print(ind);
    ll ind1 = dp[z][0] - dp[y][0];
    ind1 *= pref[y] - pref[x];
//    print(ind1);
    return ind <= ind1;
}
void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> pref[i];
        pref[i] += pref[i - 1];
    }
    vector<ll> d(n + 1);
    for(int i = 1; i <= k; ++i) {
        d[0] = 0, d[1] = 0;
        int l = 0, r = 1;
        for(int j = 1; j <= n; ++j) {
            while(r - l > 1 && get(d[l], d[l + 1], j)) l++;
            int pos = d[l];
            if(dp[pos][0] + (pref[n] - pref[j]) * (pref[j] - pref[pos]) >= dp[j][1]) {
                dp[j][1] = dp[pos][0] + (pref[n] - pref[j]) * (pref[j] - pref[pos]);
                path[j][i] = pos;
            }
            while(r - l > 1 && get1(d[r - 2], d[r - 1], j)) r--;
            d[r] = j;
            r++;
//            print(d);
        }
        for(int j = 1; j <= n; ++j) dp[j][0] = dp[j][1], dp[j][1] = 0;
    }
//    for(int i = 1; i <= k; ++i) {
//        print(i);
//        for(int j = 1; j <= n; ++j) write(dp[j][i], ' ');
//        print("");
//    }
    int whr = 0;
    ll mx = -INF;
    for(int i = 1; i <= n; ++i) {
        if(mx < dp[i][0]) {
            mx = dp[i][0];
            whr = i;
        }
    }
    cout << mx << "\n";
    for(int i = 1; i <= k; ++i) {
        cout << whr << " ";
        whr = path[whr][k - i + 1];
    }
}

int main() {
    //freop("");
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //read(t);
    for (int i = 1; i <= t; ++i) {
        //write("Case #" + to_string(i) + ": ");
        solve();
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 332 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 204 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 332 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 332 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 332 KB contestant found the optimal answer: 1 == 1
7 Correct 0 ms 332 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 332 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 332 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 332 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 332 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 0 ms 332 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 0 ms 332 KB contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 204 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 0 ms 332 KB contestant found the optimal answer: 805 == 805
16 Correct 0 ms 332 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 0 ms 204 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 332 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 0 ms 332 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 0 ms 332 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 0 ms 332 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 0 ms 332 KB contestant found the optimal answer: 933702 == 933702
7 Correct 0 ms 332 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 1 ms 332 KB contestant found the optimal answer: 687136 == 687136
9 Correct 0 ms 332 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 0 ms 332 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 460 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 460 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 460 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 2 ms 460 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 1 ms 460 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 1 ms 460 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 0 ms 460 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 1 ms 460 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 1 ms 460 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 1 ms 1100 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 4 ms 1100 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 1 ms 1100 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 5 ms 1100 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 5 ms 1100 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 5 ms 1100 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 4 ms 1100 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 2 ms 1100 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 2 ms 1100 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8396 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 6 ms 8396 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Correct 43 ms 8496 KB contestant found the optimal answer: 4973126687469639 == 4973126687469639
4 Correct 4 ms 8512 KB contestant found the optimal answer: 3748491676694116 == 3748491676694116
5 Correct 43 ms 8396 KB contestant found the optimal answer: 1085432199 == 1085432199
6 Correct 36 ms 8396 KB contestant found the optimal answer: 514790755404 == 514790755404
7 Correct 39 ms 8396 KB contestant found the optimal answer: 1256105310476641 == 1256105310476641
8 Correct 34 ms 8396 KB contestant found the optimal answer: 3099592898816 == 3099592898816
9 Correct 33 ms 8396 KB contestant found the optimal answer: 1241131419367412 == 1241131419367412
10 Correct 44 ms 8396 KB contestant found the optimal answer: 1243084101967798 == 1243084101967798

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 81984 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 42 ms 82052 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Correct 474 ms 82500 KB contestant found the optimal answer: 497313449256899208 == 497313449256899208
4 Correct 42 ms 82500 KB contestant found the optimal answer: 374850090734572421 == 374850090734572421
5 Correct 581 ms 82276 KB contestant found the optimal answer: 36183271951 == 36183271951
6 Correct 392 ms 82208 KB contestant found the optimal answer: 51629847150471 == 51629847150471
7 Correct 440 ms 82528 KB contestant found the optimal answer: 124074747024496432 == 124074747024496432
8 Correct 355 ms 82368 KB contestant found the optimal answer: 309959349080800 == 309959349080800
9 Correct 354 ms 82344 KB contestant found the optimal answer: 124113525649823701 == 124113525649823701
10 Correct 494 ms 82428 KB contestant found the optimal answer: 124309619349406845 == 124309619349406845