oj.uz

Submission #44830

# Submission time Handle Problem Language Result Execution time Memory
44830 2018-04-07T14:02:51 Z bogdan10bos Popeala (CEOI16_popeala) C++14
100 / 100
 1213 ms 15116 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;

int N, M, K;
int v[20005], sum[20005];
int dp[55][20005];
int cnt[55], pos[55];
int itv[55][2];
char s[55][20005];
deque<pii> dq[55][55];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d%d", &N, &M, &K);
    for(int i = 1; i <= M; i++) scanf("%d", &v[i]), sum[i] = sum[i - 1] + v[i];
    for(int i = 1; i <= N; i++)
        scanf("%s", s[i] + 1);

    for(int i = 1; i <= M; i++)
        for(int j = 1; j <= N; j++)
        {
            if(s[j][i] == '0')  cnt[j] = 0;
            else    cnt[j]++;
            if(cnt[j] == i) dp[1][i] += sum[i];
        }
    for(int i = 1; i <= K; i++) dp[i][0] = 2e9 + 1;

    for(int i = 1; i <= N; i++) cnt[i] = 0;
    for(int i = 1; i <= M; i++)
    {
        int ii = i;
        int cnt1 = 0;
        for(int j = 1; j <= N; j++)
        {
            if(s[j][i] == '0')  cnt[j] = 0;
            else    cnt[j]++, cnt1++;
            pos[j] = i - cnt[j] + 1;
        }

        sort(pos + 1, pos + N + 1);
        pos[0] = 1;
        pos[N + 1] = i + 1;
        int lst = 1;
        for(int j = 0; j <= cnt1; j++)
        {
            int st = pos[j];
            int dr = pos[j + 1] - 1;

            for(int i = 1; i < K; i++)
            {
                for(int k = itv[j][1] + 1; k <= dr; k++)
                {
                    int val = dp[i][k - 1] - j * sum[k - 1];
                    while(!dq[j][i].empty() && dq[j][i].back().first >= val) dq[j][i].pop_back();
                    dq[j][i].push_back({val, k});
                }
                while(!dq[j][i].empty() && dq[j][i].front().second < st)  dq[j][i].pop_front();
            }

            itv[j][0] = st;
            itv[j][1] = dr;
        }

        for(int j = 2; j <= K; j++)
        {
            dp[j][i] = 2e9 + 1;
            if(i < j)   continue;
            for(int k = 0; k <= cnt1; k++)
                if(!dq[k][j - 1].empty())
                    dp[j][i] = min(dp[j][i], dq[k][j - 1].front().first + k * sum[i]);
        }
    }

    for(int i = 1; i <= K; i++)
        printf("%d\n", dp[i][M]);

    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:41:13: warning: unused variable 'ii' [-Wunused-variable]
         int ii = i;
             ^~
popeala.cpp:53:13: warning: unused variable 'lst' [-Wunused-variable]
         int lst = 1;
             ^~~
popeala.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:25:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= M; i++) scanf("%d", &v[i]), sum[i] = sum[i - 1] + v[i];
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s[i] + 1);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2672 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2996 KB Output is correct
2 Correct 28 ms 3024 KB Output is correct
3 Correct 30 ms 3356 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 3848 KB Output is correct
2 Correct 172 ms 4344 KB Output is correct
3 Correct 242 ms 4624 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2672 KB Output is correct
3 Correct 42 ms 2996 KB Output is correct
4 Correct 28 ms 3024 KB Output is correct
5 Correct 30 ms 3356 KB Output is correct
6 Correct 115 ms 3848 KB Output is correct
7 Correct 172 ms 4344 KB Output is correct
8 Correct 242 ms 4624 KB Output is correct
9 Correct 371 ms 5788 KB Output is correct
10 Correct 510 ms 6836 KB Output is correct
11 Correct 1065 ms 10428 KB Output is correct
12 Correct 1213 ms 11652 KB Output is correct
13 Correct 1145 ms 13116 KB Output is correct
14 Correct 1126 ms 14312 KB Output is correct
15 Correct 1134 ms 15116 KB Output is correct