oj.uz

Submission #1023930

# Submission time Handle Problem Language Result Execution time Memory
1023930 2024-07-15T09:40:51 Z ttamx Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 8676 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int T=20005;
const int N=55;
const int S=55;
const int K=1<<16;
const ll INF=LLONG_MAX/2;

int m,n,s;
ll p[T],qs[T];
string a[N];
ll dp[T][S];
int ptr[N];

struct Segtree{
    ll t[K],lz[K];
    void apply(int i,ll v){
        t[i]+=v,lz[i]+=v;
    }
    void push(int i){
        apply(i*2,lz[i]);
        apply(i*2+1,lz[i]);
        lz[i]=0;
    }
    void pull(int i){
        t[i]=min(t[i*2],t[i*2+1]);
    }
    void build(int l,int r,int i){
        t[i]=INF;
        if(l==r)return;
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
    }
    void build(){
        build(0,m,1);
    }
    void modify(int l,int r,int i,int x,ll v){
        if(x<l||r<x)return;
        if(l==r)return void(t[i]=v);
        int m=(l+r)/2;
        push(i);
        modify(l,m,i*2,x,v);
        modify(m+1,r,i*2+1,x,v);
        pull(i);
    }
    void modify(int x,ll v){
        modify(0,m,1,x,v);
    }
    void update(int l,int r,int i,int x,int y,ll v){
        if(y<l||r<x)return;
        if(l==r)return apply(i,v);
        int m=(l+r)/2;
        push(i);
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        pull(i);
    }
    void update(int x,int y,ll v){
        update(0,m,1,x,y,v);
    }
    ll query(int l,int r,int i,int x,int y){
        if(y<l||r<x)return INF;
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        push(i);
        return min(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
    }
    ll query(int x,int y){
        return query(0,m,1,x,y);
    }
}seg[S];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++)cin >> p[i];
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<=m;i++)qs[i]=qs[i-1]+p[i];
    for(int i=0;i<=s;i++)seg[i].build();
    seg[0].modify(0,0);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<=s;k++){
                seg[k].update(ptr[j],i-1,p[i]);
            }
        }
        for(int j=1;j<=n;j++)if(a[j][i-1]=='0'){
            for(;ptr[j]<i;ptr[j]++){
                for(int k=0;k<=s;k++){
                    seg[k].update(ptr[j],ptr[j],-(qs[i]-qs[ptr[j]]));
                }
            }
        }
        for(int j=1;j<=s;j++)dp[i][j]=seg[j-1].query(0,i-1);
        for(int j=1;j<=s;j++)seg[j].modify(i,dp[i][j]);
    }
    for(int i=1;i<=s;i++)cout << dp[m][i] << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 600 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 1944 KB Output is correct
2 Correct 496 ms 1912 KB Output is correct
3 Correct 441 ms 1876 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 8676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 400 ms 1944 KB Output is correct
4 Correct 496 ms 1912 KB Output is correct
5 Correct 441 ms 1876 KB Output is correct
6 Execution timed out 2060 ms 8676 KB Time limit exceeded
7 Halted 0 ms 0 KB -