This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> v(n), c(n);
REP(i, n) cin >> v[i] >> c[i];
ll res = 0;
for (int bm = 0; bm < (1<<n); bm++) {
if (__builtin_popcount(bm) != m) continue;
vector<int> a;
REP(j, n) {
if (bm&(1<<j)) a.eb(j);
}
ll sum = 0;
for (auto j : a) sum += v[j];
do {
ll x = 0;
REP(i, m-1) x += abs(c[a[i]]-c[a[i+1]]);
x += abs(c[a[m-1]]-c[a[0]]);
res = max(res, sum-x);
} while (next_permutation(all(a)));
}
cout << res << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |