Submission #718478

#	Time	Username	Problem	Language	Result	Execution time	Memory
718478		MinhAnhnd	Stove (JOI18_stove)	C++14	100 / 100	73 ms	9408 KiB

stove

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

//long R,n,m,p,totalsum = 0;
#define limit 300001


using namespace std;

/*
vector<int> graph[limit];
int timer = 0, tin[limit], euler_tour[limit];
//int segtree[800000];  // Segment tree for RMQ

void dfs(int node = 0, int parent = -1) {
	tin[node] = timer;  // The time when we first visit a node
	euler_tour[timer++] = node;
	for (int i : graph[node]) {
		if (i != parent) {
			dfs(i, node);
			euler_tour[timer++] = node;
		}
	}
}

long k = 0;
long tmax[limit*2] ={};
long tmin[limit*2] ={};
#include <bits/stdc++.h>*/

typedef long long ll;
using namespace std;

struct Line {
	bool type;
	long double x;
	ll m, c;
};

bool operator<(Line l1, Line l2) {
	if (l1.type || l2.type) return l1.x < l2.x;
	return l1.m > l2.m;
}

set<Line> cht[1];
long cht_pointer = 0;
//ll h[100001], w[100001], tot = 0, dp[100001];

bool has_prev(set<Line>::iterator it) { return it != cht[cht_pointer].begin(); }
bool has_next(set<Line>::iterator it) {
	return it != cht[cht_pointer].end() && next(it) != cht[cht_pointer].end();
}

long double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
	return (long double)(l1->c - l2->c) / (l2->m - l1->m);
}

void calc_x(set<Line>::iterator it) {
	if (has_prev(it)) {
		Line l = *it;
		l.x = intersect(prev(it), it);
		cht[cht_pointer].insert(cht[cht_pointer].erase(it), l);
	}
}

bool bad(set<Line>::iterator it) {
	if (has_next(it) && next(it)->c <= it->c) return true;
	return (has_prev(it) && has_next(it) &&
	        intersect(prev(it), next(it)) <= intersect(prev(it), it));
}

void add_line(ll m, ll c) {
	set<Line>::iterator it;

	it = cht[cht_pointer].lower_bound({0, 0, m, c});
	if (it != cht[cht_pointer].end() && it->m == m) {
		if (it->c <= c) return;
		cht[cht_pointer].erase(it);
	}

	it = cht[cht_pointer].insert({0, 0, m, c}).first;
	if (bad(it)) cht[cht_pointer].erase(it);
	else {
		while (has_prev(it) && bad(prev(it))) cht[cht_pointer].erase(prev(it));
		while (has_next(it) && bad(next(it))) cht[cht_pointer].erase(next(it));

		if (has_next(it)) calc_x(next(it));
		calc_x(it);
	}
}

ll query(ll h) {
	Line l = *prev(cht[cht_pointer].upper_bound({1, (long double)h, 0, 0}));
	return l.m * h + l.c;
}

/*long long Y,N, parent[limit] = {}, weight[limit] = {}, dp[limit] ={}, incon[limit] = {};
long long distance_[limit] = {};
long long num_child[limit] ={};
vector<long> children[limit];
stack<long> tovisit;
bool visited[limit] = {};

long moveit(ll current){
    if (!children[current].empty()) tovisit.push(current);
    long long sum = 0;
    for (auto i: children[current]){
        //cout<<i<<"checker";
        distance_[i] = distance_[current] + weight[i];
        sum += moveit(i);
        //cout<<sum<<"checker";

    }
    if (children[current].empty()) return (long long) 1;
    num_child[current] = (long long) sum;
    return sum;
}*/
#define T pair<long,long>

struct node{
    long val, sum;
};
long N, M, maxlen = 0;
vector<pair<long,long>> adj[limit];
tuple<long,long,long> temp[limit];
pair<long,long> roadid[limit];
pair<long,pair<long,long>> dist[limit];

void dijkstra(int src) {  // Source and destination
	//for (int i = 0; i < N; ++i) dist[i] = LONG_MAX;
	// Set all distances to infinity
    for (int i = 1; i <= N; i++) {dist[i].first = LONG_MAX; dist[i].second.first = -1;dist[i].second.second = -1;}
	priority_queue<T, vector<T>, greater<T>> pq;
	dist[src].first = 0;  // The shortest path from a node to itself is 0
	pq.push({0, src});

	while (pq.size()) {
		long cdist;
		long node;
		tie(cdist, node) = pq.top();

		pq.pop();
		if (cdist != dist[node].first) continue;
		for (pair<int, int> i : adj[node]) {
            long distance = roadid[i.second].first;
            if (distance == LONG_MAX) continue;
            //cout<<distance<<" "<<cdist<<" "<<i.first<<endl;
			// If we can reach a neighbouring node faster,
			// we update its minimum distance
			if (cdist + distance< dist[i.first].first) {
			    dist[i.first].second.first = node;
			    dist[i.first].second.second = i.second;
                dist[i.first].first = cdist + distance;
				pq.push({dist[i.first].first, i.first});
			}
		}
	}
}
#define lim 100001
int main(){
  long N,K,A[lim] = {},Delta[lim] = {},total = 0;
  cin>>N>>K;
  for(long i = 1;i<=N;i++){
    cin>>A[i];
  }
  total = A[N]-A[1]+1;
  for(long i = 1;i<=N-1;i++){
    Delta[i]= A[i+1]-A[i];
  }
  sort(Delta + 1,Delta+N,greater<long>());
  for(long i = 1;i<=K-1;i++){
    total -=(Delta[i]-1);
  }
  cout<<total;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50