oj.uz

Submission #1077147

# Submission time Handle Problem Language Result Execution time Memory
1077147 2024-08-27T01:46:10 Z duyhoanho K blocks (IZhO14_blocks) C++17
0 / 100
 44 ms 80284 KB 
#include <bits/stdc++.h>
#define task ""
#define int long long
#define forinc(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e5+10;
int n,a[N],dp[N][102],k;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    if (fopen ("blocks.in", "r"))
    {
        freopen ("blocks.in", "r", stdin);
        freopen ("blocks.out", "w", stdout);
    }
    cin>>n>>k;
    memset(dp,99,sizeof dp);
    int mx=0;
    forinc(i,1,n)
    {
        cin>>a[i];
        mx=max(mx,a[i]);
        dp[i][1] = mx;

    }

    for(int j=2; j<=k; j++)
    {
        stack<int> st;
        for(int i=1; i<=n; i++)
        {
            while(st.size() && a[st.top()] <= a[i] )
            {
                dp[i][j] = min(dp[i][j], dp[st.top()][j-1] + a[i]);
                dp[i][j] = min(dp[i][j],dp[st.top()][j] - a[st.top()] + a[i]);
                st.pop();
            }
            if(st.size())
            {
                dp[i][j] = min(dp[i][j], dp[st.top()][j-1] + a[i]);
                dp[i][j] = min(dp[i][j],dp[st.top()][j]  + a[i]);
            }
            st.push(i);
        }
    }
//    forinc(i,1,n)
//    {
//      forinc(j,1,k) cout<<dp[i][j]<<" ";
//      cout<<"\n";
//    }
    cout<<dp[n][k];
}

Compilation message

blocks.cpp: In function 'int32_t main()':
blocks.cpp:16:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen ("blocks.in", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:17:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen ("blocks.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 80212 KB Output is correct
2 Correct 36 ms 80212 KB Output is correct
3 Correct 37 ms 80212 KB Output is correct
4 Correct 43 ms 80216 KB Output is correct
5 Correct 35 ms 80220 KB Output is correct
6 Correct 35 ms 80212 KB Output is correct
7 Correct 34 ms 80208 KB Output is correct
8 Correct 34 ms 80212 KB Output is correct
9 Correct 43 ms 80208 KB Output is correct
10 Correct 34 ms 80212 KB Output is correct
11 Correct 44 ms 80208 KB Output is correct
12 Correct 35 ms 80204 KB Output is correct
13 Incorrect 33 ms 80220 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 80212 KB Output is correct
2 Correct 33 ms 80220 KB Output is correct
3 Correct 36 ms 80284 KB Output is correct
4 Correct 35 ms 80216 KB Output is correct
5 Correct 30 ms 80220 KB Output is correct
6 Correct 32 ms 80216 KB Output is correct
7 Correct 34 ms 80208 KB Output is correct
8 Correct 34 ms 80208 KB Output is correct
9 Correct 33 ms 80216 KB Output is correct
10 Correct 40 ms 80108 KB Output is correct
11 Correct 44 ms 80172 KB Output is correct
12 Correct 35 ms 80212 KB Output is correct
13 Correct 30 ms 80220 KB Output is correct
14 Incorrect 33 ms 80208 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 80212 KB Output is correct
2 Correct 36 ms 80212 KB Output is correct
3 Correct 37 ms 80212 KB Output is correct
4 Correct 43 ms 80216 KB Output is correct
5 Correct 35 ms 80220 KB Output is correct
6 Correct 35 ms 80212 KB Output is correct
7 Correct 34 ms 80208 KB Output is correct
8 Correct 34 ms 80212 KB Output is correct
9 Correct 43 ms 80208 KB Output is correct
10 Correct 34 ms 80212 KB Output is correct
11 Correct 44 ms 80208 KB Output is correct
12 Correct 35 ms 80204 KB Output is correct
13 Incorrect 33 ms 80220 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 80212 KB Output is correct
2 Correct 36 ms 80212 KB Output is correct
3 Correct 37 ms 80212 KB Output is correct
4 Correct 43 ms 80216 KB Output is correct
5 Correct 35 ms 80220 KB Output is correct
6 Correct 35 ms 80212 KB Output is correct
7 Correct 34 ms 80208 KB Output is correct
8 Correct 34 ms 80212 KB Output is correct
9 Correct 43 ms 80208 KB Output is correct
10 Correct 34 ms 80212 KB Output is correct
11 Correct 44 ms 80208 KB Output is correct
12 Correct 35 ms 80204 KB Output is correct
13 Incorrect 33 ms 80220 KB Output isn't correct
14 Halted 0 ms 0 KB -