oj.uz

답안 #983125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983125 2024-05-15T08:30:16 Z _callmelucian 수열 (APIO14_sequence) C++14
100 / 100
 722 ms 84428 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

ll divi (ll a, ll b) {
    return a / b + ((a ^ b) < 0 && a % b);
}

struct line {
    ll slope, c; int id;

    line (ll u = 0, ll v = 0, int z = 0) : slope(u), c(v), id(z) {}

    ll calc (ll x) { return slope * x + c; }

    friend ll isect (line a, line b) {
        return divi(a.c - b.c, b.slope - a.slope);
    }
};

struct CHT {
    deque<line> hull;

    void add (line cur) {
        while (hull.size() >= 2 && isect(hull[hull.size() - 2], hull.back()) > isect(hull.back(), cur))
            hull.pop_back();
        hull.push_back(cur);
    }

    pair<ll,int> query (ll x) {
        while (hull.size() >= 2 && x > isect(hull[0], hull[1]))
            hull.pop_front();
        return make_pair(hull.front().calc(x), hull.front().id);
    }
};

const int mn = 1e5 + 5;
ll dp[2][mn], pre[mn];
int trace[202][mn];

void track (int k, int i, vector<int> &cuts, vector<pl> &vec) {
    if (k == 0) {
        cuts.push_back(vec[i].second);
        return;
    }
    track(k - 1, trace[k][i], cuts, vec);
    cuts.push_back(vec[i].second);
}

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

    int n, split, cnt = 0; cin >> n >> split;
    vector<pl> vec(1);
    queue<int> zero;

    for (int i = 1; i <= n; i++) {
        int a; cin >> a;
        if (a) {
            vec.push_back(make_pair(a, i));
            cnt++;
        }
        else zero.push(i);
    }

    for (int i = 1; i <= cnt; i++)
        pre[i] = pre[i - 1] + vec[i].first;

    int use = min(split, cnt - 1);
    for (int k = 1; k <= use; k++) {
        int t = k & 1; CHT helper;
        for (int i = 1; i <= k; i++)
            helper.add(line(pre[i], dp[t ^ 1][i] - pre[i] * pre[i], i));
        for (int i = k + 1; i <= cnt; i++) {
            tie(dp[t][i], trace[k][i]) = helper.query(pre[i]);
            helper.add(line(pre[i], dp[t ^ 1][i] - pre[i] * pre[i], i));
        }
    }

    cout << dp[use & 1][cnt] << "\n";

    vector<int> cuts;
    track(min(split, cnt - 1), cnt, cuts, vec);
    cuts.pop_back();

    while (cuts.size() < split) {
        cuts.push_back(zero.front());
        zero.pop();
    }
    for (int u : cuts) cout << u << " ";

    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:96:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |     while (cuts.size() < split) {
      |            ~~~~~~~~~~~~^~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 2396 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 348 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 2396 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 1 ms 4440 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 1 ms 2396 KB contestant found the optimal answer: 1 == 1
7 Correct 1 ms 2396 KB contestant found the optimal answer: 1 == 1
8 Correct 1 ms 2396 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 2392 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 1 ms 2396 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 1 ms 2396 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 1 ms 2396 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 1 ms 2396 KB contestant found the optimal answer: 140072 == 140072
14 Correct 1 ms 2396 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 1 ms 2396 KB contestant found the optimal answer: 805 == 805
16 Correct 1 ms 2396 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 1 ms 2396 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 2396 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 6 ms 20828 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 2396 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 1 ms 4444 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 1 ms 4444 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 10588 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 1 ms 6492 KB contestant found the optimal answer: 687136 == 687136
9 Correct 1 ms 4444 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 1 ms 6492 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 2520 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 22 ms 78416 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 2396 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 7 ms 55900 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 8 ms 64092 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 10 ms 78428 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 3 ms 18780 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 2 ms 12636 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 3 ms 22876 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 1 ms 2396 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 15 ms 78428 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 1 ms 2396 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 15 ms 78292 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 12 ms 68188 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 16 ms 78296 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 15 ms 78428 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 3 ms 16728 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 7 ms 33372 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2908 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 2 ms 2908 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Correct 77 ms 78876 KB contestant found the optimal answer: 4973126687469639 == 4973126687469639
4 Correct 4 ms 3028 KB contestant found the optimal answer: 3748491676694116 == 3748491676694116
5 Correct 45 ms 47956 KB contestant found the optimal answer: 1085432199 == 1085432199
6 Correct 46 ms 56284 KB contestant found the optimal answer: 514790755404 == 514790755404
7 Correct 68 ms 60376 KB contestant found the optimal answer: 1256105310476641 == 1256105310476641
8 Correct 48 ms 50136 KB contestant found the optimal answer: 3099592898816 == 3099592898816
9 Correct 53 ms 56284 KB contestant found the optimal answer: 1241131419367412 == 1241131419367412
10 Correct 68 ms 72660 KB contestant found the optimal answer: 1243084101967798 == 1243084101967798

Subtask #6
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 6616 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 15 ms 6876 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Correct 722 ms 84428 KB contestant found the optimal answer: 497313449256899208 == 497313449256899208
4 Correct 19 ms 7892 KB contestant found the optimal answer: 374850090734572421 == 374850090734572421
5 Correct 599 ms 83320 KB contestant found the optimal answer: 36183271951 == 36183271951
6 Correct 434 ms 60064 KB contestant found the optimal answer: 51629847150471 == 51629847150471
7 Correct 648 ms 65348 KB contestant found the optimal answer: 124074747024496432 == 124074747024496432
8 Correct 476 ms 55152 KB contestant found the optimal answer: 309959349080800 == 309959349080800
9 Correct 492 ms 61124 KB contestant found the optimal answer: 124113525649823701 == 124113525649823701
10 Correct 640 ms 77192 KB contestant found the optimal answer: 124309619349406845 == 124309619349406845