Submission #115242

#	Time	Username	Problem	Language	Result	Execution time	Memory
115242		minhtung0404	Popeala (CEOI16_popeala)	C++17	100 / 100	1313 ms	7160 KiB

popeala

#include<bits/stdc++.h>
const int N = 55;
const int inf = 2e9 + 7;
using namespace std;

int n, t, s, sc[20005], dp[N][20005], cur[20005];
string a[N];
deque <int> mq[N];

void Insert(int id, int i, int j){
    while (mq[id].size() && dp[i][mq[id].back()]  >= dp[i][j]) mq[id].pop_back();
    mq[id].push_back(j);
}

void Erase(int id, int i, int j){
    if (mq[id].size() && mq[id].front() == j) mq[id].pop_front();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> t >> s;
    for (int i = 1; i <= t; i++) cin >> sc[i], sc[i] += sc[i-1];
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] = '.' + a[i];
    for (int i = 0; i < N; i++) for (int j = 0; j < 20005; j++) dp[i][j] = inf;
    dp[0][0] = 0;
    for (int sub = 1; sub <= s; sub++){
        for (int j = 0; j <= n; j++) mq[j].clear();
        Insert(n, sub-1, 0); cur[0] = n;
        for (int test = 1; test <= t; test++){
            for (int peo = 1; peo <= n; peo++){
                if (a[peo][test] == '1') continue;
                int last = test-1;
                while(last > 0 && a[peo][last] == '1') last--;
                for (int ntest = last; ntest < test; ntest++){
                    Erase(cur[ntest], sub-1, ntest);
                    dp[sub-1][ntest] += sc[ntest];
                    cur[ntest]--;
                    Insert(cur[ntest], sub-1, ntest);
                }
            }
            for (int k = 0; k <= n; k++){
                if (mq[k].size()) dp[sub][test] = min(dp[sub][test], k * sc[test] + dp[sub-1][mq[k].front()]);
            }
            dp[sub-1][test] -= n * sc[test]; cur[test] = n;
            Insert(n, sub-1, test);
        }
        cout << dp[sub][t] << "\n";
    }
}

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