# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
200911 | SamAnd | Hokej (COCI17_hokej) | C++17 | 207 ms | 8952 KiB |
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;
const int N = 500005;
struct ban
{
int i;
int k, d;
};
bool operator<(const ban& a, const ban& b)
{
return a.k < b.k;
}
bool so(const ban& a, const ban& b)
{
return a.d < b.d;
}
int m, n;
ban a[N];
int u[6];
int p[6];
int s[6];
int q[N];
vector<pair<int, pair<int, int> > > v;
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; ++i)
{
a[i].i = i;
scanf("%d%d", &a[i].k, &a[i].d);
}
sort(a + 1, a + n + 1);
long long ans = 0;
int j = 0;
for (int i = n; i >= 1; --i)
{
a[i].d = min(a[i].d, m);
while (1)
{
if (j == 6)
break;
if (u[j] + a[i].d <= m)
{
if (p[j] == 0)
s[j] = a[i].i;
else
{
if (u[j] != m)
v.push_back({u[j], {p[j], a[i].i}});
}
p[j] = a[i].i;
ans += (a[i].d * 1LL * a[i].k);
q[i] += (a[i].d);
u[j] += a[i].d;
a[i].d = 0;
break;
}
else
{
if (p[j] == 0)
s[j] = a[i].i;
else
{
if (u[j] != m)
v.push_back({u[j], {p[j], a[i].i}});
}
p[j] = a[i].i;
ans += ((m - u[j]) * 1LL * a[i].k);
q[i] += (m - u[j]);
a[i].d -= (m - u[j]);
u[j] = m;
++j;
}
}
}
for (int i = 1; i <= n; ++i)
{
a[i].d = q[i];
}
sort(a + 1, a + n + 1, so);
ans = 0;
j = 0;
memset(u, 0, sizeof u);
memset(p, 0, sizeof p);
memset(s, 0, sizeof s);
v.clear();
for (int i = n; i >= 1; --i)
{
a[i].d = min(a[i].d, m);
while (1)
{
if (j == 6)
break;
if (u[j] + a[i].d <= m)
{
if (p[j] == 0)
s[j] = a[i].i;
else
{
if (u[j] != m)
v.push_back({u[j], {p[j], a[i].i}});
}
p[j] = a[i].i;
ans += (a[i].d * 1LL * a[i].k);
q[i] += (a[i].d);
u[j] += a[i].d;
a[i].d = 0;
break;
}
else
{
if (p[j] == 0)
s[j] = a[i].i;
else
{
if (u[j] != m)
v.push_back({u[j], {p[j], a[i].i}});
}
p[j] = a[i].i;
ans += ((m - u[j]) * 1LL * a[i].k);
q[i] += (m - u[j]);
a[i].d -= (m - u[j]);
u[j] = m;
++j;
}
}
}
printf("%lld\n", ans);
for (int i = 0; i < 6; ++i)
printf("%d ", s[i]);
printf("\n");
sort(v.begin(), v.end());
printf("%d\n", v.size());
for (int i = 0; i < v.size(); ++i)
printf("%d %d %d\n", v[i].first, v[i].second.first, v[i].second.second);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |