oj.uz

Submission #924990

# Submission time Handle Problem Language Result Execution time Memory
924990 2024-02-10T10:22:10 Z JakobZorz Popeala (CEOI16_popeala) C++17
100 / 100
 1220 ms 25684 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
 
int n,t,s;
ll pts[20001];
ll done[51][20001];
ll dp[51][20001];
ll cost[51][20001];
 
void solve(){
    cin>>n>>t>>s;
    for(int i=0;i<t;i++)
        cin>>pts[i];
    for(int i=t-2;i>=0;i--)
        pts[i]+=pts[i+1];
    
    for(int i=0;i<n;i++){
        string str;
        cin>>str;
        for(int j=0;j<t;j++){
            if(str[j]=='1'){
                if(j)
                    done[i][j]=done[i][j-1]+1;
                else
                    done[i][j]=1;
            }
        }
    }
    
    for(int i=0;i<51;i++)
        for(int j=0;j<20001;j++)
            dp[i][j]=1e18;
    
    dp[0][0]=0;
    
    for(int num=1;num<=s;num++){
        for(int p=0;p<=n;p++){
            ll prev=1e18;
            for(int i=0;i<=t;i++){
                cost[p][i]=min(prev,dp[num-1][i]+pts[i]*p);
                prev=cost[p][i];
            }
        }
        
        for(int i=0;i<=t;i++){
            if(i){
                vector<ll>vec;
                vec.push_back(i);
                vec.push_back(0);
                for(int p=0;p<n;p++)
                    vec.push_back(done[p][i-1]);
                sort(vec.begin(),vec.end());
                reverse(vec.begin(),vec.end());
                for(int j=0;j<=n;j++){
                    if(i-vec[j+1]-1>=0)
                        dp[num][i]=min(dp[num][i],cost[j][i-vec[j+1]-1]-pts[i]*j);
                }
            }
        }
    }
    
    for(int i=0;i<s;i++)
        cout<<dp[i+1][t]<<"\n";
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("input.in","r",stdin);freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}
 
/*
 
2 3 3
4 3 5
101
110
 
 
0
8
16
 
 */

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22360 KB Output is correct
2 Correct 27 ms 22872 KB Output is correct
3 Correct 30 ms 22872 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 23172 KB Output is correct
2 Correct 190 ms 23132 KB Output is correct
3 Correct 212 ms 23324 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 31 ms 22360 KB Output is correct
4 Correct 27 ms 22872 KB Output is correct
5 Correct 30 ms 22872 KB Output is correct
6 Correct 136 ms 23172 KB Output is correct
7 Correct 190 ms 23132 KB Output is correct
8 Correct 212 ms 23324 KB Output is correct
9 Correct 268 ms 23084 KB Output is correct
10 Correct 456 ms 23644 KB Output is correct
11 Correct 826 ms 24156 KB Output is correct
12 Correct 996 ms 25536 KB Output is correct
13 Correct 1194 ms 25536 KB Output is correct
14 Correct 1064 ms 25540 KB Output is correct
15 Correct 1220 ms 25684 KB Output is correct