Submission #681037

#	Time	Username	Problem	Language	Result	Execution time	Memory
681037		minhnhatnoe	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	640 ms	129684 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cycle_len;
vector<pair<int, int>> a;
vector<vector<vector<array<ll, 2>>>> dp;

// Counter-clockwise
ll get_dist(ll l, ll r){
    if (l < -1 || l > a.size()) return 1e15;
    if (r < -1 || r > a.size()) return 1e15;
    if (l == -1 || l == a.size()) l = 0;
    else l = a[l].first;
    if (r == -1 || r == a.size()) r = 0;
    else r = a[r].first;
    return (l + cycle_len - r) % cycle_len;
}
ll get_time(int idx){
    if (idx == -1 || idx == a.size()) return -1;
    return a[idx].second;
}
ll f(int l, int r, int picked, bool lr){
    if (l == -1 || l == a.size()+1 || r == -1 || r == a.size()+1 || picked == -1) return 1e15;
    if (l + r > a.size()) return 1e15;
    if (l == 0 && r == 0){
        if (picked) return 1e15;
        return 0;
    }
    ll& value = dp[l][r][picked][lr];
    if (value != -1) return value;
    value = 1e15;
    if (!lr){
        // At left
        
        // Case 1: From left
        {
            ll picking = f(l-1, r, picked-1, false) + get_dist(l-1, l-2);
            if (picking <= get_time(l-1)) value = min(value, picking);
            ll not_picking = f(l-1, r, picked, false) + get_dist(l-1, l-2);
            value = min(value, not_picking);
        }
        // Case 2: From right
        {
            ll picking = f(l-1, r, picked-1, true) + get_dist(l-1, a.size()-r);
            if (picking <= get_time(l-1)) value = min(value, picking);
            ll not_picking = f(l-1, r, picked, true) + get_dist(l-1, a.size()-r);
            value = min(value, not_picking);
        }
    }
    else{
        // At right

        // Case 1: From right
        {
            ll picking = f(l, r-1, picked-1, true) + get_dist(a.size()-r+1, a.size()-r);
            if (picking <= get_time(a.size()-r)) value = min(value, picking);
            ll not_picking = f(l, r-1, picked, true) + get_dist(a.size()-r+1, a.size()-r);
            value = min(value, not_picking);
        }
        // Case 2: From left 
        {
            ll picking = f(l, r-1, picked-1, false) + get_dist(l-1, a.size()-r);
            if (picking <= get_time(a.size()-r)) value = min(value, picking);
            ll not_picking = f(l, r-1, picked, false) + get_dist(l-1, a.size()-r);
            value = min(value, not_picking);
        }
    }
    return value;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n >> cycle_len;
    a.resize(n);
    for (int i=0; i<n; i++){
        cin >> a[i].first;
        a[i].first %= cycle_len;
    }
    for (int i=0; i<n; i++){
        cin >> a[i].second;
    }
    sort(a.begin(), a.end());
    dp.assign(n+1, vector<vector<array<ll, 2>>> (n+1, vector<array<ll, 2>> (n+1, array<ll, 2>({-1, -1}))));
    for (int result = n; result >= 0; result--){
        for (int l=0; l<=a.size(); l++){
            for (int r=0; r<=a.size(); r++){
                if (f(l, r, result, false) < 1e15 || f(l, r, result, true) < 1e15){
                    cout << result << "\n";
                    return 0;
                }
            }
        }
    }

}

Compilation message (stderr)

ho_t3.cpp: In function 'll get_dist(ll, ll)':
ho_t3.cpp:10:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if (l < -1 || l > a.size()) return 1e15;
      |                   ~~^~~~~~~~~~
ho_t3.cpp:11:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     if (r < -1 || r > a.size()) return 1e15;
      |                   ~~^~~~~~~~~~
ho_t3.cpp:12:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (l == -1 || l == a.size()) l = 0;
      |                    ~~^~~~~~~~~~~
ho_t3.cpp:14:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if (r == -1 || r == a.size()) r = 0;
      |                    ~~^~~~~~~~~~~
ho_t3.cpp: In function 'll get_time(int)':
ho_t3.cpp:19:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if (idx == -1 || idx == a.size()) return -1;
      |                      ~~~~^~~~~~~~~~~
ho_t3.cpp: In function 'll f(int, int, int, bool)':
ho_t3.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if (l == -1 || l == a.size()+1 || r == -1 || r == a.size()+1 || picked == -1) return 1e15;
      |                    ~~^~~~~~~~~~~~~
ho_t3.cpp:23:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if (l == -1 || l == a.size()+1 || r == -1 || r == a.size()+1 || picked == -1) return 1e15;
      |                                                  ~~^~~~~~~~~~~~~
ho_t3.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if (l + r > a.size()) return 1e15;
      |         ~~~~~~^~~~~~~~~~
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int l=0; l<=a.size(); l++){
      |                       ~^~~~~~~~~~
ho_t3.cpp:85:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for (int r=0; r<=a.size(); r++){
      |                           ~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75