oj.uz

답안 #1032828

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032828 2024-07-24T09:28:55 Z 김은성(#10965) 조교 (CEOI16_popeala) C++17
0 / 100
 50 ms 11344 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int p[20009], dp[52][20009];
int n, r[52][20009], re[52][20009];
char res[20009];
int tree[52][1<<16];
int ctree[1<<16], idx[52], lazy[1<<16];
int solved(int s, int e){
    int ans = 0, i;
    for(i=1; i<=n; i++){
        if(re[i][e] - re[i][s-1] == e-s+1)
            ans++;
    }
    return ans;
}
void settree(int idx, int i, int v, int l, int r){ //-idx * p[k] + dp[i][k] �� ����
    if(l==r)
        tree[idx][v] = -idx * p[l] + dp[i][l];
    else{
        int mid = (l+r)/2;
        settree(idx, i, 2*v,l , mid);
        settree(idx, i, 2*v+1, mid+1, r);
        tree[idx][v] = min(tree[idx][2*v], tree[idx][2*v+1]);
    }
}
int minquery(int idx, int v, int l, int r, int s, int e){
    if(e<l || r<s)
        return INF;
    if(s<=l && r<=e)
        return tree[idx][v];
    int mid = (l+r)/2;
    return min(minquery(idx, 2*v,l , mid, s, e), minquery(idx, 2*v+1, mid+1, r, s, e));
}
void update(int v, int l, int r, int s, int e){
    if(lazy[v]){
        ctree[v] += lazy[v];
        if(l!=r){
            lazy[2*v] += lazy[v];
            lazy[2*v+1] += lazy[v];
        }
        lazy[v] = 0;
    }
    if(e<l || r<s)
        return;
    if(s<=l && r<=e){
        ctree[v]++;
        if(l!=r){
            lazy[2*v]++;
            lazy[2*v+1]++;
        }
    }
    else{
        int mid = (l+r)/2;
        update(2*v,l , mid, s, e);
        update(2*v+1, mid+1, r, s, e);
        ctree[v] = max(ctree[2*v], ctree[2*v+1]);
    }
}
int bound(int v, int l, int r, int x){  //�����ڼ� >= x �� �ִ��� k
    if(lazy[v]){
        ctree[v] += lazy[v];
        if(l!=r){
            lazy[2*v] += lazy[v];
            lazy[2*v+1] += lazy[v];
        }
        lazy[v] = 0;
    }
   // printf("x=%d\n", x);
    //printf("ctree=%d lazy=%d x=%d\n", ctree[v], lazy[v], x);
    if(ctree[v] + lazy[v] < x)
        return -1;
    if(l==r)
        return l;
    int mid = (l+r)/2;
    if(ctree[2*v+1] + lazy[2*v+1] >= x)
        return bound(2*v+1, mid+1, r,  x);
    return bound(2*v, l, mid, x);
}
int main(){
    int t, s, i, j, k;
    scanf("%d %d %d", &n, &t, &s);
    for(i=1; i<=t; i++){
        scanf("%d", &p[i]);
        p[i] += p[i-1];
    }
    for(i=1; i<=n; i++){
        scanf(" %s", res+1);
        for(j=1; j<=t; j++){
            r[i][j] = res[j] - '0';
            re[i][j]= re[i][j-1] + r[i][j];
        }
    }
    dp[1][0] = INF;
    for(i=1; i<=t; i++)
        dp[1][i] = solved(1, i) * p[i];
    for(i=2; i<=s; i++){
        for(j=0; j<=n; j++){
            settree(j, i-1, 1, 1, t);
        }
        for(j=1; j<=n; j++)
            idx[j] = 1;
        memset(ctree, 0, sizeof(ctree));
        memset(lazy, 0, sizeof(lazy));
        for(j=1; j<=t; j++){
            dp[i][j] = INF;
            for(k=1; k<=n; k++){
                if(!r[k][j]){
                    update(1, 1, t, idx[k], j);
                   //printf("idx[k]=%d j=%d\n", idx[k], j);
                    idx[k]=j+1;
                }
            }
            for(k=0; k<=n; k++){
                int lo = bound(1, 1, t, n-k);
               // printf("k=%d lo=%d\n", n-k, lo);
                if(lo==-1)
                    continue;
                dp[i][j] = min(dp[i][j], p[j] * k + minquery(k, 1, 1, t, 1, min(lo-1, j-1)));
            }
            if(i>j)
                assert(dp[i][j] == INF);
            //printf("dp[%d][%d]=%d\n", i, j, dp[i][j]);
        }
    }
    for(i=1;i <=s; i++)
        printf("%d\n", dp[i][t]);
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d %d %d", &n, &t, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d", &p[i]);
      |         ~~~~~^~~~~~~~~~~~~
popeala.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf(" %s", res+1);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Runtime error 3 ms 2652 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 3672 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 50 ms 11344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Runtime error 3 ms 2652 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -