Submission #786918

#	Time	Username	Problem	Language	Result	Execution time	Memory
786918		eltu0815	Sightseeing in Kyoto (JOI22_kyoto)	C++14	0 / 100	1 ms	340 KiB

kyoto

#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define inf (1987654321)
 
using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
int n, m, q;
ll a[100005], b[100005];
ll dp[2005][2005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= m; ++i) cin >> b[i];
    a[0] = b[0] = inf, a[n + 1] = b[m + 1] = inf;
    
    vector<int> row, col;
    for(ll i = 1, p = INF; i <= n; ++i) if(p > a[i]) row.push_back(i), p = a[i];
    for(ll i = 1, p = INF; i <= m; ++i) if(p > b[i]) col.push_back(i), p = b[i];
    
    int rmn = row.back(), cmn = col.back();
    for(ll i = n, p = INF; i >= rmn; --i) if(p > a[i]) row.push_back(i), p = a[i];
    for(ll i = m, p = INF; i >= cmn; --i) if(p > b[i]) col.push_back(i), p = b[i];
    sort(row.begin(), row.end()); row.erase(unique(row.begin(), row.end()), row.end());
    sort(col.begin(), col.end()); col.erase(unique(col.begin(), col.end()), col.end());
    
    int r = 0, c = 0; ll ans = 0;
    while(col[c] < cmn) {
        while(row[r] < rmn) {
            ll rl = row[r + 1] - row[r], cl = col[c + 1] - col[c];
            if(a[row[r]] * cl + b[col[c + 1]] * rl < a[row[r + 1]] * cl + b[col[c]] * rl) break;
            ans += b[col[c]] * rl; ++r;
        }
        ans += a[row[r]] * (col[c + 1] - col[c]); ++c;
    }
    ans += b[cmn] * (rmn - row[r]);
    
    r = row.size() - 1, c = col.size() - 1;
    while(col[c] > cmn) {
        while(row[r] > rmn) {
            int rl = row[r] - row[r - 1], cl = col[c] - col[c - 1];
            if(a[row[r]] * cl + b[col[c - 1]] * rl < a[row[r - 1]] * cl + b[col[c]] * rl) break;
            ans += 1ll * b[col[c]] * rl, --r;
        }
        ans += 1ll * a[row[r]] * (col[c] - col[c - 1]);
        --c;
    }
    ans += 1ll * b[cmn] * (row[r] - rmn);
    cout << ans;
    return 0;
}

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