oj.uz

답안 #238194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238194 2020-06-10T07:17:54 Z NONAME Hokej (COCI17_hokej) C++17
120 / 120
 194 ms 16376 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define el '\n'
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
using namespace std;

typedef long long ll;

const int N = 5e5 + 10;

ll n, m, ans, ps[N], a[N], b[N], ost[N], start[N];
vector <pair <ll, pair <int, int> > > res;

bool cmp0(int x, int y) { return a[x] > a[y]; }
bool cmp1(int x, int y) { return b[x] > b[y]; }

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> m >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        ost[i] = b[i];
        ps[i] = i;
    }

    sort(ps, ps + n, cmp0);

    int p = 0;

    for (int team = 0; team < 6; ++team) {
        int cur = 0;
        while (cur < m) {
            int o = min(m - cur, ost[ps[p]]);

            ost[ps[p]] -= o;
            ans += o * a[ps[p]];

            p += !ost[ps[p]];

            cur += o;
        }
    }

    if (p == n || b[ps[p]] == ost[ps[p]]) {}
        else {
            b[ps[p]] -= ost[ps[p]];
            p++;
        }

    sort(ps, ps + p, cmp1);

    p = 0;

    for (int team = 0; team < 6; ++team) {
        start[team] = ps[p] + 1;
        int cur = b[ps[p]], lst = ps[p++];

        while (cur < m) {
            int o = min(m - cur, b[ps[p]]);

            b[ps[p]] -= o;
            res.pb(mp(cur, mp(lst + 1, ps[p] + 1)));
            lst = ps[p];

            p += !b[ps[p]];

            cur += o;
        }
    }

    sort(all(res));

    cout << ans << el;
    for (int i = 0; i < 6; ++i)
        cout << start[i] << ' ';
    cout << el << sz(res) << el;
    for (int i = 0; i < sz(res); ++i)
        cout << res[i].ft << ' ' << res[i].sd.ft << ' ' << res[i].sd.sd << el;
}

Subtask #1
120.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 12 ms 1152 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 37 ms 3884 KB Output is correct
9 Correct 183 ms 16376 KB Output is correct
10 Correct 194 ms 16376 KB Output is correct