oj.uz

답안 #697483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697483 2023-02-10T03:40:48 Z Bobonbush Discharging (NOI20_discharging) C++17
20 / 100
 266 ms 86728 KB 
#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll ;
const int LOG = 18;
const long long base = 31;
const long long MODULO = 1e9+7;
const long long INF = 1e18+1;
template<class X ,class Y>
    bool Minimize(X &x , Y y)
    {
        if(x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X , class Y>
    bool Maximize(X &x , Y y)
    {
        if(x < y)
        {
            x = y;
            return true;
        }
        return false;
    }
const int N = 1e6+1;
int n , k ;
long long dp[N];
int a[N];

class SegmentedTree
{
    private:
        vector<pair<long long , long long >>nodes;
    public:
        SegmentedTree(int _n)
        {
            nodes.assign(_n * 4 + 1 , make_pair(INF , INF));
        }

        void Down(int id ,long long lazy)
        {
            Minimize(nodes[id].first , lazy);
            Minimize(nodes[id].second , lazy);
        }

        void Update(int l ,int r ,int id , int u ,int v ,long long w)
        {
            if(l > v  || u > r)
            {
                return ;
            }
            if(u <= l && r <= v)
            {
                Minimize(nodes[id].first , w);
                Minimize(nodes[id].second , w);
                return ;
            }
            int mid = (l+r) >> 1;
            Down(id << 1 , nodes[id].second);
            Down(id << 1 |1 , nodes[id].second);
            nodes[id].second = INF;
            Update(l , mid ,id << 1 , u ,v , w);
            Update(mid+1 , r , id <<1 |1 , u , v , w);

            nodes[id].first = min(nodes[id << 1].first , nodes[id << 1 | 1].first);
        }

        long long Get(int l,int r ,int id ,int u ,int v)
        {
            if(l > v || u > r)
            {
                return INF;
            }
            if(u <= l && r <= v)
            {
                return nodes[id].first;
            }
            int mid = (l+r) >> 1;
            Down(id << 1 , nodes[id].second);
            Down(id << 1 |1 , nodes[id].second);
            nodes[id].second = INF;
            return min(Get(l , mid , id << 1 , u , v) , Get(mid+1 , r , id << 1 |1 , u , v));
        }
};

int lll[N] ,rr[N];
void Input()
{
    cin >> n ;
    for(int i = 1; i <= n ; i++)
    {
        cin >> a[i];
    }
}
void Process()
{
    SegmentedTree Seg(n);
    stack<int>st;
    for(int i =1; i <= n ; i++)
    {
        while(!st.empty() && a[st.top()] <= a[i])
        {
            st.pop();
        }
        lll[i] = 1;
        if(!st.empty())lll[i] = st.top() + 1;
        st.push(i);
    }
    while(!st.empty())st.pop();
    for(int i = n ; i >= 1 ; i--)
    {
        while(!st.empty() && a[st.top()] <= a[i])st.pop();
        rr[i] = n;
        if(!st.empty())rr[i] = st.top() -1;
        st.push(i);
    }
    for(int i = 1 ; i <= n ; i++)dp[i] = INF;
    for(int i = 1; i <= n ; i++)
    {
        int maxx = a[i];
        for(int j = i ; j>=1 && (i - j +1 <= 100) ; j--)
        {
            Maximize(maxx , a[j]);

            Minimize(dp[i] , dp[j-1]  + maxx * 1LL * (n - j + 1));

        }
        if(a[lll[i] -1] > a[i])
            Minimize(dp[i] , dp[lll[i] -1]);
    }
    cout << dp[n];
}
int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    int test = 1;
    while(test--)
    {
        Input();
        Process();
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 13.0

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

Subtask #3
0 / 25.0

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

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 86504 KB Output is correct
2 Correct 257 ms 86508 KB Output is correct
3 Correct 257 ms 86724 KB Output is correct
4 Correct 258 ms 86484 KB Output is correct
5 Correct 263 ms 86612 KB Output is correct
6 Correct 254 ms 86604 KB Output is correct
7 Correct 266 ms 86692 KB Output is correct
8 Correct 254 ms 86612 KB Output is correct
9 Correct 253 ms 86612 KB Output is correct
10 Correct 257 ms 86728 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 468 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 468 KB Output isn't correct
16 Halted 0 ms 0 KB -