Submission #90807

#	Time	Username	Problem	Language	Result	Execution time	Memory
90807		EntityIT	Popeala (CEOI16_popeala)	C++14	100 / 100	1877 ms	21140 KiB

popeala

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74