Submission #156407

#	Time	Username	Problem	Language	Result	Execution time	Memory
156407		Ruxandra985	Popeala (CEOI16_popeala)	C++14	0 / 100	6 ms	1016 KiB

popeala

#include <cstdio>
#include <iostream>
using namespace std;
int dp[51][20001];
long long ok[20010];
int val[20010],t,n;
pair <int,int> p[51][20010];
int aint[51][80001];
int logg[20010];
int rmq[15][20010],last[20010];
int biti1 (long long x){
    int sol = 0;
    while (x){
        sol = sol + (x&1);
        x/=2;
    }
    return sol;
}
int query_rmq (int st,int dr){
    int len = dr - st + 1;
    if ((1<<logg[len]) == len)
        return biti1(rmq[logg[len]][st]);
    return biti1(rmq[logg[len]][st] & rmq[logg[len]][dr - (1<<logg[len])+1]);
}
void precalculare(){
    int i,po,j,st,dr,mid;
    for (i=1;i<=t;i++)
        rmq[0][i] = ok[i];
    for (po=1;po<=logg[t];po++){
        for (i=1;i+(1<<po)-1<=t;i++)
            rmq[po][i] = (rmq[po-1][i] & rmq[po-1][i+(1<<(po-1))]);
    }

    for (j=1;j<=t;j++){
        p[n+1][j].first = j+1;
        last[j] = n+1;
    }

    for (i=n;i>=0;i--){
        for (j=t;j;j--){
            if (query_rmq(p[last[j]][j].first-1 , j) == i){ /// exista un interval cu i biti

                p[i][j].second = p[last[j]][j].first-1;

                st = 1;
                dr = p[i][j].second;
                while (st<=dr){
                    mid = (st + dr)/2;
                    if (query_rmq(mid , j) != i)
                        st = mid + 1;
                    else dr = mid - 1;
                }

                p[i][j].first = st;
                last[j] = i;
            }
        }
    }

    /// T log T + N * T * log T

}
void update (int b,int nod,int st,int dr,int poz,int x){
    int mid = (st + dr)/2;
    if (st == dr){
        aint[b][nod] = x;
        return;
    }
    if (poz<=mid)
        update(b,2*nod,st,mid,poz,x);
    else update (b,2*nod+1,mid+1,dr,poz,x);
    aint[b][nod] = min(aint[b][2*nod] , aint[b][2*nod+1]);
}
int query (int b,int nod,int st,int dr,int x,int y){
    int mid = (st + dr)/2;
    int sol = 2000000000;
    if (x<=st && dr<=y){
        return aint[b][nod];
    }
    if (x<=mid)
        sol = min(sol , query (b,2*nod,st,mid,x,y));
    if (mid+1<=y)
        sol = min(sol , query(b,2*nod+1,mid+1,dr,x,y));
    return sol;
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int s,i,j,sk,b;
    fscanf (fin,"%d%d%d",&n,&t,&s);
    for (i=2;i<=20010;i++)
        logg[i] = 1 + logg[i-1];
    for (i=1;i<=t;i++){
        fscanf (fin,"%d",&val[i]);
        val[i]+=val[i-1];
    }
    long long p2 = 1;
    for (i=1;i<=n;i++){
        fgetc(fin);
        for (j=1;j<=t;j++)
            ok[j]=p2 * (fgetc(fin)-'0') + ok[j];
        p2*=2;
    }

    precalculare();


    for (sk=1;sk<=s;sk++){
        for (i=1;i<=t;i++){
            if (i<sk){
                dp[sk][i] = 2000000000;
                continue;
            }
            if (sk==1)
                dp[sk][i] = (query_rmq(1,i) * val[i]);
            else {
                dp[sk][i] = 2000000000;
                for (b=0;b<=n;b++){
                    if (p[b][i].first && p[b][i].second){
                       // if (p[b][i].first == 1 && p[b][i].first != p[b][i].second)
                         //   p[b][i].first++;
                        dp[sk][i] = min(dp[sk][i],query (b,1,1,t,p[b][i].first,p[b][i].second) + b * val[i]);
                    }
                }
            }
        }
        dp[sk][0]=2000000000;
        for (i=0;i<t;i++){
            for (b=0;b<=n;b++){
                if (dp[sk][i]!=2000000000)
                    update(b,1,1,t,i+1,dp[sk][i] - b * val[i]);
                else update(b,1,1,t,i+1,dp[sk][i]);
            }
        }
    }

    for (j=1;j<=s;j++)
        fprintf (fout,"%d\n",dp[j][t]);
    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:91:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&t,&s);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:95:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&val[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
popeala.cpp:93:17: warning: iteration 20008 invokes undefined behavior [-Waggressive-loop-optimizations]
         logg[i] = 1 + logg[i-1];
         ~~~~~~~~^~~~~~~~~~~~~~~
popeala.cpp:92:15: note: within this loop
     for (i=2;i<=20010;i++)
              ~^~~~~~~

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