Submission #49281

#	Time	Username	Problem	Language	Result	Execution time	Memory
49281		Benq	Popeala (CEOI16_popeala)	C++14	100 / 100	1303 ms	14680 KiB

popeala

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;

int N,T,S, poi[20000];
ll ans[20001][51], mn[51]; 
string res[50];
int tmp[50], mnind[51];
multiset<int> cur;

ll getSum(int l, int r) {
    if (l == 0) return poi[r];
    return poi[r]-poi[l-1];
}

void solve(int x) {
    // up to i 
    
    cur.clear();
    F0R(i,N+1) {
        mn[i] = 2*MOD; // fix this?
        mnind[i] = x-2;
    }
    F0R(i,N) {
        tmp[i] = 0;
        cur.insert(tmp[i]);
    }
    
    F0R(i,T) {
        F0R(j,N) if (res[j][i] == '0') {
            cur.erase(cur.find(tmp[j]));
            tmp[j] = i+1;
            cur.insert(tmp[j]);
        }
        // 0th: 1st-1
        ans[i+1][x] = 2*MOD;
        
        int co = 0;
        for (int j: cur) {
            while (mnind[co] < j-1) {
                mnind[co] ++;
                mn[co] = min(mn[co],ans[mnind[co]][x-1]+co*getSum(mnind[co],N-1));
            }
            ans[i+1][x] = min(ans[i+1][x],mn[co]-co*getSum(i+1,N-1));
            co ++;
        }
        while (mnind[co] < i) {
            mnind[co] ++;
            //cout << "ZZ " << mnind[co] << "\n";
            mn[co] = min(mn[co],ans[mnind[co]][x-1]+co*getSum(mnind[co],N-1));
            ans[i+1][x] = min(ans[i+1][x],mn[co]-co*getSum(i+1,N-1));
        }
        // cout << "HI " << i+1 << " " << x << " " << ans[i+1][x] << " " << mnind[0] <<  "\n";
        /*for (int j: cur) cout << j << " ";
        cout << "\n";*/
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> T >> S;
    F0R(i,T) {
        cin >> poi[i];
        if (i) poi[i] += poi[i-1];
    }
    F0R(i,N) cin >> res[i];
    FOR(i,1,T+1) ans[i][0] = 2*MOD;
    FOR(i,1,S+1) {
        solve(i);
        cout << ans[T][i] << "\n";
    }
} // OK

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74