Submission #342775

#TimeUsernameProblemLanguageResultExecution timeMemory
342775SSYernarK blocks (IZhO14_blocks)C++14
0 / 100
1 ms512 KiB
//#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], k; ll dp[N][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 rec(int l, int r, int optl = 1, int optr = n) { ll mn = INF; int pos = 0, mid = (l + r) / 2; for (int i = optl; i <= min(mid, optr); i++) { ll cost = dp[k - 1][i] + get(i + 1, mid); if (cost < mn) { mn = cost; pos = i; } } dp[k][mid] = mn; if (l == r) return; rec(l, mid, optl, pos); rec(mid + 1, r, pos, optr); } 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 (k = 2; k <= K; k++) { rec(1, n); } // 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...