Submission #536891

#	Time	Username	Problem	Language	Result	Execution time	Memory
536891		maomao90	Popeala (CEOI16_popeala)	C++17	17 / 100	2077 ms	1996 KiB

popeala

// 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;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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[MAXT][MAXN];
int dp[MAXN][MAXT];
bool blk[MAXN];
int lft[MAXN];

#define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
uint vmn[MAXT * 4], lz[MAXT * 4];
void propo(int u, int lo, int hi) {
    if (lo == hi || lz[u] == 0) return;
    MLR;
    lz[lc] += lz[u];
    lz[rc] += lz[u];
    vmn[lc] += lz[u];
    vmn[rc] += lz[u];
    lz[u] = 0;
}
void incre(int s, int e, uint x, int u = 1, int lo = 0, int hi = t - 1) {
    if (lo >= s && hi <= e) {
        lz[u] += x;
        vmn[u] += x;
        return;
    }
    propo(u, lo, hi);
    MLR;
    if (s <= mid) {
        incre(s, e, x, lc, lo, mid);
    }
    if (e > mid) {
        incre(s, e, x, rc, mid + 1, hi);
    }
   vmn[u] = min(vmn[lc], vmn[rc]);
}
uint qmn(int s, int e, int u = 1, int lo = 0, int hi = t - 1) {
    if (lo >= s && hi <= e) {
        return vmn[u];
    }
    propo(u, lo, hi);
    MLR;
    uint res = INF;
    if (s <= mid) {
        mnto(res, qmn(s, e, lc, lo, mid));
    }
    if (e > mid) {
        mnto(res, qmn(s, e, rc, mid + 1, hi));
    }
    return res;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> t >> s;
    REP (i, 0, t) {
        cin >> p[i];
    }
    REP (i, 0, n) {
        REP (j, 0, t) {
            cin >> g[j][i];
        }
    }
    REP (i, 1, t) {
        incre(i, i, INF);
    }
    REP (i, 1, s + 1) {
        memset(lft, -1, sizeof lft);
        REP (j, 0, t) {
            dp[i][j] = INF;
            REP (k, 0, n) {
                if (g[j][k] == '1') {
                    if (lft[k] == -1) {
                        lft[k] = j;
                    }
                    incre(lft[k], j, p[j]);
                } else if (lft[k] != -1) {
                    int sm = 0;
                    RREP (l, j - 1, lft[k]) {
                        sm += p[l];
                        incre(l, l, -sm);
                    }
                    lft[k] = -1;
                }
            }
            if (j + 1 >= i) {
                dp[i][j] = qmn(i - 1, j);
            }
            cerr << i << ' ' << j << ": " << dp[i][j] << '\n';
        }
        memset(vmn, 0, sizeof vmn);
        memset(lz, 0, sizeof lz);
        REP (j, i - 1, t - 1) {
            incre(j + 1, j + 1, dp[i][j]);
        }
    }
    REP (i, 1, s + 1) {
        cout << dp[i][t - 1] << '\n';
    }
    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'void propo(int, int, int)':
popeala.cpp:49:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
popeala.cpp:53:5: note: in expansion of macro 'MLR'
   53 |     MLR;
      |     ^~~
popeala.cpp:49:17: warning: unused variable 'mid' [-Wunused-variable]
   49 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
popeala.cpp:53:5: note: in expansion of macro 'MLR'
   53 |     MLR;
      |     ^~~
popeala.cpp: In function 'void incre(int, int, uint, int, int, int)':
popeala.cpp:49:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
popeala.cpp:67:5: note: in expansion of macro 'MLR'
   67 |     MLR;
      |     ^~~
popeala.cpp: In function 'uint qmn(int, int, int, int, int)':
popeala.cpp:49:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 | #define MLR int mid = lo + hi >> 1; int lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
popeala.cpp:81:5: note: in expansion of macro 'MLR'
   81 |     MLR;
      |     ^~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74