Submission #1178534
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;
int n, m, p, q, r;
vector<vvi> yz;
int ans;
int calculate_max_value(vi& girl) {
vi value_of_boy(m, 0);
rep (i, p) {
for (auto y_z : yz[girl[i]]) {
value_of_boy[y_z[0]] += y_z[1];
}
}
sort(all(value_of_boy), greater<int>());
int ret = 0;
rep (i, q) {
ret += value_of_boy[i];
}
return ret;
}
template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first1, BidirectionalIterator last1, BidirectionalIterator first2, BidirectionalIterator last2) {
if (first1 == last1 || first2 == last2) {
return false;
}
BidirectionalIterator m1 = last1;
BidirectionalIterator m2 = last2;
--m2;
while (--m1 != first1 && !(*m1 < *m2)) {}
bool result = (m1 == first1 && !(*first1 < *m2));
if (!result) {
while (first2 != m2 && !(*m1 < *first2)) {
++first2;
}
first1 = m1;
std::iter_swap(first1, first2);
++first1;
++first2;
}
if (first1 != last1 && first2 != last2) {
m1 = last1; m2 = first2;
while (m1 != first1 && m2 != last2) {
std::iter_swap(--m1, m2);
++m2;
}
std::reverse(first1, m1);
std::reverse(first1, last1);
std::reverse(m2, last2);
std::reverse(first2, last2);
}
return !result;
}
template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) {
return next_combination(first, middle, middle, last);
}
void solve() {
ans = 0;
vi girl(n);
rep (i, n) {
girl[i] = i;
}
do {
ans = max(ans, calculate_max_value(girl));
} while (next_combination(girl.begin(), girl.begin() + p, girl.end()));
}
int main() {
scanf("%d%d%d%d%d", &n, &m, &p, &q, &r);
yz.resize(n);
rep (i, r) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
x -= 1;
y -= 1;
yz[x].push_back((vi){y, z});
}
solve();
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - バレンタインデー |
User |
tspcx |
Language |
C++14 (Clang 3.8.0) |
Score |
100 |
Code Size |
2844 Byte |
Status |
AC |
Exec Time |
333 ms |
Memory |
384 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0-sample01.txt, subtask0-sample02.txt |
Subtask1 |
subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt |
Subtask2 |
subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0-sample01.txt |
AC |
1 ms |
256 KB |
subtask0-sample02.txt |
AC |
1 ms |
256 KB |
subtask1-01.txt |
AC |
1 ms |
256 KB |
subtask1-02.txt |
AC |
1 ms |
256 KB |
subtask1-03.txt |
AC |
1 ms |
256 KB |
subtask1-04.txt |
AC |
1 ms |
256 KB |
subtask1-05.txt |
AC |
1 ms |
256 KB |
subtask1-06.txt |
AC |
1 ms |
256 KB |
subtask1-07.txt |
AC |
1 ms |
256 KB |
subtask1-08.txt |
AC |
1 ms |
256 KB |
subtask1-09.txt |
AC |
1 ms |
256 KB |
subtask1-10.txt |
AC |
1 ms |
256 KB |
subtask1-11.txt |
AC |
1 ms |
256 KB |
subtask1-12.txt |
AC |
1 ms |
256 KB |
subtask1-13.txt |
AC |
1 ms |
256 KB |
subtask1-14.txt |
AC |
1 ms |
256 KB |
subtask1-15.txt |
AC |
1 ms |
256 KB |
subtask1-16.txt |
AC |
1 ms |
256 KB |
subtask1-17.txt |
AC |
3 ms |
384 KB |
subtask1-18.txt |
AC |
1 ms |
256 KB |
subtask1-19.txt |
AC |
1 ms |
256 KB |
subtask1-20.txt |
AC |
1 ms |
256 KB |
subtask1-21.txt |
AC |
1 ms |
256 KB |
subtask1-22.txt |
AC |
1 ms |
256 KB |
subtask1-23.txt |
AC |
1 ms |
256 KB |
subtask1-24.txt |
AC |
1 ms |
256 KB |
subtask1-25.txt |
AC |
1 ms |
256 KB |
subtask1-26.txt |
AC |
1 ms |
256 KB |
subtask1-27.txt |
AC |
1 ms |
256 KB |
subtask1-28.txt |
AC |
1 ms |
256 KB |
subtask1-29.txt |
AC |
1 ms |
256 KB |
subtask1-30.txt |
AC |
1 ms |
256 KB |
subtask2-01.txt |
AC |
1 ms |
256 KB |
subtask2-02.txt |
AC |
1 ms |
256 KB |
subtask2-03.txt |
AC |
1 ms |
256 KB |
subtask2-04.txt |
AC |
1 ms |
256 KB |
subtask2-05.txt |
AC |
114 ms |
256 KB |
subtask2-06.txt |
AC |
135 ms |
256 KB |
subtask2-07.txt |
AC |
153 ms |
256 KB |
subtask2-08.txt |
AC |
183 ms |
256 KB |
subtask2-09.txt |
AC |
261 ms |
256 KB |
subtask2-10.txt |
AC |
309 ms |
256 KB |
subtask2-11.txt |
AC |
314 ms |
256 KB |
subtask2-12.txt |
AC |
333 ms |
256 KB |
subtask2-13.txt |
AC |
333 ms |
256 KB |
subtask2-14.txt |
AC |
332 ms |
256 KB |
subtask2-15.txt |
AC |
333 ms |
256 KB |
subtask2-16.txt |
AC |
333 ms |
256 KB |
subtask2-17.txt |
AC |
333 ms |
256 KB |
subtask2-18.txt |
AC |
332 ms |
256 KB |
subtask2-19.txt |
AC |
333 ms |
256 KB |
subtask2-20.txt |
AC |
332 ms |
256 KB |