oj.uz

Submission #90807

# Submission time Handle Problem Language Result Execution time Memory
90807 2018-12-24T13:39:18 Z EntityIT Popeala (CEOI16_popeala) C++14
100 / 100
 1877 ms 21140 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = 55, T = 2e4 + 5, inf = (int)2e9 + 123;
int n, t, s, points[T], lst[N][T], sum[N][T], dp[N][T];
vector<int> vec[T];
char res[N][T];

int32_t main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("popeala.in", "r", stdin);
//    freopen("popeala.out", "w", stdout);

    cin >> n >> t >> s;
    for (int j = 1; j <= t; ++j) {
        cin >> points[j];
        for (int i = 0; i <= n; ++i) sum[i][j] = sum[i][j - 1] + points[j] * i;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= t; ++j) cin >> res[i][j];
    }
    for (int i = 1; i <= n; ++i) {
        int last = 0;
        for (int j = 1; j <= t; ++j) { if (res[i][j] == '0') last = j; lst[i][j] = last; }
    }

    for (int j = 1; j <= t; ++j) {
        vec[j].pb(0); vec[j].pb(j);
        for (int i = 1; i <= n; ++i) vec[j].pb(lst[i][j]);
        sort(vec[j].begin(), vec[j].end() ); reverse(vec[j].begin(), vec[j].end() );
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < T; ++j) dp[i][j] = inf;
    }
    dp[0][0] = 0;

    for (int i = 1; i <= s; ++i) {
//        cout << "i = " << i << "*****\n";
        deque<int> deq[N];
        for (int j = 1; j <= t; ++j) {
//            cout << "j = " << j << '\n';
            vector<int> change = vec[j];

            int iChange = 0;
            while (iChange + 1 < change.size() ) {
                do { iChange ++; } while (iChange + 1 < change.size() && change[iChange] == change[iChange - 1]);
                int l = change[iChange], r = change[iChange - 1] - 1;
                if (r != -1) {
//                    cout << "l = " << l << "  r = " << r << ' ' << n - iChange + 1 << '\n';
                    while (deq[n - iChange + 1].size() && deq[n - iChange + 1].front() < l) deq[n - iChange + 1].pop_back();
                    if (!deq[n - iChange + 1].size() ) deq[n - iChange + 1].push_back(l);
                    while (deq[n - iChange + 1].size() && deq[n - iChange + 1].back() < r) {
                        int nxt = deq[n - iChange + 1].back() + 1;
                        while (deq[n - iChange + 1].size() &&
                               dp[i - 1][ deq[n - iChange + 1].back() ] - sum[n - iChange + 1][ deq[n - iChange + 1].back() ]
                                > dp[i - 1][nxt] - sum[n - iChange + 1][nxt]) deq[n - iChange + 1].pop_back();
                        deq[n - iChange + 1].push_back(nxt);
                    }
                }
                int tmp = (deq[n - iChange + 1].size() && dp[i - 1][ deq[n - iChange + 1].front() ] != inf ? dp[i - 1][ deq[n - iChange + 1].front() ]
                            - sum[n - iChange + 1][ deq[n - iChange + 1].front() ] : inf);

                if (tmp != inf) dp[i][j] = min(dp[i][j], tmp + sum[n - iChange + 1][j]);
            }
//            cout << dp[i][j] << "+++++\n";
        }
    }

    for (int i = 1; i <= s; ++i) cout << dp[i][t] << '\n';

    return 0;
}

Compilation message

popeala.cpp: In function 'int32_t main()':
popeala.cpp:50:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (iChange + 1 < change.size() ) {
                    ~~~~~~~~~~~~^~~~~~~~~~~~~~~
popeala.cpp:51:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 do { iChange ++; } while (iChange + 1 < change.size() && change[iChange] == change[iChange - 1]);
                                           ~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 6 ms 5620 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6168 KB Output is correct
2 Correct 34 ms 6244 KB Output is correct
3 Correct 34 ms 6320 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 7600 KB Output is correct
2 Correct 182 ms 8120 KB Output is correct
3 Correct 275 ms 8800 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 6 ms 5620 KB Output is correct
3 Correct 35 ms 6168 KB Output is correct
4 Correct 34 ms 6244 KB Output is correct
5 Correct 34 ms 6320 KB Output is correct
6 Correct 129 ms 7600 KB Output is correct
7 Correct 182 ms 8120 KB Output is correct
8 Correct 275 ms 8800 KB Output is correct
9 Correct 484 ms 10552 KB Output is correct
10 Correct 636 ms 12088 KB Output is correct
11 Correct 1741 ms 19444 KB Output is correct
12 Correct 1877 ms 19640 KB Output is correct
13 Correct 1657 ms 19820 KB Output is correct
14 Correct 1712 ms 20716 KB Output is correct
15 Correct 1588 ms 21140 KB Output is correct