제출 #1194450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194450		bleahbleah	Popeala (CEOI16_popeala)	C++20	100 / 100	1414 ms	18276 KiB

popeala

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

#define int long long
const int inf = 2e9 + 5;

struct Deque {
    deque<int> deq;
    int l, r;
    Deque() {
        l = 1, r = 0;
        deq.clear();
    }
    void push(int x) {
        while(!deq.empty() && deq.back() > x) deq.pop_back();
        deq.emplace_back(x);
    }
    void pop(int x) {
        if(!deq.empty() && deq.front() == x) deq.pop_front();
    }
    int query() { return deq.empty()? inf : deq.front(); }
};

const int nmax = 2e4 + 5;
const int pmax = 55;
int points[nmax];

int occ[nmax][pmax];
int lst[nmax][pmax];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int m, n, k;
    cin >> m >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> points[i];
        points[i] += points[i - 1];
    }
    
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            char ch;
            cin >> ch;
            occ[j][i] = ch - '0';
            if(ch == '1') lst[j][i] = lst[j - 1][i];
            else lst[j][i] = j;
        }
    }
    
    vector<int> dp(n + 1, inf), nvdp;
    dp[0] = 0;
    for(int p = 1; p <= k; p++) {
        nvdp.resize(n + 1);
        fill(begin(nvdp), end(nvdp), inf);
        vector<Deque> withsuch(m + 1);
        for(int i = 1; i <= n; i++) {
            vector<int> vs;
            for(int j = 1; j <= m; j++) vs.emplace_back(lst[i][j]);
            vs.emplace_back(i);
            vs.emplace_back(0);
            sort(all(vs), greater<int>());
            for(int cnt = 0; cnt <= m; cnt++) {
                int nl = vs[cnt + 1] + 1, nr = vs[cnt];
                auto &l = withsuch[cnt].l;
                auto &r = withsuch[cnt].r;
                while(r < nr) ++r, withsuch[cnt].push(dp[r - 1] - points[r - 1] * (m - cnt));
                while(l < nl) withsuch[cnt].pop(dp[l - 1] - points[l - 1] * (m - cnt)), ++l;
                nvdp[i] = min(nvdp[i], withsuch[cnt].query() + points[i] * (m - cnt));
                // cerr << i << ' ' << cnt << '\t' << nl << ' ' << nr << '\t' << withsuch[cnt].query() + points[i] * (m - cnt) << '\n';    
            } 
            // cerr << '\n';
        }
        cout << nvdp.back() << '\n';
        dp = move(nvdp);
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74