oj.uz

답안 #308791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
308791 2020-10-01T23:58:52 Z jainbot27 수열 (APIO14_sequence) C++17
0 / 100
 80 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int mxK = 201;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
ll dp[2][mxN], L[mxN][mxK], p[mxN], a[mxN], n, K;
void divi(int k, int l, int r, int opt_l, int opt_r){
    // cout << k << ' ' << l << ' ' << r << ' ' << opt_l << ' ' << opt_r << endl;
    // cout << l << ' ' << r << ' ' << opt_l << ' ' << opt_r << endl;
    if(l > r) return;
    int m = (l+r)/2;
    int pos = opt_l; ll ma = 0;
    for(int i = opt_l; i <= min(m, opt_r); i++){
        //do something
        if(ckmax(ma, 1LL*dp[0][i-1]+1LL*(p[m]-p[i-1])*(p[n]-p[m]))){
            pos = i;
        }
    }
    dp[1][m] = ma;
    L[m][k] = pos;
    divi(k, l, m-1, opt_l, pos);
    divi(k, m+1, r, pos, opt_r);
}


int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> K;
    FOR(i, 1, n+1){
        cin >> a[i];
        p[i] = a[i] + p[i-1];
    }
    ll bst = 0, val = 0;
    FOR(i, 1, K+1){
        divi(i, 1, n, 1, n);
        FOR(j, 1, n+1) dp[0][j] = dp[1][j];
        // cout << nl;
        if(i==K){
            FOR(j, 1, n+1){
                if(ckmax(val, dp[0][j])){
                    bst = j;
                }
            }
        }
    }
    vi res;
    cout << val << nl;
    int k = K; 
    res.pb(bst);
    while(k>1){
        res.pb(L[bst][k]);
        bst = L[bst][k];
        k--;
    }
    assert(siz(res)==K);
    reverse(all(res));
    trav(x, res){
        cout << x << ' ';
    }
    cout << nl;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB position 4 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 1093956 == 1093956
2 Incorrect 1 ms 512 KB position 3 occurs twice in split scheme
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB position 199 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1920 KB declared answer doesn't correspond to the split scheme: declared = 21503404, real = 21503392
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 16384 KB declared answer doesn't correspond to the split scheme: declared = 1818678304, real = 1695400000
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 80 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -