oj.uz

Submission #106451

# Submission time Handle Problem Language Result Execution time Memory
106451 2019-04-18T14:18:41 Z tictaccat Meetings (IOI18_meetings) C++14
0 / 100
 5500 ms 23604 KB 
#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);

    dp.reserve(22*N);

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

  return C;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 695 ms 4644 KB Output is correct
3 Execution timed out 5525 ms 23604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 695 ms 4644 KB Output is correct
3 Execution timed out 5525 ms 23604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -