Submission #853337

#	Time	Username	Problem	Language	Result	Execution time	Memory
853337		aaronkim00	수족관 3 (KOI13_aqua3)	C++17	0 / 100	70 ms	15912 KiB

aqua3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
const ll MOD = 1000000007;

struct FLOOR{
    int idx, x1, x2, y;
};

vector<int> tree[300010];
int parent[300010];
ll w[300010];
ll val[300010];

const bool compare(const int x, const int y){
    return val[x]>val[y];
}

int dfs(int u){
    int curr = u;
    for(int v: tree[u]){
        int t = dfs(v);
        if(val[curr] < val[t]){
            curr = t;
        }
    }
    val[curr] += w[u];
    return curr;
}

int main(void){
    int N, K;
    scanf("%d", &N);
    int t1, t2;
    scanf("%d %d", &t1, &t2);
    stack<FLOOR> st;
    st.push({0, 0, 0, -1});
    int maxX = 0;
    for(int i=1; i<=N/2; i++){
        int x1 = maxX, y = -1, x2 = maxX;
        if(i<N/2){
            scanf("%d %d", &x1, &y);
            scanf("%d %d", &x2, &y);
            maxX = max(maxX, x2);
        }
        while(true){
            FLOOR t = st.top();
            st.pop();
            if(t.y<y){
                st.push(t);
                st.push({i, x1, x2, y});
                break;
            }
            else if(t.y==y){
                st.push(t);
                break;
            }
            else{
                if(st.top().y < y){
                    parent[t.idx] = i;
                    tree[i].push_back(t.idx);
                }
                else{
                    parent[t.idx] = st.top().idx;
                    tree[st.top().idx].push_back(t.idx);
                }
                w[t.idx] = (ll)(t.y-max(st.top().y, y))*(ll)(x1-st.top().x2);
            }
        }
    }
    scanf("%d %d", &t1, &t2);
    scanf("%d", &K);
    for(int i=1; i<N/2; i++){
        if(parent[i]==0&&w[i]>0){
            dfs(i);
        }
    }
    /*for(int i=1; i<N/2; i++){
        printf("%d: %d %lld %lld\n", i, parent[i], w[i], val[i]);
        for(int x: tree[i]){
            printf("%d ", x);
        }
        printf("\n");
    }*/
    ll result = 0;
    vector<int> L;
    for(int i=1; i<N/2; i++){
        L.push_back(i);
    }
    sort(all(L), compare);
    for(int i=0; i<K; i++){
        result += val[L[i]];
    }
    printf("%lld\n", result-maxX);
}

Compilation message (stderr)

aqua3.cpp: In function 'int main()':
aqua3.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
aqua3.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d", &t1, &t2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
aqua3.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |             scanf("%d %d", &x1, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
aqua3.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |             scanf("%d %d", &x2, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
aqua3.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d %d", &t1, &t2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
aqua3.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &K);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 21
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16