oj.uz

Submission #1032697

# Submission time Handle Problem Language Result Execution time Memory
1032697 2024-07-24T06:24:07 Z 변재우(#10969) Popeala (CEOI16_popeala) C++17
0 / 100
 109 ms 8796 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Kmax=55, Nmax=20010, INF=1e18;
int N, T, S, A[Nmax], D[Kmax][Nmax];
string R[Kmax];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>T>>S;
    for(int i=1; i<=T; i++) cin>>A[i], A[i]+=A[i-1];
    for(int i=1; i<=N; i++) cin>>R[i];
    for(int i=0; i<=S; i++) for(int j=0; j<=T; j++) D[i][j]=INF;
    D[0][0]=0;
    for(int i=1; i<=S; i++) {
        int P[Kmax]={0};
        for(int j=1; j<=T; j++) {
            vector<int> V;
            for(int k=1; k<=N; k++) {
                if(R[k][j-1]=='0') P[k]=j;
                if(P[k]) V.emplace_back(P[k]);
            }
            sort(V.rbegin(), V.rend());
            D[i][j]=min(D[i][j], D[i-1][j-1]+(A[j]-A[j-1])*N);
            for(int k=0, c=N; k<V.size(); k++) {
                int p=k;
                for(int l=k; l<V.size() && V[k]==V[l]; l++) p=l, c--;
                if(V[k]) D[i][j]=min(D[i][j], D[i-1][V[k]-1]+(A[j]-A[V[k]-1])*c);
                k=p;
                if(k==V.size()-1) D[i][j]=min(D[i][j], D[i-1][0]+A[j]*c);
            }
        }
    }
    for(int i=1; i<=S; i++) cout<<D[i][T]<<"\n";
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:26:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for(int k=0, c=N; k<V.size(); k++) {
      |                               ~^~~~~~~~~
popeala.cpp:28:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |                 for(int l=k; l<V.size() && V[k]==V[l]; l++) p=l, c--;
      |                              ~^~~~~~~~~
popeala.cpp:31:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 if(k==V.size()-1) D[i][j]=min(D[i][j], D[i-1][0]+A[j]*c);
      |                    ~^~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

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