oj.uz

답안 #411482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411482 2021-05-25T11:50:35 Z 최서현(#7473) The short shank; Redemption (BOI21_prison) C++17
0 / 100
 165 ms 71684 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
//#define DEBUG

using namespace std;

int k;
vector<pii> W;
vector<int> gph[2020202];
vector<vector<int>> dp;
int cnt;

void dfs(int x)
{
    ++cnt;
    while(cnt < (int)W.size() && W[x].ff <= W[cnt].ff && W[x].ss >= W[cnt].ss)
    {
        gph[x].push_back(cnt);
        dfs(cnt);
    }
}

void sol(int x, int p)
{
    for(auto y : gph[x]) if(y != p)
    {
        sol(y, x);
        if(dp[x].empty()) dp[x] = dp[y];
        else
        {
            vector<int> tmp(min(k + 1, int(dp[x].size() + dp[y].size()) - 1));
            for(int i = 0; i < (int)dp[x].size(); ++i)
            {
                for(int j = 0; j < (int)dp[y].size(); ++j)
                {
                    if(i + j > k) continue;
                    tmp[i + j] = max(tmp[i + j], dp[x][i] + dp[y][j]);
                }
            }

            #ifdef DEBUG
                cout << endl;
                cout << "dpx dpy tmp" << endl;
                for(auto i : dp[x]) cout << i << ' '; cout << endl;
                for(auto i : dp[y]) cout << i << ' '; cout << endl;
                for(auto i : tmp) cout << i << ' '; cout << endl;
                cout << endl;
            #endif

            dp[x] = tmp;
        }
    }
    if(dp[x].empty()) dp[x] = {0, 0};
    for(int i = 1; i < (int)dp[x].size(); ++i) dp[x][i]++;
    #ifdef DEBUG
        cout << endl;
        cout << "dpx" << endl;
        cout << x << endl;
        for(auto i : dp[x]) cout << i << ' '; cout << endl;
        cout << endl;
    #endif
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, t; cin >> n >> k >> t;
    int A[n]; for(auto &i : A) cin >> i;

    vector<pii> V;
    W.push_back({0, n});
    for(int i = 0; i < n; ++i)
    {
        if(A[i] > t)
        {
            while(V.size() && V.back().ss < i) V.pop_back();
            if(V.size() && V.back().ss >= i)
            {
                W.push_back({V.back().ff, i});
            }
        }
        else if(A[i] < t)
        {
            V.push_back({i, i + t - A[i]});
        }
    }
    sort(W.begin(), W.end(), [](pii x, pii y){return x.ff == y.ff ? x.ss > y.ss : x.ff < y.ff;});

    dfs(0);

    #ifdef DEBUG
        cout << endl;
        cout << "W" << endl;
        for(auto i : W) cout << i.ff << ' ' << i.ss << endl;;
        cout << endl;
    #endif
    #ifdef DEBUG
        cout << endl;
        cout << "gph" << endl;
        for(int i = 0; i < (int)W.size(); ++i)
        {
            cout << i << ": ";
            for(auto j : gph[i]) cout << j << ' ';
            cout << endl;
        }
        cout << endl;
    #endif

    dp.resize(cnt);
    sol(0, -1);
    cout << n - dp[0][k] + 1;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47696 KB Output is correct
2 Correct 29 ms 47688 KB Output is correct
3 Correct 29 ms 47776 KB Output is correct
4 Correct 30 ms 47692 KB Output is correct
5 Incorrect 29 ms 47684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47696 KB Output is correct
2 Correct 29 ms 47688 KB Output is correct
3 Correct 29 ms 47776 KB Output is correct
4 Correct 30 ms 47692 KB Output is correct
5 Incorrect 29 ms 47684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47696 KB Output is correct
2 Correct 29 ms 47688 KB Output is correct
3 Correct 29 ms 47776 KB Output is correct
4 Correct 30 ms 47692 KB Output is correct
5 Incorrect 29 ms 47684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47696 KB Output is correct
2 Correct 29 ms 47688 KB Output is correct
3 Correct 29 ms 47776 KB Output is correct
4 Correct 30 ms 47692 KB Output is correct
5 Incorrect 29 ms 47684 KB Output isn't correct
6 Halted 0 ms 0 KB -