oj.uz

Submission #1098068

# Submission time Handle Problem Language Result Execution time Memory
1098068 2024-10-09T03:00:30 Z anhthi K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define left _left
#define right _right
#define ll long long
#define sz(s) ((int)(s).size())
#define ALL(v) (v).begin(), (v).end()
 
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define FOREACH(x, a) for (auto x : (a))
 
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1LL)
#define popcount __builtin_popcountll
 
template<class T1, class T2> inline bool maximize(T1 &x, T2 y) {
    T1 EPS = 1e-9;
    if (x + EPS < y) return x = y, true;
    return false;
}
template<class T1, class T2> inline bool minimize(T1 &x, T2 y) {
    T1 EPS = 1e-9;
    if (x > y + EPS) return x = y, true;
    return false;
}
template<class T> inline vector<T> remove_duplicate(vector<T> a) {
    sort(ALL(a)); a.resize(unique(ALL(a))-a.begin());
    return a;
}
 
#define TASK "elecar"
void online() {
    freopen(TASK".inp", "r", stdin);
    freopen(TASK".out", "w", stdout);
}
const ll oo = 4e18 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
 
const int MAX = (int) 1e5 + 5;
 
int n, k;
ll a[MAX];
 
namespace sub_one {
 
    void perform() {
        #define Fast vector<vector<ll>>
        Fast dp(n+1, vector<ll>(k+1, oo));
        Fast max_cost(n+1, vector<ll>(n+1, 0));
 
        FOR(i, 1, n) FOR(j, i, n) {
            if (i == j)
                max_cost[i][j] = a[j];
            else max_cost[i][j] = max(max_cost[i][j-1], a[j]);
        }
 
        dp[0][0] = 0;
 
        FOR(i, 1, n) FOR(j, 1, k) {
            FOR(r, 0, i-1) {
                minimize(dp[i][j], dp[r][j-1] + max_cost[r+1][i]);
                if (max_cost[r + 1][i] >= a[i])
                    break;
            }
        }
 
        cout << dp[n][k] << "\n";
    }
}
 
signed main(void) {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
 
    #define CHECK 25000000
    if (n * k <= CHECK)
        return sub_one::perform(), 0;
 
    return 0;
}

Compilation message

blocks.cpp: In function 'void online()':
blocks.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen(TASK".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen(TASK".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Incorrect 0 ms 476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -