Submission #249546

#	Time	Username	Problem	Language	Result	Execution time	Memory
249546		panda	Stove (JOI18_stove)	C++14	100 / 100	56 ms	16172 KiB

stove

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;

const ll MX = 1e5 + 5;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

#define F0R(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define ps(x) cout << x << "\n";
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) begin(x), end(x)
#define sz(x) (ll)x.size()
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
		ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
		// cin.exceptions(cin.failbit); 
		// throws exception when do smth illegal
		// ex. try to read letter llo ll
		if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

ll N, K, A[MX];
ll visited[MX], last;
set<ll> adj[MX];

void deleteEdge(ll u, ll v) {
	adj[v].erase(u); // v < u so there for it's like v polling to u :P.
}

void dfs(ll u) {
	visited[u] = 1;
	bool leaf = !sz(adj[u]);
	

	for (auto x: adj[u]) dfs(x);

	if (leaf) last = u;
}

int main() {
	setIO();
	cin >> N >> K;
	F0R(i, N) cin >> A[i];
	sort(A, A + N);

	vector<pair<ll, pi> > v;
	FOR(i, 1, N) {
		v.pb(mp(A[i] + 1 - A[i - 1], mp(i, i - 1)));
		adj[i - 1].insert(i);
	}
	sort(all(v));

	K--; // find a way to represent my drawing and to find the sum.

	// represent it as a graph.
	while (K--) {
		pair<ll, pi> cur = v.back();
		v.pop_back();
		//cout << cur.s.f << ", " << cur.s.s << "\n";
		deleteEdge(cur.s.f, cur.s.s);
	} 

	ll ans = 0;
	F0R(i, N) if (!visited[i]) {
		dfs(i);
		ans += A[last] + 1 - A[i];
		//cout << i << " " << last << "\n";
	}
	ps(ans);

}

Compilation message (stderr)

stove.cpp: In function 'void setIn(std::__cxx11::string)':
stove.cpp:28:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
stove.cpp: In function 'void setOut(std::__cxx11::string)':
stove.cpp:29:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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