oj.uz

Submission #90806

# Submission time Handle Problem Language Result Execution time Memory
90806 2018-12-24T13:36:47 Z EntityIT Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 37968 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#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:51:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (iChange + 1 < change.size() ) {
                    ~~~~~~~~~~~~^~~~~~~~~~~~~~~
popeala.cpp:52: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 8 ms 9464 KB Output is correct
2 Correct 8 ms 10132 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10760 KB Output is correct
2 Correct 36 ms 10820 KB Output is correct
3 Correct 37 ms 11024 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 13396 KB Output is correct
2 Correct 192 ms 14712 KB Output is correct
3 Correct 311 ms 16280 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9464 KB Output is correct
2 Correct 8 ms 10132 KB Output is correct
3 Correct 36 ms 10760 KB Output is correct
4 Correct 36 ms 10820 KB Output is correct
5 Correct 37 ms 11024 KB Output is correct
6 Correct 139 ms 13396 KB Output is correct
7 Correct 192 ms 14712 KB Output is correct
8 Correct 311 ms 16280 KB Output is correct
9 Correct 534 ms 20080 KB Output is correct
10 Correct 825 ms 22988 KB Output is correct
11 Correct 1892 ms 37280 KB Output is correct
12 Execution timed out 2017 ms 37968 KB Time limit exceeded
13 Halted 0 ms 0 KB -