Submission #608792

#	Time	Username	Problem	Language	Result	Execution time	Memory
608792		BJoozz	Popeala (CEOI16_popeala)	C++14	0 / 100	23 ms	1492 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;}
//ii C[MAX],R[MAX];
//int a[MAX][MAX];
int dp[MAX],C[MAX];
int A[MAX],a[MAX];
char s[MAX];
int F[52][MAX];
int D[MAX];
int n,S,T;
void solve(int l,int r,int u,int v){

    int mid=l+r>>1;
    int cs=u,temp=n;
    int en=min(v,mid-1);
    for(int i=1;i<=n;i++){
        if(F[i][mid]>en) temp--;
        else D[F[i][mid]]++;
    }
    //if(mid==1)cout<<u<<' '<<en<<' '<<dp[1]<<' '<<C[0]<<'\n';
    for(int i=en;i>=u;i--){
        if(cmin(dp[mid],C[i]+(A[mid]-A[i])*temp)) cs=i;
        temp-=D[i];
    }
    for(int i=1;i<=n;i++)D[F[i][mid]]=0;
    if(l<mid)solve(l,mid-1,u,cs);if(mid<r)solve(mid+1,r,cs,v);
}
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=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;
    }
    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];
        memset(dp,0x3f,sizeof dp);
        solve(1,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 'void solve(long long int, long long int, long long int, long long int)':
popeala.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid=l+r>>1;
      |             ~^~
popeala.cpp:49:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   49 |     if(l<mid)solve(l,mid-1,u,cs);if(mid<r)solve(mid+1,r,cs,v);
      |     ^~
popeala.cpp:49:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |     if(l<mid)solve(l,mid-1,u,cs);if(mid<r)solve(mid+1,r,cs,v);
      |                                  ^~
popeala.cpp: In function 'int main()':
popeala.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         cin>>s+1;
      |              ~^~

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