#pragma GCC optimize("Ofast,unroll-loops,shrink-wrap-separate,loop-nest-optimize")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native,avx,avx2,fma")
#include <bits/stdc++.h>
#include <tr1/unordered_map>
#include <tr1/unordered_set>
// #include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define mat vector<vector<ll>>
#define mat2 vector<vector<mat>>
#define vi vector<int>
#define vll vector<ll>
#define lll __int128_t
#define psi pair<string, int>
#define pis pair<int, string>
#define pic pair<int, char>
#define pcc pair<char, char>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piiii pair<pii, pii>
#define mii map<int, int>
#define umii tr1::unordered_map<int, int>
#define iter multiset<pair<pll, ll>>::iterator
#define lb lower_bound
#define ub upper_bound
/*
#define fi first
#define se second
*/
/*
#define fi first.first
#define se first.second
#define th second.first
#define fo second.second
*/
/*
#define piii pair<int, pii>
#define fi first
#define se second.fi
#define th second.second
*/
#define piii pair<pii, int>
#define fi first.first
#define se first.th
#define th second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
// using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ost;
const int nax = 500005, block = 320, dax = 2, lim = 2187, lgax = 25, bit = 64, mod = 1000000007, inf = 1000000007;
const ll llax = 1e18;
const double pi = acos(0) * 2, eps = 1e-6;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
/*
const int MAX_MEM = 100000000;
int mpos;
char mem[MAX_MEM];
inline void* operator new(size_t n) {
assert((mpos += n) <= MAX_MEM);
return (void*)(mem + mpos - n);
}
inline void operator delete(void*) {}
*/
inline int read() {
char c = getchar_unlocked();
int t = 0, f = 1;
while (!isdigit(c) && c != EOF)
f = (c == '-' ? -1 : 1), c = getchar_unlocked();
while (isdigit(c) && c != EOF)
t = t * 10 + c - '0', c = getchar_unlocked();
return t * f;
}
inline void read(char* s) {
char c = getchar_unlocked();
while (isspace(c))
c = getchar_unlocked();
while (!isspace(c))
*s++ = c, c = getchar_unlocked();
*s = '\0';
}
/*
struct chash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
*/
vector<int> a[nax];
ll ans;
vector<pair<pll, ll>> ord, ans1;
multiset<pll> s;
int main() {
//IOS
//freopen("in", "r", stdin);
//freopen("out1", "w", stdout);
int m = read(), n = read();
for (int i = 1; i <= n; ++i) {
int c = read(), l = read();
ord.pb({{c, l}, i});
}
sort(rall(ord));
int idx, cur;
for (idx = 0, cur = 0; cur < m * 6; cur += ord[idx++].se) {}
ord[--idx].se -= cur - m * 6;
for (int i = 0; i <= idx; ++i)
s.insert({ord[i].se, i}), ans += ord[i].fi * ord[i].se;
int j = 0;
while (s.rbegin()->first) {
a[j].resize(6);
for (int i = 0; i < 6; ++i)
a[j][i] = (--s.end())->second, s.erase(--s.end());
for (int i = 0; i < 6; ++i)
s.insert({--ord[a[j][i]].se, a[j][i]});
for (int i = 0; i < 6; ++i)
a[j][i] = ord[a[j][i]].th;
sort(all(a[j]));
++j;
}
sort(a, a + j);
printf("%lld\n", ans);
for (int i = 0; i < 6; ++i)
printf("%d ", a[0][i]);
for (int i = 0; i + 1 < j; ++i) {
vi tmp, tmp1;
for (int k = 0; k < 6; ++k)
if (find(all(a[i + 1]), a[i][k]) == a[i + 1].end())
tmp.pb(a[i][k]);
for (int k = 0; k < 6; ++k)
if (find(all(a[i]), a[i + 1][k]) == a[i].end())
ans1.pb({{i + 1, tmp.back()}, a[i + 1][k]}), tmp.pop_back();
}
printf("\n%d\n", (int)ans1.size());
for (pair<pll, ll> p : ans1)
printf("%lld %lld %lld\n", p.fi, p.se, p.th);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Correct |
15 ms |
12396 KB |
Output is correct |
| 3 |
Correct |
693 ms |
28672 KB |
Output is correct |
| 4 |
Correct |
13 ms |
12268 KB |
Output is correct |
| 5 |
Correct |
295 ms |
19432 KB |
Output is correct |
| 6 |
Correct |
10 ms |
12396 KB |
Output is correct |
| 7 |
Correct |
12 ms |
12716 KB |
Output is correct |
| 8 |
Correct |
99 ms |
19164 KB |
Output is correct |
| 9 |
Correct |
841 ms |
42816 KB |
Output is correct |
| 10 |
Execution timed out |
1004 ms |
44804 KB |
Time limit exceeded |
