解法 二次元累積和を計算しておくと矩形の範囲の値の総和をO(1)で計算できる。あとは切る位置を全通り試すO(H^2W^2)をすればよい。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typed</ll></vi></int></bits/stdc++.h>…

解法 i,jから始まる部分列について同型である直線の長さを考える。各区間について傾きが等しく、比率が等しいならば同型であると判定できる。 i+k→i+k+1、j+k→j+k+1の線分について傾きが等しく、day[i+k+1]-day[i+k] と day[j+k+1] - day[j+k] の比率が等し…

概要 M種類の品物を売っている店でN人の人が買い物に来た。同じものを2つ以上買った人はいない。商品iが売れた数はS[i]である。このとき、K個以上の商品を買った人を大口顧客と呼ぶ。このとき、大口顧客の最少人数を求めろ。 解法 できるだけ大口顧客の数を…