oj.uz

Submission #198836

# Submission time Handle Problem Language Result Execution time Memory
198836 2020-01-27T20:11:16 Z ZwariowanyMarcin Kisik (COCI19_kisik) C++14
90 / 90
 1637 ms 65912 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define ld long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);


using namespace std;		

const int nax = 1000100;

int n, k;
pair <int, int> x[nax];

multiset <int> s;
vector <int> vec;

LL sum = 0;
LL ans = 1e18 + 111;

void add(int val) {
	sum += val;
	s.insert(val);
	if (ss(s) >= k) {
		sum -= *--s.end();
		s.erase(--s.end());
	}
}

int main() {		
	scanf ("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf ("%d%d", &x[i].se, &x[i].fi);
	}	
	sort (x + 1, x + n + 1);
	
	for (int i = 1; i <= n;) {
		vec.clear();
		int j = i;
		while (j <= n && x[i].fi == x[j].fi) {
			vec.pb(x[j].se);
			j++;
		}
		sort(vec.begin(), vec.end());
		for (int j = 1; j < ss(vec); ++j)
			add(vec[j]);
		if (ss(s) == k - 1)
			ans = min(ans, 1LL * x[i].fi * (sum + x[i].se));
		add(vec[0]);
		i = j;
	}
	printf ("%lld", ans);		
	
	return 0;
}

Compilation message

kisik.cpp: In function 'int main()':
kisik.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
  ~~~~~~^~~~~~~~~~~~~~~~
kisik.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &x[i].se, &x[i].fi);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 296 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 6648 KB Output is correct
2 Correct 861 ms 28640 KB Output is correct
3 Correct 978 ms 40952 KB Output is correct
4 Correct 852 ms 38008 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 15864 KB Output is correct
2 Correct 63 ms 5624 KB Output is correct
3 Correct 157 ms 10488 KB Output is correct
4 Correct 706 ms 33144 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 15192 KB Output is correct
2 Correct 267 ms 12360 KB Output is correct
3 Correct 262 ms 12024 KB Output is correct
4 Correct 1637 ms 65912 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 14968 KB Output is correct
2 Correct 1343 ms 42408 KB Output is correct
3 Correct 287 ms 15352 KB Output is correct
4 Correct 1043 ms 46460 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 19704 KB Output is correct
2 Correct 851 ms 35864 KB Output is correct
3 Correct 600 ms 25336 KB Output is correct
4 Correct 389 ms 22008 KB Output is correct