oj.uz

Submission #609223

# Submission time Handle Problem Language Result Execution time Memory
609223 2022-07-27T12:53:56 Z BJoozz Popeala (CEOI16_popeala) C++14
100 / 100
 288 ms 37160 KB 
#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));
        //cout<<"st "<<v<<'\n';for(ii u:V[v]) cout<<u.X<<' '<<u.Y<<'\n';
    }
    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=0;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]-A[i]*j);
                //if(zz==2 &&j==1)cout<<"here "<<i<<' '<<dp[i]<<' '<<A[i]<<'\n';
            }
        }
        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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2388 KB Output is correct
2 Correct 6 ms 2368 KB Output is correct
3 Correct 5 ms 2388 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5172 KB Output is correct
2 Correct 27 ms 6868 KB Output is correct
3 Correct 37 ms 8660 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct
3 Correct 6 ms 2388 KB Output is correct
4 Correct 6 ms 2368 KB Output is correct
5 Correct 5 ms 2388 KB Output is correct
6 Correct 20 ms 5172 KB Output is correct
7 Correct 27 ms 6868 KB Output is correct
8 Correct 37 ms 8660 KB Output is correct
9 Correct 70 ms 13104 KB Output is correct
10 Correct 104 ms 16884 KB Output is correct
11 Correct 238 ms 36360 KB Output is correct
12 Correct 241 ms 37064 KB Output is correct
13 Correct 281 ms 36872 KB Output is correct
14 Correct 288 ms 36912 KB Output is correct
15 Correct 270 ms 37160 KB Output is correct