Submission #709241

#	Time	Username	Problem	Language	Result	Execution time	Memory
709241		minhcool	Sightseeing in Kyoto (JOI22_kyoto)	C++17	10 / 100	10 ms	12324 KiB

kyoto

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;
 
int n, m;
int r[N], c[N];
 
int arr[5005][5005];
 
map<int, int> mp;
 
vector<int> pos1, pos2;
 
void process(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> r[i];
    for(int i = 1; i <= m; i++) cin >> c[i];
    for(int i = 1; i <= n; i++){
    	if(mp[r[i]]) continue;
    	mp[r[i]] = i;
    	pos1.pb(i);
	}
	mp.clear();
	for(int i = n; i >= 1; i--){
		if(mp[r[i]]) continue;
		mp[r[i]] = i;
		pos1.pb(i);
	}
	mp.clear();
	for(int i = 1; i <= m; i++){
		if(mp[c[i]]) continue;
		mp[c[i]] = i;
		pos2.pb(i);
	}
	for(int i = m; i >= 1; i--){
		if(mp[c[i]]) continue;
		mp[c[i]] = i;
		pos2.pb(i);
	}
	pos1.pb(1), pos1.pb(n), pos2.pb(1), pos2.pb(m);
	sort(pos1.begin(), pos1.end());
	pos1.resize(unique(pos1.begin(), pos1.end()) - pos1.begin());
	sort(pos2.begin(), pos2.end());
	pos2.resize(unique(pos2.begin(), pos2.end()) - pos2.begin());
  assert(pos1.size() <= 2500), assert(pos2.size() <= 2500);
    for(int i = 0; i < pos1.size(); i++){
    	for(int j = 0; j < pos2.size(); j++) arr[i][j] = oo;
	}
	arr[0][0] = 0;
	for(int i = 1; i < pos2.size(); i++) arr[0][i] = r[pos1[0]] * (pos2[i] - 1);
	for(int i = 1; i < pos1.size(); i++) arr[i][0] = c[pos2[0]] * (pos1[i] - 1); 
	for(int i = 1; i < pos1.size(); i++){
		for(int j = 1; j < pos2.size(); j++){
			arr[i][j] = min(arr[i][j - 1] + r[pos1[i]] * (pos2[j] - pos2[j - 1]), arr[i - 1][j] + c[pos2[j]] * (pos1[i] - pos1[i - 1])); 
		}
	}
	/*
	for(int i = 0; i < pos1.size(); i++){
		for(int j = 0; j < pos2.size(); j++) cout << arr[i][j] << " ";
		cout << "\n";
	}*/
	cout << arr[pos1.size() - 1][pos2.size() - 1];
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    //freopen("KEK.inp", "r", stdin);
    //freopen("KEK.out", "w", stdout);
    cin.tie(0);
    process();
}

Compilation message (stderr)

kyoto.cpp: In function 'void process()':
kyoto.cpp:57:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0; i < pos1.size(); i++){
      |                    ~~^~~~~~~~~~~~~
kyoto.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |      for(int j = 0; j < pos2.size(); j++) arr[i][j] = oo;
      |                     ~~^~~~~~~~~~~~~
kyoto.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 1; i < pos2.size(); i++) arr[0][i] = r[pos1[0]] * (pos2[i] - 1);
      |                 ~~^~~~~~~~~~~~~
kyoto.cpp:62:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 1; i < pos1.size(); i++) arr[i][0] = c[pos2[0]] * (pos1[i] - 1);
      |                 ~~^~~~~~~~~~~~~
kyoto.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 1; i < pos1.size(); i++){
      |                 ~~^~~~~~~~~~~~~
kyoto.cpp:64:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j = 1; j < pos2.size(); j++){
      |                  ~~^~~~~~~~~~~~~

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