Submission #602620

#TimeUsernameProblemLanguageResultExecution timeMemory
602620HamletPetrosyanSightseeing in Kyoto (JOI22_kyoto)C++17
10 / 100
46 ms27656 KiB
/// #if (code == true) #include <bits/stdc++.h> using namespace std; #define pll pair<long long, long long> #define len(a) ((int)((a).size())) #define all(a) a.begin(), a.end() #define add push_back #define mkp make_pair #define ll long long #define fr first #define sc second const long long INF = 1000000000ll * 1000000003ll; const long long MOD = 1000000007ll; const int N = 1e5 + 5; ll h, w, a[N], b[N]; ll cnta[N], cntb[N], dp[3005][3005]; bool ss[N], cc[N]; void solve(){ cin >> h >> w; for(int i = 1; i <= h; i++){ cin >> a[i]; } for(int i = 1; i <= w; i++){ cin >> b[i]; } for(int i = 1; i <= max({w, h, 3000ll}); i++){ dp[0][i] = dp[i][0] = INF; } if(h <= 1000 && w <= 1000){ for(int i = 1; i <= h; i++){ for(int j = 1; j <= w; j++){ if(i == j && i == 1) continue; dp[i][j] = min(dp[i - 1][j] + b[j], dp[i][j - 1] + a[i]); } } cout << dp[h][w] << "\n"; return; } for(int i = 1; i <= h; i++){ cnta[a[i]]++; } for(int i = 1; i <= w; i++){ cntb[b[i]]++; } vector<ll> na, nb, nad, nbd; ll now = 0; for(int i = 1; i <= h; i++){ if(!ss[a[i]]){ na.add(a[i]); nad.add(now); now = 0; ss[a[i]] = 1; } else if(cnta[a[i]] == 1){ na.add(a[i]); nad.add(now); now = 0; } now++; cnta[a[i]]--; } now = 0; for(int i = 1; i <= w; i++){ if(!cc[b[i]]){ nb.add(b[i]); nbd.add(now); now = 0; cc[b[i]] = 1; } else if(cntb[b[i]] == 1){ nb.add(b[i]); nbd.add(now); now = 0; } now++; cntb[b[i]]--; } // for(int i = 0; i < len(na); i++){ // cout << na[i] << " "; // } // cout << endl; // for(int i = 0; i < len(nad); i++){ // cout << nad[i] << " "; // } // cout << endl << endl; // // for(int i = 0; i < len(nb); i++){ // cout << nb[i] << " "; // } // cout << endl; // for(int i = 0; i < len(nbd); i++){ // cout << nbd[i] << " "; // } // cout << endl << endl; for(int i = 0; i < len(na); i++){ for(int j = 0; j < len(nb); j++){ if(i == j && i == 0) continue; dp[i + 1][j + 1] = min(dp[i + 1][j] + na[i] * nbd[j], dp[i][j + 1] + nb[j] * nad[i]); // cout << i << " " << j << " : " << na[i] << " " << nad[i] << " : " << nb[j] << " " << nbd[j] << " " << dp[i + 1][j] << " " << dp[i][j + 1] << endl; } } // for(int i = 1; i <= len(na); i++){ // for(int j = 1; j <= len(nb); j++){ // cout << dp[i][j] << " "; // } // cout << endl; // } // cout << endl; cout << dp[len(na)][len(nb)] << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int _ = 1; // cout << fixed; // cout.precision(15); // cin >> _ ; while(_--) solve(); return 0; } /// #else /// #include <bits/stdc++.h> using namespace std; int main() { cout << "Hello World!"; } /// #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...