oj.uz

Submission #115242

# Submission time Handle Problem Language Result Execution time Memory
115242 2019-06-06T08:35:57 Z minhtung0404 Popeala (CEOI16_popeala) C++17
100 / 100
 1313 ms 7160 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4736 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4736 KB Output is correct
2 Correct 33 ms 4736 KB Output is correct
3 Correct 34 ms 4736 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 4984 KB Output is correct
2 Correct 195 ms 5120 KB Output is correct
3 Correct 251 ms 5340 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4736 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct
3 Correct 35 ms 4736 KB Output is correct
4 Correct 33 ms 4736 KB Output is correct
5 Correct 34 ms 4736 KB Output is correct
6 Correct 135 ms 4984 KB Output is correct
7 Correct 195 ms 5120 KB Output is correct
8 Correct 251 ms 5340 KB Output is correct
9 Correct 382 ms 5516 KB Output is correct
10 Correct 548 ms 5752 KB Output is correct
11 Correct 1198 ms 7000 KB Output is correct
12 Correct 1184 ms 7092 KB Output is correct
13 Correct 1269 ms 7160 KB Output is correct
14 Correct 1313 ms 7072 KB Output is correct
15 Correct 1303 ms 7160 KB Output is correct