oj.uz

Submission #740936

# Submission time Handle Problem Language Result Execution time Memory
740936 2023-05-13T10:02:09 Z 이동현(#9959) Popeala (CEOI16_popeala) C++17
100 / 100
 1121 ms 18448 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = (int)20004;
int n, t, s;
int p[NS], chk[NS], lst[54];
int dpl[NS], dp[NS], mn[54][NS];
int res[54][20004], sum[20004];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> t >> s;
    for(int i = 1; i <= t; ++i){
        cin >> p[i];
        sum[i] = p[i] + sum[i - 1];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= t; ++j){
            char c;
            cin >> c;
            res[i][j] = c - '0';
        }
    }

    for(int i = 0; i < NS; ++i){
        dpl[i] = (int)2e9 + 5;
    }
    for(int i = 1; i <= s; ++i){
        vector<int> vc(n + 1, 0);
        memset(chk, 0, sizeof(chk));
        memset(lst, 0, sizeof(lst));
        chk[0] = n + 1;
        for(int j = 0; j < 54; ++j){
            for(int k = 0; k < 20004; ++k){
                mn[j][k] = (int)2e9 + 5;
            }
        }
        if(i == 1){
            dpl[0] = 0;
            for(int j = 0; j < 54; ++j) mn[j][0] = 0;
        }
        for(int j = 1; j <= t; ++j){
            int ato = 0;
            for(int k = 1; k <= n; ++k){
                if(res[k][j] == 0){
                    ++ato;
                    --chk[lst[k]];

                    lst[k] = j;
                    ++chk[lst[k]];
                }
            }

            if(ato){
                vector<int> nvc;
                for(int k = 0; k < (int)vc.size(); ++k){
                    if(k + 1 < (int)vc.size() && vc[k] == vc[k + 1]){
                        continue;
                    }
                    for(int k2 = 0; k2 < chk[vc[k]]; ++k2){
                        nvc.push_back(vc[k]);
                    }
                }
                for(int k = 0; k < ato; ++k) nvc.push_back(j);

                for(int k = 0; k <= n; ++k){
                    mn[k][j] = -sum[j] * k + dpl[j];
                }
                for(int k = 0, k2 = 0; k < (int)nvc.size(); ++k){
                    while(k2 < (int)vc.size() && vc[k2] < (k == (int)nvc.size() - 1 ? (int)1e9 : nvc[k + 1])){
                        if(nvc[k] != vc[k2]) for(int x = 0; x <= 50; ++x){
                            mn[x][nvc[k]] = min(mn[x][nvc[k]], mn[x][vc[k2]]);
                        }
                        ++k2;
                    }
                }

                swap(vc, nvc);
            }

            assert((int)vc.size() == n + 1);

            dp[j] = (int)2e9 + 5;
            for(int k = 0; k <= n && vc[k] < j; ++k){
                if(k == n || vc[k] != vc[k + 1]){
                    dp[j] = min(dp[j], mn[k][vc[k]] + sum[j] * k);
                    //cout << i << ' ' << j << ' ' << vc[k] << ' ' << dp[j] << endl;
                }
            }

            if(!ato){
                for(int k = 0; k <= n; ++k){
                    mn[k][vc.back()] = min(mn[k][vc.back()], -sum[j] * k + dpl[j]);
                }
            }

            dpl[j] = dp[j];
        }

        cout << dp[t] << endl;
    }
    
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9044 KB Output is correct
2 Correct 18 ms 9156 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9552 KB Output is correct
2 Correct 69 ms 9544 KB Output is correct
3 Correct 71 ms 9556 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 10196 KB Output is correct
2 Correct 229 ms 10692 KB Output is correct
3 Correct 248 ms 11212 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9044 KB Output is correct
2 Correct 18 ms 9156 KB Output is correct
3 Correct 72 ms 9552 KB Output is correct
4 Correct 69 ms 9544 KB Output is correct
5 Correct 71 ms 9556 KB Output is correct
6 Correct 180 ms 10196 KB Output is correct
7 Correct 229 ms 10692 KB Output is correct
8 Correct 248 ms 11212 KB Output is correct
9 Correct 388 ms 12316 KB Output is correct
10 Correct 511 ms 13292 KB Output is correct
11 Correct 804 ms 18088 KB Output is correct
12 Correct 787 ms 18448 KB Output is correct
13 Correct 1121 ms 18380 KB Output is correct
14 Correct 1106 ms 18368 KB Output is correct
15 Correct 1097 ms 18404 KB Output is correct