oj.uz

Submission #947869

# Submission time Handle Problem Language Result Execution time Memory
947869 2024-03-17T07:45:08 Z Darren0724 Popeala (CEOI16_popeala) C++17
100 / 100
 812 ms 18840 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int INF=1e18;
 
int32_t main() {
    LCBorz;
    int n,t,s;cin>>n>>t>>s;
    vector<int> v(t+1);
    for(int i=1;i<=t;i++){
        cin>>v[i];
        v[i]+=v[i-1];
    }
    vector pre(n,vector(t+1,0)),last(t+1,vector(n+2,0));
    for(int i=0;i<n;i++){
        for(int j=1;j<=t;j++){
            char c;cin>>c;
            pre[i][j]=c-'0'+pre[i][j-1];
            last[j][i]=(c=='0'?j:last[j-1][i]);
        }   
    }
    for(int j=1;j<=t;j++){
        last[j][n]=j;
        sort(all(last[j]));
    }
    vector dp(s+1,vector(t+1,INF));
    dp[0][0]=0;
    for(int i=1;i<=s;i++){
        deque<int> d[n+1];
        for(int j=1;j<=t;j++){
            for(int cnt=0;cnt<=n;cnt++){
                while(d[cnt].size()&&d[cnt].front()<last[j][cnt]){
                    d[cnt].pop_front();
                }
                for(int i1=last[j-1][cnt+1];i1<last[j][cnt+1];i1++){
                    while(d[cnt].size()&&dp[i-1][d[cnt].front()]-cnt*v[d[cnt].front()]>=dp[i-1][i1]-cnt*v[i1]){
                        d[cnt].pop_front();
                    }
                    d[cnt].push_back(i1);
                }
                if(d[cnt].size()){
                    dp[i][j]=min(dp[i][j],dp[i-1][d[cnt].front()]+cnt*v[j]-cnt*v[d[cnt].front()]);
                }
                /*for(int k=last[j][cnt];k<last[j][cnt+1];k++){
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+cnt*(v[j]-v[k]));
                }*/

            }
        }
    }
    for(int i=1;i<=s;i++){
        cout<<dp[i][t]<<endl;
    }
 
    
    return 0;
}
/*
5 5 5
1 5 2 4 3
11010
00101
10011
00010
11011
0
3
12
22
40
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 860 KB Output is correct
2 Correct 20 ms 860 KB Output is correct
3 Correct 20 ms 860 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2392 KB Output is correct
2 Correct 140 ms 3192 KB Output is correct
3 Correct 164 ms 4108 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 21 ms 860 KB Output is correct
4 Correct 20 ms 860 KB Output is correct
5 Correct 20 ms 860 KB Output is correct
6 Correct 95 ms 2392 KB Output is correct
7 Correct 140 ms 3192 KB Output is correct
8 Correct 164 ms 4108 KB Output is correct
9 Correct 242 ms 6236 KB Output is correct
10 Correct 357 ms 8172 KB Output is correct
11 Correct 680 ms 18196 KB Output is correct
12 Correct 711 ms 18688 KB Output is correct
13 Correct 789 ms 18788 KB Output is correct
14 Correct 812 ms 18784 KB Output is correct
15 Correct 806 ms 18840 KB Output is correct