oj.uz

Submission #718478

# Submission time Handle Problem Language Result Execution time Memory
718478 2023-04-04T07:40:12 Z MinhAnhnd Stove (JOI18_stove) C++14
100 / 100
 73 ms 9408 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8916 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 5 ms 8912 KB Output is correct
4 Correct 5 ms 8916 KB Output is correct
5 Correct 5 ms 8916 KB Output is correct
6 Correct 5 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8912 KB Output is correct
9 Correct 6 ms 8912 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8916 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 5 ms 8912 KB Output is correct
4 Correct 5 ms 8916 KB Output is correct
5 Correct 5 ms 8916 KB Output is correct
6 Correct 5 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8912 KB Output is correct
9 Correct 6 ms 8912 KB Output is correct
10 Correct 7 ms 8932 KB Output is correct
11 Correct 8 ms 8928 KB Output is correct
12 Correct 6 ms 8916 KB Output is correct
13 Correct 8 ms 8936 KB Output is correct
14 Correct 7 ms 8916 KB Output is correct
15 Correct 7 ms 8928 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8916 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 5 ms 8912 KB Output is correct
4 Correct 5 ms 8916 KB Output is correct
5 Correct 5 ms 8916 KB Output is correct
6 Correct 5 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8912 KB Output is correct
9 Correct 6 ms 8912 KB Output is correct
10 Correct 7 ms 8932 KB Output is correct
11 Correct 8 ms 8928 KB Output is correct
12 Correct 6 ms 8916 KB Output is correct
13 Correct 8 ms 8936 KB Output is correct
14 Correct 7 ms 8916 KB Output is correct
15 Correct 7 ms 8928 KB Output is correct
16 Correct 51 ms 9352 KB Output is correct
17 Correct 48 ms 9300 KB Output is correct
18 Correct 50 ms 9408 KB Output is correct
19 Correct 49 ms 9384 KB Output is correct
20 Correct 73 ms 9360 KB Output is correct
21 Correct 51 ms 9292 KB Output is correct
22 Correct 50 ms 9296 KB Output is correct
23 Correct 49 ms 9364 KB Output is correct
24 Correct 61 ms 9292 KB Output is correct