Submission #3223046


Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <queue>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

int n;
LL cost;

vector<LL> x;

LL ans;

LL f(LL qsize) {
    vector<LL> y = x;

    LL res = 0;

    queue<PLL> q;

    FORN(i, qsize) {
        auto e = y.back();
        y.pop_back();

        res += e + cost;

        q.push(MP(e, 1));
    }

    while (!y.empty()) {
        auto e = y.back();
        y.pop_back();

        auto f = q.front();
        q.pop();

        res += (f.FF - e) * (f.SS + 1) * (f.SS + 1) + cost;

        q.push(MP(e, f.SS + 1));
    }

    while (!q.empty()) {
        auto f = q.front();
        q.pop();

        res += f.FF * (f.SS + 1) * (f.SS + 1) + cost;
    }

    ans = min(ans, res);
    return res;
}

int main() {
    GI(n);
    GLL(cost);

    x.resize(n);

    FORN(i, n) {
        GLL(x[i]);
    }

    ans = 1LL * INF * INF;

    LL lo = 1;
    LL hi = n;
    
    while (lo < hi) {
        auto mid = (lo + hi) / 2;

        if (f(mid) < f(mid + 1)) {
            hi = mid;
        }
        else {
            lo = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

Submission Info

Submission Time
Task B - Garbage Collector
User chenmark
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2063 Byte
Status
Exec Time 88 ms
Memory 5136 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 400 / 400 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, stest_01.txt, stest_02.txt, stest_03.txt, stest_04.txt, stest_05.txt, stest_06.txt, stest_07.txt, stest_08.txt, stest_09.txt, stest_10.txt, stest_11.txt, stest_12.txt
All 300 / 300 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, stest_01.txt, stest_02.txt, stest_03.txt, stest_04.txt, stest_05.txt, stest_06.txt, stest_07.txt, stest_08.txt, stest_09.txt, stest_10.txt, stest_11.txt, stest_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB
stest_01.txt 2 ms 256 KB
stest_02.txt 2 ms 256 KB
stest_03.txt 1 ms 256 KB
stest_04.txt 1 ms 256 KB
stest_05.txt 1 ms 256 KB
stest_06.txt 1 ms 256 KB
stest_07.txt 2 ms 256 KB
stest_08.txt 2 ms 256 KB
stest_09.txt 1 ms 256 KB
stest_10.txt 2 ms 256 KB
stest_11.txt 2 ms 256 KB
stest_12.txt 1 ms 256 KB
test_13.txt 88 ms 5128 KB
test_14.txt 87 ms 5128 KB
test_15.txt 16 ms 1228 KB
test_16.txt 61 ms 5120 KB
test_17.txt 83 ms 5136 KB
test_18.txt 9 ms 1024 KB
test_19.txt 63 ms 5120 KB
test_20.txt 85 ms 5136 KB
test_21.txt 84 ms 5120 KB
test_22.txt 85 ms 5136 KB
test_23.txt 61 ms 5120 KB
test_24.txt 83 ms 5128 KB
test_25.txt 30 ms 2784 KB
test_26.txt 63 ms 5120 KB
test_27.txt 84 ms 5136 KB
test_28.txt 51 ms 4096 KB