Submission #561348

#	Time	Username	Problem	Language	Result	Execution time	Memory
561348		wiwiho	Sightseeing in Kyoto (JOI22_kyoto)	C++14	40 / 100	567 ms	1048576 KiB

kyoto

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define pob pop_back()
#define ef emplace_front
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

const ll MOD = 1000000007;

void topos(ll& a){
    a = (a % MOD + MOD) % MOD;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<pll> a(n), b(m);
    for(int i = 0; i < n; i++) cin >> a[i].F, a[i].S = i;
    for(int i = 0; i < m; i++) cin >> b[i].F, b[i].S = i;
    lsort(a);
    lsort(b);

    auto solve = [&](vector<pll>& v){
        deque<pll> r;
        for(pll i : v){
            if(r.empty()){
                r.eb(i);
                continue;
            }
            if(r.front().S < i.S && i.S < r.back().S) continue;
            if(i.S < r.front().S){
                if(i.F == r.front().F && r.size() > 1) r.pof;
                r.ef(i);
            }
            if(r.back().S < i.S){
                if(i.F == r.back().F && r.size() > 1) r.pob;
                r.eb(i);
            }
        }
        v.clear();
        for(pll i : r) v.eb(i);
    };
    solve(a);
    solve(b);
    n = a.size(); m = b.size();

    vector<vector<ll>> dp(n, vector<ll>(m, 1LL << 60));
    dp[0][0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[j].F * (a[i].S - a[i - 1].S));
            if(j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i].F * (b[j].S - b[j - 1].S));
        }
    }
    cout << dp[n - 1][m - 1] << "\n";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60