oj.uz

Submission #537132

# Submission time Handle Problem Language Result Execution time Memory
537132 2022-03-14T15:26:24 Z maomao90 Popeala (CEOI16_popeala) C++17
100 / 100
 601 ms 5464 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];
unsigned int 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 16 ms 852 KB Output is correct
2 Correct 14 ms 852 KB Output is correct
3 Correct 14 ms 836 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1256 KB Output is correct
2 Correct 92 ms 1464 KB Output is correct
3 Correct 110 ms 1740 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 16 ms 852 KB Output is correct
4 Correct 14 ms 852 KB Output is correct
5 Correct 14 ms 836 KB Output is correct
6 Correct 62 ms 1256 KB Output is correct
7 Correct 92 ms 1464 KB Output is correct
8 Correct 110 ms 1740 KB Output is correct
9 Correct 172 ms 2332 KB Output is correct
10 Correct 271 ms 2876 KB Output is correct
11 Correct 540 ms 5456 KB Output is correct
12 Correct 584 ms 5464 KB Output is correct
13 Correct 600 ms 5384 KB Output is correct
14 Correct 587 ms 5436 KB Output is correct
15 Correct 601 ms 5352 KB Output is correct