Submission #35639

#	Time	Username	Problem	Language	Result	Execution time	Memory
35639		imaxblue	Popeala (CEOI16_popeala)	C++14	100 / 100	289 ms	46304 KiB

popeala

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k= x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, m, s, ans, i[55],
    p[20006], psa[20005], cnt[20005], best[55][55], start[55][200005];
bool fail[55][20005];
char ch;
int main(){
    flood(best); flood(start);
    scanf("%i%i%i", &m, &n, &s);
    fox1(l, n){
        scanf("%i", &p[l]);
        psa[l]=p[l]+psa[l-1];
        cnt[l]=m;
    }
    fox(l, 51) i[l]=1;
    fox(l, m){
        fox1(l2, n){
            scanf(" %c", &ch);
            fail[l][l2]=(ch=='0');
        }
    }
    best[0][m]=0; start[0][1]=0;
    fox1(l, n){
        if (l!=1){
            fox1r(l2, s-1){
                fox(l3, m+1){
                    start[l2][l]=min(start[l2][l], best[l2-1][l3]);
                }
                best[l2][m]=min(best[l2][m], start[l2][l]);
            }
        }
        fox(l3, m){
            if (fail[l3][l]){
                //cout << "*";
                for (; i[l3]<=l; i[l3]++){
                    cnt[i[l3]]--;
                    //cout << i[l3] << ' ';
                    fox(l2, s)
                        best[l2][cnt[i[l3]]]=
    min(best[l2][cnt[i[l3]]], start[l2][i[l3]]+cnt[i[l3]]*(psa[l-1]-psa[i[l3]-1]));
                }
            }
        }
        fox(l2, s){
            fox(l3, m+1){
                best[l2][l3]+=l3*p[l];
            }
        }
        /*fox(l2, s){
            fox(l3, m+1){
                printf("%i ", best[l2][l3]);
            }
            printf("\n");
        } printf("\n");*/
    }
    fox(l, s){
        ans=(1 << 30);
        fox(l2, m+1){
            ans=min(ans, best[l][l2]);
        }
        printf("%i\n", ans);
    }
    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:33:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i", &m, &n, &s);
                                ^
popeala.cpp:35:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i", &p[l]);
                           ^
popeala.cpp:42:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &ch);
                              ^

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