oj.uz

Submission #537115

# Submission time Handle Problem Language Result Execution time Memory
537115 2022-03-14T14:40:13 Z maomao90 Popeala (CEOI16_popeala) C++17
100 / 100
 586 ms 5540 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 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 0 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 17 ms 816 KB Output is correct
2 Correct 14 ms 884 KB Output is correct
3 Correct 14 ms 876 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1244 KB Output is correct
2 Correct 80 ms 1492 KB Output is correct
3 Correct 117 ms 1720 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 17 ms 816 KB Output is correct
4 Correct 14 ms 884 KB Output is correct
5 Correct 14 ms 876 KB Output is correct
6 Correct 58 ms 1244 KB Output is correct
7 Correct 80 ms 1492 KB Output is correct
8 Correct 117 ms 1720 KB Output is correct
9 Correct 186 ms 2276 KB Output is correct
10 Correct 254 ms 2976 KB Output is correct
11 Correct 556 ms 5360 KB Output is correct
12 Correct 578 ms 5380 KB Output is correct
13 Correct 562 ms 5540 KB Output is correct
14 Correct 560 ms 5452 KB Output is correct
15 Correct 586 ms 5316 KB Output is correct