oj.uz

Submission #272704

# Submission time Handle Problem Language Result Execution time Memory
272704 2020-08-18T13:41:51 Z Killer2501 K blocks (IZhO14_blocks) C++14
0 / 100
 12 ms 13056 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "blocks"
#define fi first
#define se second
#define pll pair<ll, ll>
using namespace std;
const ll N = 2e5 + 5;
const ll mod = 1e9 + 7;
ll n, sum= 0, m, tong, k, ans, T, t;

ll a[N], dp[N][102];
string s;
vector<pll> adj[N];
ll f(ll i, ll j)
{
    return (i-1) * m + j;
}
char c[N];
inline void sol()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        dp[i][1] = max(dp[i-1][1], a[i]);
        dp[0][i] = mod;
        //cout << dp[i][1] <<" ";
    }
    for(int j = 2; j <= k; j ++)
    {
        stack<pll> ds;
        for(int i = j; i <= n; i ++)
        {
            ll mn = dp[i-1][j-1];
            while(!ds.empty() && a[ds.top().se] <= a[i])
            {

                mn = min(mn, ds.top().fi);
                ds.pop();
            }
            dp[i][j] = min(dp[ds.empty() ? 0 : ds.top().se][j-1], mn + a[i]);
            ds.push({mn, i});
            //cout << dp[i][j] <<' ';
        }
        //cout << '\n';
    }
    cout << dp[n][k];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    sol();
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Incorrect 4 ms 5120 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 5 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Incorrect 4 ms 4992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 13056 KB Output isn't correct
2 Halted 0 ms 0 KB -