oj.uz

Submission #116653

# Submission time Handle Problem Language Result Execution time Memory
116653 2019-06-13T10:49:54 Z JohnTitor Popeala (CEOI16_popeala) C++11
17 / 100
 2000 ms 1920 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Popeala"
class line{
public:
    ll a, b;
    line(): a(0), b(1e18){}
    line(ll a, ll b): a(a), b(b){}
    ll at(ll x){
        return a*x+b;
    }
};
int n, t, h;
ll s[20001];
ll x[20001];
string p[51];
int nf[51][20001];
class linear_segment_tree{
public:
    using pointer=linear_segment_tree*;
    int l, r, m;
    line L;
    pointer left, right;
    linear_segment_tree(int idl, int idr): L(){
        l=x[idl];
        r=x[idr];
        int idm=(idl+idr)/2;
        m=x[idm];
        if(idl!=idr){
            left=new linear_segment_tree(idl, idm);
            right=new linear_segment_tree(idm+1, idr);
        }
        else left=right=nullptr;
    }
    void clear(){
        if(left!=nullptr){
            left->clear();
            right->clear();
        }
        L=line();
    }
    void update(int u, int v, line A){
        if(l>v||r<u) return;
        if(u<=l&&v>=r){
            bool gl=A.at(l)<=L.at(l);
            bool gr=A.at(r)<=L.at(r);
            if(gl&&gr) L=A;
            else if(gl||gr){
                left->update(u, v, A);
                right->update(u, v, A);
            }
        }
        else{
            left->update(u, v, A);
            right->update(u, v, A);
        }
    }
    ll get(int u){
        if(l==r) return L.at(u);
        else{
            if(m>=u) return min(left->get(u), L.at(u));
            return min(right->get(u), L.at(u));
        }
    }
};
linear_segment_tree::pointer tree;
ll f[20001];
ll g[20001];
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(t);
    read(h);
    FOR(i, 1, t) read(s[i]);
    FOR(i, 1, t) x[i]=x[i-1]+s[i];
    tree=new linear_segment_tree(1, t);
    FOR(i, 1, n){
        cin>>p[i];
        p[i]='0'+p[i];
        nf[i][t]=t+1;
        DFOR(j, t-1, 0) if(p[i][j+1]=='0') nf[i][j]=j+1;
        else nf[i][j]=nf[i][j+1];
    }
    FOR(i, 1, t) f[i]=1e18;
    g[0]=1e18;
    FOR(used, 1, h){
        tree->clear();
        FFOR(i, 0, t) if(f[i]<1e18){
            int cnt=n;
            vector <int> alive;
            FOR(j, 1, n) alive.pb(j);
            int now=i;
            bool first=1;
            while(!alive.empty()){
                tree->update(x[now+first], x[t], line(alive.size(), f[i]-x[i]*alive.size()));
                int nxdeath=t+1;
                for(int x: alive) nxdeath=min(nxdeath, nf[x][now]);
                vector <int> nalive;
                for(int x: alive) if(nf[x][now]>nxdeath) nalive.pb(x);
                alive=nalive;
                now=nxdeath;
                first=0;
            }
            if(now<=t) tree->update(x[now], x[t], line(0, f[i]));
        }
        FOR(i, 1, t) f[i]=tree->get(x[i]);
        f[0]=1e18;
        writeln(f[t]);
    }
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:108:17: warning: unused variable 'cnt' [-Wunused-variable]
             int cnt=n;
                 ^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 820 KB Output is correct
2 Correct 413 ms 808 KB Output is correct
3 Correct 423 ms 908 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1554 ms 1580 KB Output is correct
2 Execution timed out 2051 ms 1920 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 408 ms 820 KB Output is correct
4 Correct 413 ms 808 KB Output is correct
5 Correct 423 ms 908 KB Output is correct
6 Correct 1554 ms 1580 KB Output is correct
7 Execution timed out 2051 ms 1920 KB Time limit exceeded
8 Halted 0 ms 0 KB -