Submission #106449

#	Time	Username	Problem	Language	Result	Execution time	Memory
106449		tictaccat	Meetings (IOI18_meetings)	C++14	0 / 100	5571 ms	5820 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll INF = 1e18;

int Q,N;
vector<int> H;
vector<vector<int>> indices(20+1);

unordered_map<ll,int> dp;

ll f (int i, int j, ll hMax) {
    if (i > j) return 0;
    if (hMax == 1) return j-i+1;
    ll h = (ll)i + (ll)(1e5)*j + (ll)(1e10)*hMax;
    if (dp.count(h) > 0) {
       // cout << "test";
        return dp[h];
    }
    auto left = lower_bound(indices[hMax].begin(),indices[hMax].end(),i);
    auto right = upper_bound(indices[hMax].begin(),indices[hMax].end(),j); 
    if (left == right) return f(i,j,hMax-1);
    ll res = INF;
    for (auto it = left; it != right; it++) {
        int x = (it == left ? i : *prev(it)+1);
        int y = *it-1;
        ll val = f(x,y,hMax-1) + (ll)hMax*(j-i+1 - (y-x+1));
        res = min(res,val);
    }
    int x = *prev(right)+1; int y = j;
    
    ll val = f(x,y,hMax-1) + (ll)hMax*(j - i + 1 - (y-x+1));
    res = min(res,val);
    dp[h] = res;
    return res;
}

vector<long long> minimum_costs(vector<int> tempH, vector<int> L, vector<int> R) {

    H = tempH; Q = L.size(); N = H.size();

    for (int i = 0; i < N; i++) indices[H[i]].push_back(i);

    vector<long long> C(Q,-1);

    for (int q = 0; q < Q; q++) {
        C[q] = f(L[q],R[q],20);
    }

  return C;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40