oj.uz

Submission #51377

# Submission time Handle Problem Language Result Execution time Memory
51377 2018-06-17T18:31:20 Z spencercompton Popeala (CEOI16_popeala) C++17
100 / 100
 428 ms 17192 KB 
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    long t, n, s;
    cin >> n >> t >> s;
    long long cumu[t+1];
    cumu[0] = 0;
    for(long i = 1; i<=t; i++){
        cin >> cumu[i];
        cumu[i]+=cumu[i-1];
    }
    bool got[n][t];
    for(long i = 0; i<n; i++){
        string str;
        cin >> str;
        for(long j = 0; j<t; j++){
            got[i][j] = str[j]=='1';
        }
    }
    vector<vector<long long> > best;
    best.resize(s+1);
    
    for(long a = 0; a<=s; a++){
        for(long b = 0; b<=t; b++){
            best[a].push_back(2000000002L);
        }
    }
    best[0][0] = 0L;
    for(long i = 0; i<s; i++){
        long long last[n];
        for(long j= 0; j<n; j++){
            last[j] = -1L;
        }
        long long inactive[t+1];
        long long mini[n+1];
        for(long j = 0; j<=n; j++){
            mini[j] = 2000000002L;
        }
        for(long j = 0; j<t; j++){
            mini[0] = min(mini[0],best[i][j]);
            inactive[j] = 0;
            for(long k = 0; k<=n; k++){
                mini[k] += (long long)(n-k)*(cumu[j+1]-cumu[j]);
            }
            for(long k = 0; k<n; k++){
                if(got[k][j]){
                    continue;
                }
                for(long l = j; l>=0; l--){
                    if(l>last[k]){
                        inactive[l]++;
                        mini[inactive[l]] = min(mini[inactive[l]],best[i][l]+(cumu[j+1]-cumu[l])*(long long)(n-inactive[l]));
                    }
                    else{
                        break;
                    }
                }
                last[k] = j;
            }
            for(long k = 0; k<=n; k++){
                best[i+1][j+1] = min(best[i+1][j+1],mini[k]);
            }
        }
    }
    for(long i = 1; i<=s; i++){
        cout << best[i][t] << endl;
    }
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 680 KB Output is correct
2 Correct 12 ms 752 KB Output is correct
3 Correct 13 ms 796 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2044 KB Output is correct
2 Correct 84 ms 2544 KB Output is correct
3 Correct 84 ms 3076 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 11 ms 680 KB Output is correct
4 Correct 12 ms 752 KB Output is correct
5 Correct 13 ms 796 KB Output is correct
6 Correct 43 ms 2044 KB Output is correct
7 Correct 84 ms 2544 KB Output is correct
8 Correct 84 ms 3076 KB Output is correct
9 Correct 139 ms 4776 KB Output is correct
10 Correct 174 ms 6164 KB Output is correct
11 Correct 422 ms 12632 KB Output is correct
12 Correct 423 ms 13844 KB Output is correct
13 Correct 428 ms 14784 KB Output is correct
14 Correct 409 ms 15912 KB Output is correct
15 Correct 416 ms 17192 KB Output is correct