oj.uz

Submission #342772

# Submission time Handle Problem Language Result Execution time Memory
342772 2021-01-02T18:32:06 Z SSYernar K blocks (IZhO14_blocks) C++17
53 / 100
 1000 ms 1388 KB 
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
     
using namespace std;
//using namespace __gnu_pbds;
     
void err(istream_iterator<string> it) {cout << '\n';}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    string s = typeid(a).name();
    cout << "[" << *it << " = ";
    cout << a;
    cout << "] ";
    err(++it, args...);
}
     
#define F first
#define S second
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pf push_front
#define db double
#define ld long double
#define ofk order_of_key
#define fbo find_by_order
#define ppb pop_back
#define ppf pop_front
#define br cout << '\n'
#define pll pair<long long, long long>
#define here cout << "HERE\n"
#define bruh cout << "BRUH\n"
#define all(x) (x).begin(),(x).end()
#define __ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define TEST int TT; cin >> TT; for(int T = 1; T <= TT; T++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define lb lower_bound
#define ub upper_bound
    
int gcd(int a, int b) {if (a < b) swap(a, b); return b ? gcd(b, a % b) : a;}
ll gcd(ll a, ll b) {if (a < b) swap(a, b); return b ? gcd(b, a % b) : a;}
   
pair<int, int> dx[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
     
int inf = 2e9 + 7;
ll INF = 9e18 + 7;
//ld pi = 3.1415926535897932384626433;
db eps = 1e-7;
//ld EPS = 1e-9;
int mod = 1e9 + 7;
int mod2 = 1000010029;
int BASE = 1000117;
int base = 29;
ll MOD = 1e15 + 7;
    
//mt19937 lol(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
    
//random_device random_device;
//mt19937 generator(random_device());
    

void Add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
void Sub(int &a, int b) {
    a -= b;
    if (a < 0) a += mod;
}
int add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}
int sub(int a, int b) {
    a -= b;
    if (a < 0) a += mod;
    return a;
}
int mul(int a, int b) {
    return a * 1ll * b % mod;
}
int bp(int a, int n, int mOd = mod) {
    if (n == 0) return 1;
    int res = bp(a, n / 2, mOd);
    res = res * 1ll * res % mOd;
    if (n & 1) res = res * 1ll * a % mOd;
    return res;
}
int inv(int a, int mOd = mod) {
    return bp(a, mOd - 2, mOd);
}
bool is_prime(int a) {
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0) return 0;
    }
    return 1;
}

const bool multiple_tests = 0;
const int N = 2e5 + 7;

//#define int long long
#define pii pair<int, int>

int n, K, a[N], mx, p[N], t[N][20];
ll dp[101][101];

int get(int l, int r) {
    int pw = p[r - l + 1];
    return max(t[l][pw], t[r - (1 << pw) + 1][pw]);
}

void solve() {
    cin >> n >> K;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    p[1] = 0;
    t[1][0] = a[1];
    for (int i = 2; i <= n; i++) {
        p[i] = log2(i);
        t[i][0] = a[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            t[i][j] = max(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    
    for (int i = 1; i <= n; i++) {
        dp[1][i] = get(1, i);
    }
    for (int k = 2; k <= K; k++) {
        for (int i = 1; i <= n; i++) {
            dp[k][i] = INF;
            for (int j = 1; j < i; j++) {
                dp[k][i] = min(dp[k][i], dp[k - 1][j] + get(j + 1, i));
            }
        }
    }
    cout << dp[K][n];
}
// KEEP IT SIMPLE


signed main() { __
//  freopen("condense2.in", "r", stdin);
//  freopen("condense2.out", "w", stdout);
    int TT = 1;
    if (multiple_tests) cin >> TT;
    for (int testcase = 1; testcase <= TT; testcase++) {
        solve();
        cout << '\n';
    }
        
//    #ifndef SSYernar
//      cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
//    #endif
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 0 ms 364 KB Output is correct
22 Correct 0 ms 364 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 0 ms 364 KB Output is correct
29 Correct 0 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 0 ms 364 KB Output is correct
32 Correct 0 ms 364 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 2 ms 364 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 0 ms 364 KB Output is correct
42 Correct 0 ms 364 KB Output is correct
43 Correct 1 ms 236 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 0 ms 364 KB Output is correct
47 Correct 0 ms 364 KB Output is correct
48 Correct 1 ms 364 KB Output is correct
49 Correct 1 ms 364 KB Output is correct
50 Correct 0 ms 364 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 2 ms 512 KB Output is correct
54 Correct 2 ms 492 KB Output is correct
55 Correct 2 ms 384 KB Output is correct
56 Correct 2 ms 492 KB Output is correct
57 Correct 2 ms 492 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 0 ms 364 KB Output is correct
22 Correct 0 ms 364 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 0 ms 364 KB Output is correct
29 Correct 0 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 0 ms 364 KB Output is correct
32 Correct 0 ms 364 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 2 ms 364 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 0 ms 364 KB Output is correct
42 Correct 0 ms 364 KB Output is correct
43 Correct 1 ms 236 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 0 ms 364 KB Output is correct
47 Correct 0 ms 364 KB Output is correct
48 Correct 1 ms 364 KB Output is correct
49 Correct 1 ms 364 KB Output is correct
50 Correct 0 ms 364 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 2 ms 512 KB Output is correct
54 Correct 2 ms 492 KB Output is correct
55 Correct 2 ms 384 KB Output is correct
56 Correct 2 ms 492 KB Output is correct
57 Correct 2 ms 492 KB Output is correct
58 Execution timed out 1087 ms 1388 KB Time limit exceeded
59 Halted 0 ms 0 KB -