| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 275850 |
2020-08-20T08:01:00 Z |
문홍윤(#5111) |
Radio (Balkan15_RADIO) |
C++17 |
|
37 ms |
416 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;
int n, k;
LL x[110], p[110], s[110], anss=llinf;
vector<LL> l, r;
bool ch[110];
LL solve(){
LL ret=llinf, suml=0, cntl=0, sumr=0, cntr=0, temp=0;
l.clear(); r.clear();
for(int i=1; i<=n; i++){
if(!ch[i]){
temp+=s[i];
continue;
}
l.eb(x[i]-p[i]);
r.eb(x[i]+p[i]);
suml+=x[i]-p[i];
cntl++;
}
svec(l); svec(r);
for(int 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];
ret=min(ret, suml-cntl*l[i]+cntr*l[i]-sumr-temp);
i++;
}
else{
cntr++;
sumr+=r[j];
ret=min(ret, suml-cntl*r[j]+cntr*r[j]-sumr-temp);
j++;
}
}
return ret;
}
int main(){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++)scanf("%lld %lld %lld", &x[i], &p[i], &s[i]);
for(int bt=0; bt<(1<<n); bt++){
if(__builtin_popcount(bt)!=k)continue;
LL suml=0, cntl=0, sumr=0, cntr=0, temp=0;
l.clear(); r.clear();
for(int i=1; i<=n; i++){
if(bt&(1<<(i-1))){
l.eb(x[i]-p[i]);
r.eb(x[i]+p[i]);
suml+=x[i]-p[i];
cntl++;
}
else temp+=s[i];
}
svec(l); svec(r);
for(int 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];
anss=min(anss, suml-cntl*l[i]+cntr*l[i]-sumr-temp);
i++;
}
else{
cntr++;
sumr+=r[j];
anss=min(anss, suml-cntl*r[j]+cntr*r[j]-sumr-temp);
j++;
}
}
}
printf("%lld", anss);
}
Compilation message
radio.cpp: In function 'LL solve()':
radio.cpp:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0, j=0; i<l.size()||j<r.size(); ){
| ~^~~~~~~~~
radio.cpp:37:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0, j=0; i<l.size()||j<r.size(); ){
| ~^~~~~~~~~
radio.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if(j==r.size()||(i!=l.size()&&l[i]<=r[j])){
| ~^~~~~~~~~~
radio.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | if(j==r.size()||(i!=l.size()&&l[i]<=r[j])){
| ~^~~~~~~~~~
radio.cpp: In function 'int main()':
radio.cpp:71:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0, j=0; i<l.size()||j<r.size(); ){
| ~^~~~~~~~~
radio.cpp:71:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0, j=0; i<l.size()||j<r.size(); ){
| ~^~~~~~~~~
radio.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(j==r.size()||(i!=l.size()&&l[i]<=r[j])){
| ~^~~~~~~~~~
radio.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(j==r.size()||(i!=l.size()&&l[i]<=r[j])){
| ~^~~~~~~~~~
radio.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
radio.cpp:56:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
56 | for(int i=1; i<=n; i++)scanf("%lld %lld %lld", &x[i], &p[i], &s[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
256 KB |
Output is correct |
| 6 |
Correct |
1 ms |
256 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
