Submission #609189

#	Time	Username	Problem	Language	Result	Execution time	Memory
609189		BJoozz	Popeala (CEOI16_popeala)	C++14	0 / 100	20 ms	5156 KiB

popeala

#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;

#define int long long
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
typedef pair < int , int > ii;
using ll = long long;
using ld = long double;
const int MAX=20000+5,inf=1e16,mod=1e9+7;
template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}
void maxx(int &a,int b){if(b>a)a=b;}
void minn(int &a,int b){if(b<a)a=b;}
struct qb{
    int x,y,z;
    qb(int x,int y,int z):x(x),y(y),z(z){};
};
//ii C[MAX],R[MAX];
//int a[MAX][MAX];
int dp[MAX],C[52][MAX];
int LG[MAX];
vector < ii > V[MAX];
int A[MAX],a[MAX];
char s[MAX];
int F[52][MAX];
int D[MAX];
int n,S,T;

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("popeala.inp","r",stdin);freopen("popeala.out","w",stdout);
    cin>>n>>T>>S;
    for(int i=1;i<=T;i++)cin>>a[i],A[i]=A[i-1]+a[i];
    for(int i=2;i<MAX;i++) LG[i]=LG[i>>1]+1;
    for(int i=1;i<=n;i++){
        cin>>s+1;
        for(int j=1;j<=T;j++)
        if(s[j]=='1') F[i][j]=F[i][j-1];
        else F[i][j]=j;
    }
    vector < int > vec;
    for(int v=1;v<=T;v++){
        vec.clear();
        for(int i=1;i<=n;i++)
            vec.pb(F[i][v]);
        sort(vec.begin(),vec.end(),greater < int >());
        int temp=n,pre=v;
        for(int u:vec)if(u==pre)
            temp--;
        else{
            V[v].pb(ii(pre-1,temp));
            temp--;
            pre=u;
        }
        if(pre)V[v].pb(ii(pre-1,temp));
    }
    memset(dp,0x3f,sizeof dp);dp[0]=0;
    for(int zz=1;zz<=S;zz++){
        //for(int j=0;j<=T;j++) C[j]=dp[j],ST[0][j]=dp[j];

        for(int j=1;j<=n;j++){
            C[j][0]=dp[0];
            for(int i=1;i<=T;i++){
                C[j][i]=min(C[j][i-1],dp[i]-j*A[i]);
            }
        }
        memset(dp,0x3f,sizeof dp);
        for(int i=zz;i<=T;i++){
            for(ii u:V[i]){
                minn(dp[i],C[u.Y][u.X]+u.Y*A[i]);
            }
        }
        //solve(zz,T,0,T-1);
        //for(int j=0;j<=T;j++) cout<<dp[j]<<' ';cout<<'\n';
        cout<<dp[T]<<'\n';
    }
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         cin>>s+1;
      |              ~^~

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