Submission #51826

#	Time	Username	Problem	Language	Result	Execution time	Memory
51826		evpipis	Popeala (CEOI16_popeala)	C++14	100 / 100	1808 ms	26632 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;

const int len = 2e4+5;
const ll inf = 1e15;
int po[len], can[55][len], n, s, t;
ll dp[55][len];
ii inter[55][len];
deque<pair<ll, int> > deq;

int val(int l, int r){
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (can[i][r]-can[i][l-1] == r-l+1)
            ans += po[r]-po[l-1];

    return ans;
}

int cnt(int l, int r){
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (can[i][r]-can[i][l-1] == r-l+1)
            ans++;

    return ans;
}

ll fin_mn(int rem, int x, int l, int r){
    ll ans = inf;
    for (int i = l; i <= r; i++)
        ans = min(ans, x*po[i] + dp[rem][i+1]);

    return ans;
}

/*int bs(int i, int x){
    int l = i, r = t, ans = -1;
    while (l <= r){
        int mid = (l+r)/2;
        if (val(i, mid) <= x*(po[mid]-po[i-1])){
            ans = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }

    return ans;
}

ll solve(int i, int rem){
    if (i == t+1 && rem == 0) return 0;
    if (i == t+1 && rem != 0) return inf;
    if (rem == 1) return val(i, t);
    if (dp[i][rem] != -1) return dp[i][rem];

    ll ans = inf;
    //for (int j = i; j <= t; j++)
      //  ans = min(ans, val(i, j) + solve(j+1, rem-1));

    for (int x = 0; x <= n; x++){
        int j = bs(i, x);
        //printf("i = %d, x = %d, j = %d\n", i, x, j);
        if (j != -1 && val(i, j) == x*(po[j]-po[i-1]))
            ans = min(ans, solve(j+1, rem-1) + val(i, j));
    }

    //printf("i = %d, rem = %d, ans = %lld\n", i, rem, ans);
    return dp[i][rem] = ans;
}*/

int main(){
    scanf("%d %d %d", &n, &t, &s);
    for (int i = 1; i <= t; i++)
        scanf("%d", &po[i]);
    for (int i = 1; i <= n; i++){
        scanf(" ");
        for (int j = 1; j <= t; j++){
            char temp;
            scanf("%c", &temp);

            if (temp == '1')
                can[i][j] = 1;
        }
    }

    /*for (int i = 1; i <= n; i++){
        for (int j = 1; j <= t; j++)
            printf("%d", can[i][j]);
        printf("\n");
    }*/

    for (int j = 1; j <= t; j++)
        po[j] += po[j-1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= t; j++)
            can[i][j] += can[i][j-1];

    //for (int i = 1; i <= t; i++)
      //  for (int j = 0; j <= s; j++)
        //    dp[i][j] = -1;

    //for (int i = 1; i <= t; i++)
      //  for (int j = i; j <= t; j++)
        //    printf("(%d, %d) = %d\n", i, j, val(i, j));


    for (int x = 0; x <= n; x++){
        for (int i = 1, l = 1, r = 1; i <= t; i++){
            l = max(l, i), r = max(r, i);

            while (l <= t && cnt(i, l) > x) l++;
            while (r <= t && cnt(i, r) >= x) r++;

            //printf("x = %d, i = %d, l = %d, r = %d\n", x, i, l, r-1);
            inter[x][i] = mp(l, r);
        }
    }

    for (int rem = 1; rem <= s; rem++)
        for (int i = 1; i <= t+1; i++)
            dp[rem][i] = inf;

    for (int i = 1; i <= t; i++)
        dp[1][i] = val(i, t);

    //for (int i = 1; i <= t; i++)
      //  printf("rem = 1, i = %d, ans = %lld\n", i, dp[1][i]);

    for (int rem = 2; rem <= s; rem++){
        for (int x = 0; x <= n; x++){
            deq.clear();
            int cur = 1;
            for (int i = 1; i <= t; i++){
                //printf("ans before is: %lld\n", dp[rem][i]);
                int l = inter[x][i].fi, r = inter[x][i].se;

                cur = max(cur, l);
                while (!deq.empty() && deq.front().se < l)
                    deq.pop_front();
                while (cur < r){
                    ll val = dp[rem-1][cur+1] + x*po[cur];
                    while (!deq.empty() && val <= deq.back().fi)
                        deq.pop_back();
                    deq.push_back(mp(val, cur++));
                }

                if (!deq.empty())
                    dp[rem][i] = min(dp[rem][i], deq.front().fi - x*po[i-1]);

                //if (l >= i && fin_mn(rem-1, x, l, r-1) != inf)
                  //  dp[rem][i] = min(dp[rem][i], fin_mn(rem-1, x, l, r-1) - x*po[i-1]);

                //printf("rem = %d, x = %d, i = %d, l = %d, r = %d, ans = %lld\n", rem, x, i, l, r-1, dp[rem][i]);
            }
        }
    }

    for (int rem = 1; rem <= s; rem++)
        printf("%lld\n", dp[rem][1]);
    return 0;
}
/*
2 5 5
2 1 3 5 6
10010
11011
*/

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &t, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &po[i]);
         ~~~~~^~~~~~~~~~~~~~
popeala.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" ");
         ~~~~~^~~~~
popeala.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &temp);
             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74