oj.uz

Submission #98726

# Submission time Handle Problem Language Result Execution time Memory
98726 2019-02-25T12:20:26 Z SpeedOfMagic Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 1024 KB 
/** MIT License Copyright (c) 2018-2019 Vasilev Daniil **/
#include <bits/stdc++.h>
using namespace std;
template<typename T> using v = vector<T>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
const long double EPS = 1e-10;
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin >>
#define put fout <<
#else
#define get cin >>
#define put cout <<
#endif
#define eol put endl
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
int getInt(){int a; get a; return a;}
//code starts here

void run() {
    int n, t, s;
    read(n, t, s);
    int pts[t];
    rep(i, 0, t)
        get pts[i];

    char res[n][t];
    rep(i, 0, n) {
        str st;
        get st;
        rep(j, 0, t)
            res[i][j] = st[j] - '0';
    }

    int dp[t][s];
    rep(i, 0, t)
        rep(j, 0, s)
            dp[i][j] = 2000000001;

    int cur[n];
    memset(cur, 0, sizeof cur);
    rep(i, 0, t) {
        rep(j, 0, n)
            if (res[j][i] && cur[j] != -1)
                cur[j] += pts[i];
            else
                cur[j] = -1;

        dp[i][0] = 0;
        rep(j, 0, n)
            if (cur[j] != -1)
                dp[i][0] += cur[j];
    }

    rep(j, 1, s) {
        rep(i, 0, t) {
            memset(cur, 0, sizeof cur);
            for (int k = i - 1; k >= 0; k--) {
                int sum = 0;
                rep(l, 0, n) {
                    if (res[l][k + 1] && cur[l] != -1)
                        cur[l] += pts[k + 1];
                    else
                        cur[l] = -1;
                    if (cur[l] != -1)
                        sum += cur[l];
                }
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + sum);
            }
        }
    }

    rep(j, 0, s)
        put dp[t - 1][j], eol;
}
signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); return 0;}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 560 KB Output is correct
2 Correct 781 ms 512 KB Output is correct
3 Correct 890 ms 632 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 1024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 813 ms 560 KB Output is correct
4 Correct 781 ms 512 KB Output is correct
5 Correct 890 ms 632 KB Output is correct
6 Execution timed out 2037 ms 1024 KB Time limit exceeded
7 Halted 0 ms 0 KB -