oj.uz

Submission #922509

# Submission time Handle Problem Language Result Execution time Memory
922509 2024-02-05T15:15:26 Z phong K blocks (IZhO14_blocks) C++17
0 / 100
 35 ms 85340 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e5 + 5;
const ll oo = 1e18, base = 311;
const int lg = 19, M = 105;
const ll mod = 1e9 + 7;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

int n, k;
ll f[nmax][M], a[nmax];
void ckmax(ll &a, ll b){
    a = max(a, b);
}
deque<int> de;
multiset<pii> mt[M];
int L[nmax][M];
int get(int i, int j){
    int u = L[i][j];
    if(f[u][j] > oo) ++u;
    if(u == i) --u;
    return u;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.ans", "w", stdout);
    cin >> n >> k;
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        if(i == 1) f[1][1] = a[i];
        else f[i][1] = max(f[i - 1][1], a[i]);
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= k; ++j){
            auto &cur = L[i][j];
            cur = i - 1;
            while(cur > 0 && a[cur] <= a[i] && f[cur][j] < oo) cur = L[cur][j];
        }
        if(i == 1) continue;
        while(de.size() && a[de.back()] <= a[i]){
            int u = de.back();
            for(int j = 2; j <= min(k, i); ++j){
                int x = get(u, j - 1);
                mt[j].erase({f[x][j - 1] + a[u], u});
            }
            de.pop_back();
        }
        de.push_back(i);
        for(int j = 2; j <= min(k, i); ++j){
            int x = get(i, j - 1);
            mt[j].insert({f[x][j - 1] + a[i], i});
            auto it = *mt[j].begin();
            f[i][j] = it.fi;
        }
    }
    cout << f[n][k];
}
/*
5 3 2
2 3 3
3 5 5
5 1 6
5 4 3


*/

Compilation message

blocks.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main(){
      | ^~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 85340 KB Output is correct
2 Correct 33 ms 82516 KB Output is correct
3 Correct 13 ms 85340 KB Output is correct
4 Correct 14 ms 85288 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 13 ms 85336 KB Output is correct
7 Correct 13 ms 85340 KB Output is correct
8 Correct 35 ms 82512 KB Output is correct
9 Incorrect 12 ms 85340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 85336 KB Output is correct
2 Correct 12 ms 85340 KB Output is correct
3 Correct 27 ms 82508 KB Output is correct
4 Correct 12 ms 85336 KB Output is correct
5 Correct 11 ms 85240 KB Output is correct
6 Correct 32 ms 82516 KB Output is correct
7 Correct 33 ms 82524 KB Output is correct
8 Correct 13 ms 85336 KB Output is correct
9 Incorrect 14 ms 85336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 85340 KB Output is correct
2 Correct 33 ms 82516 KB Output is correct
3 Correct 13 ms 85340 KB Output is correct
4 Correct 14 ms 85288 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 13 ms 85336 KB Output is correct
7 Correct 13 ms 85340 KB Output is correct
8 Correct 35 ms 82512 KB Output is correct
9 Incorrect 12 ms 85340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 85340 KB Output is correct
2 Correct 33 ms 82516 KB Output is correct
3 Correct 13 ms 85340 KB Output is correct
4 Correct 14 ms 85288 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 13 ms 85336 KB Output is correct
7 Correct 13 ms 85340 KB Output is correct
8 Correct 35 ms 82512 KB Output is correct
9 Incorrect 12 ms 85340 KB Output isn't correct
10 Halted 0 ms 0 KB -