横棒を通るときに、番号をその棒に記録しておけば、もう片方から来たときにO(1)で交差してることが分かります。 交差を切ることで、得点を入れ替えることができるから、最も得点差(点数を減らせる量)の大きいものを求めれば良いです。 #include<cstdio> #include<cstring> #in</cstring></cstdio>…

愚直に全てシミュレーションするとTLEするので、N-1回散歩した後の地図を求めます。 ある点をn回通るとき、 (i) nが偶数のとき、東と南にn/2回ずつ通る (ii)nが奇数のとき、最初に書かれていた文字の方向に(n+1)/2回、もう一方に(n-1)/2回通る よって、通過…

特定の区間に足し算をするのを高速(全体でO(n+m)くらい)に行えば良いから、累積和で解くことができます。 #include<cstdio> #include<algorithm> using namespace std; #define MOD 100000 int inn[100000],walk[100001]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i </algorithm></cstdio>…

動的計画法で解けます。引っかかる人はほとんどいないかもしれませんがコーナーケース(最初が0のとき)があります。 #include<iostream> using namespace std; typedef long long ll; ll dp[100][21]; int data[100]; int main(){ int n; cin>>n; for(int i = 0; i < n;</iostream>…