oj.uz

Submission #96777

# Submission time Handle Problem Language Result Execution time Memory
96777 2019-02-11T20:34:58 Z popovicirobert Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 13304 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const ll INF = 1e18;
const int MAXN = 50;
const int MAXT = 20000;

int pts[MAXT + 1], sp[MAXT + 1];
char res[MAXN + 1][MAXT + 1];
int L[MAXN + 1][MAXT + 1];

struct SegTree {

    vector <ll> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 1);
    }

    inline void clr() {
        fill(aint.begin(), aint.end(), INF);
    }

    inline void refresh(int nod) {
        aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
    }

    void update(int nod, int left, int right, int pos, ll val) {
        if(left == right) {
            aint[nod] = val;
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);
            refresh(nod);
        }
    }

    ll query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod];
        }
        else {
            int mid = (left + right) / 2;
            ll ans = INF;
            if(l <= mid) ans = min(ans, query(2 * nod, left, mid, l, r));
            if(mid < r) ans = min(ans, query(2 * nod + 1, mid + 1, right, l, r));
            return ans;
        }
    }

};

ll dp[2][MAXT + 1];
int pos[MAXN + 1];


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n, t, s;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> t >> s;
    for(i = 1; i <= t; i++) {
        cin >> pts[i];
        sp[i] = sp[i - 1] + pts[i];
    }
    for(i = 1; i <= n; i++) {
        cin >> res[i] + 1;
        res[i][0] = 0;
        for(j = 1; j <= t; j++) {
            res[i][j] -= '0';
            if(res[i][j - 1] == 0) {
                L[i][j] = j;
            }
            else {
                L[i][j] = L[i][j - 1];
            }
        }
    }
    vector < SegTree > st(n + 1);
    for(i = 0; i <= n; i++) {
        st[i].init(t);
    }
    for(i = 1; i <= t; i++) {
        dp[0][i] = INF;
    }
    for(int k = 1; k <= s; k++) {
        for(j = 0; j <= n; j++) {
            st[j].clr();
        }
        dp[k & 1][0] = INF;
        for(i = 0; i <= t; i++) {
            for(j = 0; j <= n; j++) {
                st[j].update(1, 0, t, i, dp[1 - k & 1][i] - sp[i] * j);
                //cerr << dp[1 - k & 1][i] - sp[i] * j << " ";
            }
            //cerr << "\n";
        }
        //cerr << "\n";
        for(i = 1; i <= t; i++) {
            int sz = 0;
            for(j = 1; j <= n; j++) {
                if(res[j][i] == 1) {
                    pos[++sz] = L[j][i];
                }
            }
            sort(pos + 1, pos + sz + 1, greater<int>());
            dp[k & 1][i] = INF;
            int last = i - 1;
            j = 1;
            while(j <= sz) {
                int p = j;
                while(p <= sz && pos[j] == pos[p]) {
                    p++;
                }
                if(pos[j] - 1 <= last) {
                    dp[k & 1][i] = min(dp[k & 1][i], st[sz - j + 1].query(1, 0, t, pos[j] - 1, last) + sp[i] * (sz - j + 1));
                    /*if(k == 1 && i == t) {
                        cerr << dp[k & 1][i] << " " << pos[j] - 1 << " " << last << "\n";
                    }*/
                }
                last = pos[j] - 2;
                j = p;
            }
            if(last >= 0) {
                dp[k & 1][i] = min(dp[k & 1][i], st[0].query(1, 0, t, 0, last));
            }
            //cerr << dp[k & 1][i] << " ";
        }
        //cerr << "\n";
        cout << dp[k & 1][t] << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:80:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> res[i] + 1;
                ~~~~~~~^~~
popeala.cpp:106:47: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                 st[j].update(1, 0, t, i, dp[1 - k & 1][i] - sp[i] * j);
                                             ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 636 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 1656 KB Output is correct
2 Correct 137 ms 1656 KB Output is correct
3 Correct 132 ms 1784 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 4856 KB Output is correct
2 Correct 1144 ms 6520 KB Output is correct
3 Correct 1617 ms 8440 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 636 KB Output is correct
3 Correct 123 ms 1656 KB Output is correct
4 Correct 137 ms 1656 KB Output is correct
5 Correct 132 ms 1784 KB Output is correct
6 Correct 698 ms 4856 KB Output is correct
7 Correct 1144 ms 6520 KB Output is correct
8 Correct 1617 ms 8440 KB Output is correct
9 Execution timed out 2053 ms 13304 KB Time limit exceeded
10 Halted 0 ms 0 KB -