oj.uz

Submission #416037

# Submission time Handle Problem Language Result Execution time Memory
416037 2021-06-01T20:42:07 Z ti20_ntson K blocks (IZhO14_blocks) C++17
0 / 100
 21 ms 41412 KB 
/// Author :Nguyễn Thái Sơn -Ti20 -THPT chuyên Lương Thế Vinh

#include<bits/stdc++.h>
#define TASK "test"
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define ti20_ntson int main()
#define all(x) (x).begin(),(x).end()
#define vi vector<int>
#define vii pair<int,int>
#define forup(i,l,r) for (int i=l; i<=r; i++)
#define fordown(i,l,r) for (int i=l; i>=r; i--)
#define getbit(x, i) (((x) >> (i)) & 1)
#define vvi vector< vector <int >>

using namespace std;
const int mod = 1e9+7;
const int oo = 1e8;
const int maxN = 1e5+5;

int n,a[maxN];
int dp[105][maxN],k;

void nhap()
{
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> a[i];
}

void solve()
{
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int i =1; i<=n; i++)
        dp[1][i] = max (dp[1][i-1],a[i]);
    for (int i=2; i<=k; i++) {
        stack < vii > S;
        for (int j=i; j <= n; j++) {
            int res = dp[i-1][j-1];
            while (!S.empty() && a[S.top().second] <= a[j]) {
                res =  min(res, S.top().first);
                S.pop();
            }
            dp[i][j] = min(dp[i][S.empty() ? 0 : S.top().second], res + a[j]);
//            cout << i << " " << j <<  " " << dp[i][j] << endl;
            cout << res << endl;
            S.push({res,j});
        }
    }
    cout << dp[k][n];
}

ti20_ntson
{
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    int T =1;
//    cin >> T;
    while (T--) {
        nhap();
        solve();
    }
}

/*
input
4 5
2 3 4 5 56
outpt
4455
*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41292 KB Output is correct
2 Correct 20 ms 41312 KB Output is correct
3 Correct 19 ms 41380 KB Output is correct
4 Incorrect 20 ms 41340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41360 KB Output is correct
2 Correct 21 ms 41332 KB Output is correct
3 Correct 20 ms 41360 KB Output is correct
4 Incorrect 19 ms 41412 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41292 KB Output is correct
2 Correct 20 ms 41312 KB Output is correct
3 Correct 19 ms 41380 KB Output is correct
4 Incorrect 20 ms 41340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41292 KB Output is correct
2 Correct 20 ms 41312 KB Output is correct
3 Correct 19 ms 41380 KB Output is correct
4 Incorrect 20 ms 41340 KB Output isn't correct
5 Halted 0 ms 0 KB -