oj.uz

Submission #697484

# Submission time Handle Problem Language Result Execution time Memory
697484 2023-02-10T03:41:50 Z Bobonbush Discharging (NOI20_discharging) C++17
47 / 100
 176 ms 86744 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 && (n * 1LL * (i - j +1)) <= 1e7 ; 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

# Verdict Execution time Memory 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 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Incorrect 119 ms 84004 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 86516 KB Output is correct
2 Correct 150 ms 86600 KB Output is correct
3 Correct 141 ms 86568 KB Output is correct
4 Correct 151 ms 86744 KB Output is correct
5 Correct 140 ms 86588 KB Output is correct
6 Correct 140 ms 86540 KB Output is correct
7 Correct 145 ms 86684 KB Output is correct
8 Correct 176 ms 86532 KB Output is correct
9 Correct 142 ms 86600 KB Output is correct
10 Correct 138 ms 86520 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory 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 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 3 ms 480 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 3 ms 468 KB Output is correct
22 Correct 3 ms 468 KB Output is correct
23 Correct 4 ms 468 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 4 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 3 ms 340 KB Output is correct
33 Correct 3 ms 468 KB Output is correct
34 Correct 2 ms 468 KB Output is correct
35 Correct 2 ms 468 KB Output is correct
36 Correct 3 ms 468 KB Output is correct
37 Correct 2 ms 468 KB Output is correct
38 Correct 2 ms 340 KB Output is correct
39 Correct 2 ms 468 KB Output is correct
40 Correct 2 ms 340 KB Output is correct
41 Correct 3 ms 340 KB Output is correct
42 Correct 2 ms 468 KB Output is correct
43 Correct 3 ms 468 KB Output is correct
44 Correct 2 ms 340 KB Output is correct
45 Correct 3 ms 468 KB Output is correct
46 Correct 2 ms 340 KB Output is correct
47 Correct 2 ms 468 KB Output is correct
48 Correct 2 ms 468 KB Output is correct
49 Correct 2 ms 340 KB Output is correct
50 Correct 2 ms 340 KB Output is correct

Subtask #6
0 / 28.0

# Verdict Execution time Memory 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 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 3 ms 480 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 3 ms 468 KB Output is correct
22 Correct 3 ms 468 KB Output is correct
23 Correct 4 ms 468 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 4 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Incorrect 119 ms 84004 KB Output isn't correct
31 Halted 0 ms 0 KB -