oj.uz

답안 #478619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478619 2021-10-08T05:36:19 Z Haruto810198 The short shank; Redemption (BOI21_prison) C++17
0 / 100
 65 ms 12028 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 2000010;

int n, d, T;

int segs;
vector<pii> seg; // id. of seg : 0-indexed
vi dis_prev;
vi pref;

vector<vi> dp;

int query(int ql, int qr){
    if(ql > qr) return 0;
    if(ql == 0) return pref[qr];
    return pref[qr] - pref[ql - 1];
}

void solve(int u, int sl, int sr, int optl, int optr){
    int mid = (sl + sr) / 2;
    int optmid, Max = -INF;
    FOR(i, optl, optr, 1){
        int val = dp[u - 1][i] + query(i + 2, mid) + max((int)0, seg[i+1].F - seg[i].F - 1);
        if(val > Max){
            Max = val;
            optmid = i;
        }
    }
    dp[u][mid] = Max;
    //cerr<<"dp["<<u<<"]["<<mid<<"] = "<<dp[u][mid]<<", opt = dp["<<u-1<<"]["<<optmid<<"] "<<endl;
    if(sl <= mid-1) solve(u, sl, mid-1, optl, optmid);
    if(mid+1 <= sr) solve(u, mid+1, sr, optmid, optr);
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>d>>T;
    FOR(i, 1, n, 1){
        int ti;
        cin>>ti;
        if(ti <= T){
            int len = T - ti;
            seg.eb(i, min(i + len, n));
        }
    }

    segs = szof(seg);
    dis_prev.resize(segs);

    //
    seg.eb(n+1, n+1);
    //

    dis_prev[0] = 0;
    FOR(i, 1, segs - 1, 1){
        dis_prev[i] = max((int)0, seg[i].F - seg[i-1].S - 1);
    }

    pref.resize(segs);
    pref[0] = dis_prev[0];
    FOR(i, 1, segs - 1, 1){
        pref[i] = pref[i-1] + dis_prev[i];
    }

    dp.resize(d + 1);
    for(vi& i : dp){
        i.resize(segs);
    }

    FOR(i, 0, segs - 1, 1){
        dp[1][i] = query(1, i);
    }

    FOR(i, 0, segs - 1, 1){
        //cerr<<"dp[1]["<<i<<"] = "<<dp[1][i]<<endl;
    }

    d = min(d, segs);
    FOR(i, 2, d, 1){
        solve(i, i-1, segs-1, i-2, segs-2);
        FOR(j, 0, segs - 1, 1){
            //cerr<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<" ";
        }
        //cerr<<endl;
    }
    //cerr<<endl;

    int res = -INF;
    FOR(i, d - 1, segs - 1, 1){
        res = max(res, dp[d][i] + query(i + 2, segs - 1) + max((int)0, seg[i+1].F - seg[i].F - 1));
    }

    res = n - res;
    cout<<res<<'\n';

    return 0;

}

Compilation message

prison.cpp: In function 'void solve(long long int, long long int, long long int, long long int, long long int)':
prison.cpp:59:26: warning: 'optmid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     if(sl <= mid-1) solve(u, sl, mid-1, optl, optmid);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 65 ms 12028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 24 ms 4712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -