oj.uz

Submission #698082

# Submission time Handle Problem Language Result Execution time Memory
698082 2023-02-12T09:26:22 Z abcvuitunggio Popeala (CEOI16_popeala) C++17
0 / 100
 11 ms 2396 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
const int INF=1e18;
int dp[20001][51],n,T,s,t[20001],a[51][20001],cur;
string score[51];
vector <pair <int, int>> ve[51];
int C(int i, int j){
    int cnt=0;
    for (int k=1;k<=n;k++)
        cnt+=(a[k][j]-a[k][i-1]==j-i+1);
    return (t[j]-t[i-1])*cnt;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> T >> s;
    for (int i=1;i<=T;i++){
        cin >> t[i];
        t[i]+=t[i-1];
    }
    for (int i=1;i<=n;i++){
        cin >> score[i];
        for (int j=0;j<T;j++)
            a[i][j+1]=a[i][j]+score[i][j]-'0';
    }
    for (int i=1;i<=T;i++)
        dp[i][0]=INF;
    ve[0].push_back({1,0});
    for (int j=1;j<=s;j++){
        for (int i=j;i<=T;i++){
            int k=upper_bound(ve[j-1].begin(),ve[j-1].end(),make_pair(i,INF))-ve[j-1].begin()-1;
            k=ve[j-1][k].second;
            dp[i][j]=dp[k][j-1]+C(k+1,i);
            while (!ve[j].empty()){
                auto [x,k]=ve[j].back();
                if (x>i&&dp[i][j]+C(i+1,x)<dp[k][j]+C(k+1,x)){
                    ve[j].pop_back();
                    continue;
                }
                break;
            }
            if (ve[j].empty())
                ve[j].push_back({1,i});
            else{
                auto [x,k]=ve[j].back();
                int l=x+1,r=n,kq=-1;
                while (l<=r){
                    int mid=(l+r)>>1;
                    if (mid>i&&dp[i][j]+C(i+1,mid)<dp[k][j]+C(k+1,mid)){
                        kq=mid;
                        r=mid-1;
                    }
                    else
                        l=mid+1;
                }
                if (kq!=-1)
                    ve[j].push_back({kq,i});
            }
        }
        cout << dp[T][j] << '\n';
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -