답안 #51826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51826 2018-06-21T09:59:33 Z evpipis 조교 (CEOI16_popeala) C++14
100 / 100
1808 ms 26632 KB
#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

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);
             ~~~~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 1564 KB Output is correct
2 Correct 31 ms 1564 KB Output is correct
3 Correct 32 ms 1768 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 3312 KB Output is correct
2 Correct 201 ms 4128 KB Output is correct
3 Correct 301 ms 5236 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 44 ms 1564 KB Output is correct
4 Correct 31 ms 1564 KB Output is correct
5 Correct 32 ms 1768 KB Output is correct
6 Correct 163 ms 3312 KB Output is correct
7 Correct 201 ms 4128 KB Output is correct
8 Correct 301 ms 5236 KB Output is correct
9 Correct 468 ms 7600 KB Output is correct
10 Correct 588 ms 10348 KB Output is correct
11 Correct 1326 ms 21820 KB Output is correct
12 Correct 1521 ms 23356 KB Output is correct
13 Correct 1527 ms 24324 KB Output is correct
14 Correct 1808 ms 25360 KB Output is correct
15 Correct 1597 ms 26632 KB Output is correct