Submission #1098069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098069		anhthi	K blocks (IZhO14_blocks)	C++14	0 / 100	0 ms	348 KiB

blocks

#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 (stderr)

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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47