oj.uz

Submission #35639

# Submission time Handle Problem Language Result Execution time Memory
35639 2017-11-26T19:33:54 Z imaxblue Popeala (CEOI16_popeala) C++14
100 / 100
 289 ms 46304 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 46304 KB Output is correct
2 Correct 3 ms 46304 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46304 KB Output is correct
2 Correct 6 ms 46304 KB Output is correct
3 Correct 9 ms 46304 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 46304 KB Output is correct
2 Correct 46 ms 46304 KB Output is correct
3 Correct 46 ms 46304 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 46304 KB Output is correct
2 Correct 3 ms 46304 KB Output is correct
3 Correct 13 ms 46304 KB Output is correct
4 Correct 6 ms 46304 KB Output is correct
5 Correct 9 ms 46304 KB Output is correct
6 Correct 36 ms 46304 KB Output is correct
7 Correct 46 ms 46304 KB Output is correct
8 Correct 46 ms 46304 KB Output is correct
9 Correct 79 ms 46304 KB Output is correct
10 Correct 116 ms 46304 KB Output is correct
11 Correct 289 ms 46304 KB Output is correct
12 Correct 279 ms 46304 KB Output is correct
13 Correct 289 ms 46304 KB Output is correct
14 Correct 253 ms 46304 KB Output is correct
15 Correct 269 ms 46304 KB Output is correct