oj.uz

답안 #135002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135002 2019-07-23T14:04:02 Z qrno 수열 (APIO14_sequence) C++14
0 / 100
 310 ms 1184 KB 
#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Piece {
    // PIECE [l r)
    int s, l, r;
   
    Piece(int S, int L, int R) :
        s(S), l(L), r(R) {}

    Piece() {}
};

struct Cut {
    Piece p;

    // Cut into [p.l, pos), [pos, p.r)
    int ls, rs, pos;

    Cut(Piece P, int LS, int RS, int POS) :
        p(P), ls(LS), rs(RS), pos(POS) {}

    Cut() {}
};

inline bool operator <(Piece a, Piece b) {
    return a.l < b.l;
}

set<Piece> pieces;
vector<int> v;
vector<int> splits;

void cut(Cut c) {
    pieces.erase(c.p);

    Piece l(c.ls, c.p.l, c.pos);
    Piece r(c.rs, c.pos, c.p.r);

    pieces.insert(l);
    pieces.insert(r);

    splits.push_back(c.pos);
}

Cut findSplit(Piece p) {
    int l = p.l;
    int r = p.r;

    int lSum = 0;
    int rSum = p.s;

    int ans = -1;

    int i;
    for (i = l; i < r; i++) {
        lSum += v[i];
        rSum -= v[i];

        if (lSum * rSum > ans)
            ans = lSum * rSum;
        if (lSum * rSum < ans) {
            lSum -= v[i];
            rSum += v[i];

            Cut c(p, lSum, rSum, i);
            return c;
        }
    }

    Cut c(p, lSum, rSum, i);
    return c;
}

int main() {

    int nAmount, sAmount;
    cin >> nAmount >> sAmount;


    int s = 0;
    for (int i = 0; i < nAmount; i++) {
        int x; cin >> x;
        v.push_back(x);

        s += x;
        cout << x << "-";
    }
    /*

    Piece p(s, 0, nAmount);
    pieces.insert(p);

    int ans = 0;

    for (int i = 0; i < sAmount; i++) {
        int maximum = -1;
        Cut best;

        for (Piece x : pieces) {
            if (x.r != x.l + 1) {
                Cut c = findSplit(x);
                int v = c.ls * c.rs;
                if (v > maximum)
                    maximum = v, best = c;
            }
        }

        ans += best.ls * best.rs;
        cut(best);
    }

    cout << ans << endl;
    for (int v : splits)
        cout << v << " ";
    cout << endl;
    */

    return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Expected integer, but "4-1-3-4-0-2-3-" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Expected integer, but "3-1-2-2-3-2-3-4-1-4-0-4-4-4-0-...-3-0-3-3-4-2-1-0-1-3-4-3-10000-" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Expected integer, but "3-2-0-2-3-2-0-3-3-4-3-0-3-1-4-...-1-4-2-10000-10000-10000-10000-" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 380 KB Expected integer, but "4-4-0-4-3-4-3-1-3-3-4-0-1-0-4-...-4-3-3-1-2-3-0-3-2-2-2-0-10000-" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 504 KB Expected integer, but "4-3-2-1-1-2-1-3-0-0-1-0-3-1-1-...-10000-10000-10000-10000-10000-" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 310 ms 1184 KB Expected integer, but "4-4-4-4-4-2-0-0-0-3-1-4-4-1-3-...-4-1-3-4-0-2-10000-10000-10000-" found
2 Halted 0 ms 0 KB -