oj.uz

Submission #93511

# Submission time Handle Problem Language Result Execution time Memory
93511 2019-01-09T06:14:10 Z Pancake Stove (JOI18_stove) C++14
100 / 100
 36 ms 6376 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>	
#include <stdio.h>    
 
using namespace std;
     
#define F first
#define S second
#define lb lower_bound          	    
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcount                                                                                        
#define sqr(x) ((x) * (x))
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;                                  
const int N = (int)2e5 + 123;
const ll inf = (ll)3e18 + 1;
                                       
const double pi = acos(-1.0);
const double eps = 1e-7;
const int dx[] = {0, 0, 1, 0, -1};							
const int dy[] = {0, 1, 0, -1, 0};  		
 
int n, k, ans, a[N], res[N], p[N], sz[N], e;

int get (int v) {
	if (v == p[v]) return v;
	return p[v] = get (p[v]);
}

inline void unite (int x, int y, int cost) {
	int u = get (x), v = get (y);
	if (u == v) return;
	if (sz[u] < sz[v]) swap (u, v);
	sz[u] += sz[v];
	p[v] = u;
	e --;
	ans += cost;
}

inline void boost () {
	ios_base :: sync_with_stdio (NULL);
	cin.tie (NULL), cout.tie (NULL);          
}

inline void Solve () {
	cin >> n >> k;
	e = n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	vector < pair <int, pii> > v;
	for (int i = 1; i <= n; i ++) p[i] = i, sz[i] = 1;
	for (int i = 1; i < n; i ++) v.pb ({a[i + 1] - a[i], {i, i + 1} });
	sort (all (v));
	for (auto it : v) {
		if (e == k) break;
		int cost = it.F, x = it.S.F, y = it.S.S;
		unite (x, y, cost);
	}
	cout << ans + k;
}
                  
main () {                                       
//	freopen (".in", "r", stdin);    
//	freopen (".out", "w", stdout); 	          
	boost ();
	int tt = 1;
//	cin >> tt;   
	while (tt --) {
		Solve ();
	}                                               
	return 0;      
}

Compilation message

stove.cpp:79:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {                                       
       ^

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 35 ms 6376 KB Output is correct
17 Correct 36 ms 6248 KB Output is correct
18 Correct 36 ms 6248 KB Output is correct
19 Correct 35 ms 6248 KB Output is correct
20 Correct 36 ms 6248 KB Output is correct
21 Correct 34 ms 6248 KB Output is correct
22 Correct 33 ms 6256 KB Output is correct
23 Correct 34 ms 6248 KB Output is correct
24 Correct 33 ms 6248 KB Output is correct