oj.uz

Submission #537135

# Submission time Handle Problem Language Result Execution time Memory
537135 2022-03-14T15:27:53 Z maomao90 Popeala (CEOI16_popeala) C++17
100 / 100
 592 ms 5472 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 2000000005
#define LINF 1000000000000000005ll
#define MAXT 20005
#define MAXN 55

int n, t, s;
int p[MAXT];
char g[MAXN][MAXT];
uint dp[MAXN][MAXT];
int best[MAXN], last[MAXN], ac[MAXT];

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> t >> s;
    REP (i, 1, t + 1) {
        cin >> p[i];
        p[i] += p[i - 1];
    }
    REP (i, 1, n + 1) {
        REP (j, 1, t + 1) {
            cin >> g[i][j];
        }
    }
    REP (i, 1, t + 1) {
        dp[0][i] = INF;
    }
    REP (i, 1, s + 1) {
        REP (j, 0, n + 1) {
            best[j] = 0;
            last[j] = 0;
        }
        ac[0] = n;
        dp[i][0] = INF;
        REP (j, 1, t + 1) {
            dp[i][j] = INF;
            ac[j] = n;
            auto cost = [&] (int x) {
                return dp[i - 1][x] + (p[j] - p[x]) * n;
            };
            if (cost(best[n]) > cost(j - 1)) {
                best[n] = j - 1;
            }
            REP (k, 1, n + 1) {
                if (g[k][j] == '0') {
                    REP (l, last[k] + 1, j + 1) {
                        best[ac[l]] = 0;
                    }
                    REP (l, last[k] + 1, j + 1) {
                        ac[l]--;
                        auto cost = [&] (int x) {
                            return dp[i - 1][x] + (p[j] - p[x]) * ac[l];
                        };
                        if (cost(best[ac[l]]) > cost(l - 1)) {
                            best[ac[l]] = l - 1;
                        }
                        //cerr << l << ' ' << ac[l] << '\n';
                    }
                    last[k] = j;
                }
            }
            if (j < i) continue;
            REP (k, 0, n + 1) {
                //cerr << ' ' << k << ' ' << best[k] << '\n';
                mnto(dp[i][j], dp[i - 1][best[k]] + 
                        (p[j] - p[best[k]]) * ac[best[k] + 1]);
            }
            cerr << i << ' ' << j << ": " << dp[i][j] << '\n';
        }
    }
    REP (i, 1, s + 1) {
        cout << dp[i][t] << '\n';
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 852 KB Output is correct
2 Correct 14 ms 836 KB Output is correct
3 Correct 14 ms 804 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1264 KB Output is correct
2 Correct 89 ms 1432 KB Output is correct
3 Correct 121 ms 1716 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 15 ms 852 KB Output is correct
4 Correct 14 ms 836 KB Output is correct
5 Correct 14 ms 804 KB Output is correct
6 Correct 55 ms 1264 KB Output is correct
7 Correct 89 ms 1432 KB Output is correct
8 Correct 121 ms 1716 KB Output is correct
9 Correct 183 ms 2360 KB Output is correct
10 Correct 261 ms 2884 KB Output is correct
11 Correct 539 ms 5312 KB Output is correct
12 Correct 592 ms 5472 KB Output is correct
13 Correct 578 ms 5324 KB Output is correct
14 Correct 575 ms 5372 KB Output is correct
15 Correct 586 ms 5412 KB Output is correct