oj.uz

Submission #73402

# Submission time Handle Problem Language Result Execution time Memory
73402 2018-08-28T08:19:36 Z 김세빈(#2270) Radio (Balkan15_RADIO) C++11
45 / 100
 80 ms 4716 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector <ll> L, R;
ll P[101010], K[101010], C[101010];
ll n, k, ans;
ll suml, sumr, cntl, cntr;

int main()
{
	ll b, i, j, x, s;
	
	scanf("%lld%lld", &n, &k);
	
	ans = 1e18;
	
	for(i=1; i<=n; i++){
		scanf("%lld%lld%lld", P + i, K + i, C + i);
	}
	
	if(n > 15){
		for(i=1; i<=n; i++){
			L.push_back(P[i] - K[i]);
			R.push_back(P[i] + K[i]);
			suml += P[i] - K[i];
			cntl ++;
		}
		
		sort(L.begin(), L.end());
		sort(R.begin(), R.end());
		
		for(i=0, j=0; i<n || j<n; ){
			if(j == n || (i != n && L[i] <= R[j])){
				cntl --; suml -= L[i];
				x = L[i]; i ++;
			}
			else{
				cntr ++; sumr += R[j];
				x = R[j]; j ++;
			}
			ans = min(ans, suml - cntl * x + cntr * x - sumr);
		}
	}
	else{
		for(b=0; b<(1 << n); b++){
			L.clear(); R.clear();
			suml = sumr = cntl = cntr = s = 0;
			
			for(i=1; i<=n; i++){
				if(b & (1 << i - 1)){
					L.push_back(P[i] - K[i]);
					R.push_back(P[i] + K[i]);
					suml += P[i] - K[i];
					cntl ++;
				}
				else s += C[i];
			}
			
			if(cntl != k) continue;
			
			sort(L.begin(), L.end());
			sort(R.begin(), R.end());
			
			for(i=0, j=0; i<L.size() || j<R.size(); ){
				if(j == R.size() || (i != L.size() && L[i] <= R[j])){
					cntl --; suml -= L[i];
					x = L[i]; i ++;
				}
				else{
					cntr ++; sumr += R[j];
					x = R[j]; j ++;
				}
				ans = min(ans, suml - cntl * x + cntr * x - sumr - s);
			}
		}
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message

code1.cpp: In function 'int main()':
code1.cpp:53:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     if(b & (1 << i - 1)){
                  ~~^~~
code1.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0, j=0; i<L.size() || j<R.size(); ){
                  ~^~~~~~~~~
code1.cpp:67:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0, j=0; i<L.size() || j<R.size(); ){
                                ~^~~~~~~~~
code1.cpp:68:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j == R.size() || (i != L.size() && L[i] <= R[j])){
        ~~^~~~~~~~~~~
code1.cpp:68:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j == R.size() || (i != L.size() && L[i] <= R[j])){
                          ~~^~~~~~~~~~~
code1.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
code1.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", P + i, K + i, C + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 7 ms 432 KB Output is correct
5 Correct 6 ms 432 KB Output is correct
6 Correct 7 ms 680 KB Output is correct
7 Correct 4 ms 680 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 892 KB Output is correct
2 Correct 15 ms 1528 KB Output is correct
3 Correct 33 ms 2804 KB Output is correct
4 Correct 69 ms 4196 KB Output is correct
5 Correct 75 ms 4684 KB Output is correct
6 Correct 80 ms 4716 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4716 KB Output is correct
2 Incorrect 19 ms 4716 KB Output isn't correct
3 Halted 0 ms 0 KB -