Submission #159348


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

int main()
{
    int k, n;
    cin >> k >> n;

    vector<PLL> ad;
    REP(i, n) {
        int a, b;
        cin >> a >> b;
        ad.push_back(PLL(a, b));
    }
    SORT(ad);

    LL ans = 0;

    REP(i, k) {
        ans += ad[0].first;
        ad[0].first += ad[0].second;

        if(ad[0].first > ad[1].first) {
            PLL a = ad[0];
            vector<PLL>::iterator it = ad.begin();
            ad.erase(it);
            it = lower_bound(ALL(ad), a);
            ad.insert(it, a);
        }
    }

    cout << ans << endl;
}

Submission Info

Submission Time
Task C - 増築王高橋君
User awaki75
Language C++ (G++ 4.6.4)
Score 40
Code Size 896 Byte
Status
Exec Time 2036 ms
Memory 3088 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample-01.txt, subtask0_sample-02.txt
Subtask1 30 / 30 subtask0_sample-01.txt, subtask0_sample-02.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
Subtask2 10 / 10 subtask0_sample-01.txt, subtask0_sample-02.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, 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
Subtask3 0 / 15 subtask0_sample-01.txt, subtask0_sample-02.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, 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, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Subtask4 0 / 45 subtask0_sample-01.txt, subtask0_sample-02.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, 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, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask4_01.txt, subtask4_02.txt, subtask4_03.txt, subtask4_04.txt, subtask4_05.txt, subtask4_06.txt, subtask4_07.txt, subtask4_08.txt, subtask4_09.txt, subtask4_10.txt, subtask4_11.txt, subtask4_12.txt, subtask4_13.txt, subtask4_14.txt
Case Name Status Exec Time Memory
subtask0_sample-01.txt 21 ms 804 KB
subtask0_sample-02.txt 21 ms 704 KB
subtask1_01.txt 20 ms 924 KB
subtask1_02.txt 21 ms 928 KB
subtask1_03.txt 20 ms 928 KB
subtask1_04.txt 21 ms 804 KB
subtask1_05.txt 21 ms 804 KB
subtask1_06.txt 20 ms 804 KB
subtask1_07.txt 20 ms 800 KB
subtask1_08.txt 21 ms 804 KB
subtask1_09.txt 21 ms 816 KB
subtask1_10.txt 21 ms 816 KB
subtask1_11.txt 21 ms 804 KB
subtask1_12.txt 20 ms 800 KB
subtask2_01.txt 21 ms 796 KB
subtask2_02.txt 23 ms 804 KB
subtask2_03.txt 22 ms 932 KB
subtask2_04.txt 21 ms 924 KB
subtask2_05.txt 22 ms 796 KB
subtask2_06.txt 58 ms 1052 KB
subtask2_07.txt 64 ms 888 KB
subtask2_08.txt 52 ms 920 KB
subtask2_09.txt 79 ms 924 KB
subtask2_10.txt 93 ms 936 KB
subtask2_11.txt 92 ms 1056 KB
subtask2_12.txt 46 ms 804 KB
subtask3_01.txt 21 ms 800 KB
subtask3_02.txt 21 ms 804 KB
subtask3_03.txt 63 ms 928 KB
subtask3_04.txt 167 ms 2972 KB
subtask3_05.txt 25 ms 928 KB
subtask3_06.txt 986 ms 808 KB
subtask3_07.txt 1987 ms 1436 KB
subtask3_08.txt 2029 ms 2960 KB
subtask3_09.txt 2036 ms 3088 KB
subtask3_10.txt 2029 ms 2968 KB
subtask3_11.txt 2030 ms 2920 KB
subtask3_12.txt 2029 ms 1956 KB
subtask4_01.txt 2030 ms 2972 KB
subtask4_02.txt 2029 ms 800 KB
subtask4_03.txt 2029 ms 928 KB
subtask4_04.txt 2029 ms 2956 KB
subtask4_05.txt 2028 ms 884 KB
subtask4_06.txt 158 ms 796 KB
subtask4_07.txt 774 ms 808 KB
subtask4_08.txt 54 ms 780 KB
subtask4_09.txt 2030 ms 2972 KB
subtask4_10.txt 2029 ms 932 KB
subtask4_11.txt 2029 ms 2972 KB
subtask4_12.txt 2029 ms 2968 KB
subtask4_13.txt 2030 ms 2968 KB
subtask4_14.txt 772 ms 800 KB