제출 #959857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959857		LucaIlie	별자리 3 (JOI20_constellation3)	C++17	35 / 100	1047 ms	102872 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

struct star {
    int i, j, c;
};

const int MAX_N = 2e5;
const int MAX_M = 2e5;
int n;
int h[MAX_N + 2], parent[MAX_N + 2], leftSon[MAX_N + 2], rightSon[MAX_N + 2], leftt[MAX_N + 2], rightt[MAX_N + 2], cost[MAX_N + 2];
long long dp[2002][2002];
star stars[MAX_M];
vector<int> starsByColumn[MAX_N + 2];

void dfs( int v, int l, int r ) {
    if ( v == 0 )
        return;

    leftt[v] = l;
    rightt[v] = r;
    //printf( "%d %d %d\n", v, l, r );

    dfs( leftSon[v], l, v - 1 );
    dfs( rightSon[v], v + 1, r );
}

void calcCost( int v ) {
    if ( v == 0 )
        return;

    calcCost( leftSon[v] );
    calcCost( rightSon[v] );

    for ( int x = 0; x <= n; x++ ) {
        if ( x <= h[v] )
            dp[v][x] = dp[leftSon[v]][x] + dp[rightSon[v]][x];
        else
            dp[v][x] = max( dp[leftSon[v]][x] + dp[rightSon[v]][h[v]], dp[leftSon[v]][h[v]] + dp[rightSon[v]][x] );
    }

    for ( int i: starsByColumn[v] )
        dp[v][stars[i].j] = max( dp[v][stars[i].j], dp[v][h[v]] + stars[i].c );

    for ( int x = 1; x <= n; x++ )
        dp[v][x] = max( dp[v][x], dp[v][x - 1] );
}

int main() {
    int m;
    long long total = 0;

    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> h[i];
    cin >> m;
    for ( int i = 0; i < m; i++ ) {
        cin >> stars[i].i >> stars[i].j >> stars[i].c;
        total += stars[i].c;
    }

    h[n + 1] = n + 1;
    vector<int> stack;
    for ( int i = 1; i <= n + 1; i++ ) {
        vector<int> path;
        while ( !stack.empty() && h[i] >= h[stack.back()] ) {
            path.push_back( stack.back() );
            stack.pop_back();
        }
        path.push_back( i );
        stack.push_back( i );

        for ( int j = 0; j < path.size() - 1; j++ )
            parent[path[j]] = path[j + 1];
    }

    //for ( int v = 1; v <= n; v++ )
        //printf( "%d %d, %d %d\n", v, parent[v], h[v], h[parent[v]] );
    for ( int v = 1; v <= n; v++ ) {
        if ( v < parent[v] )
            leftSon[parent[v]] = v;
        else
            rightSon[parent[v]] = v;
    }

    for ( int i = 0; i < m; i++ )
        starsByColumn[stars[i].i].push_back( i );

    calcCost( n + 1 );

    cout << total - dp[n + 1][n];

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'int main()':
constellation3.cpp:74:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for ( int j = 0; j < path.size() - 1; j++ )
      |                          ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 65