dijkstra法やるだけ #include <bits/stdc++.h> using namespace std; struct edge{int to,cost;}; typedef pair<int,int> P; int n,m,k,ans,d[3007],miti[100005][3]; const int INF = 1000000000; vector<edge> G[3007]; int main(){ scanf("%d%d%d",&n,&m,&k); for(int i = 0;i <= n;i++)</edge></int,int></bits/stdc++.h>…

DP頭悪すぎて謎な漸化式になったがなぜか通った。闇である。以前にも解いてたっぽい 第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books) - intさわだんのBlack History 第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books) - intさわだん…

想定解は二次元累積和なのですが二次元BITの練習のため二次元BITで解いてみた。 本番では絶対こんな手法は使わない。 計算量はO(K*logM*logN)でだいたいO(10^7)ぐらいなので間に合う。 #include <bits/stdc++.h> using namespace std; int bit[3][1010][1010]; int m,n,k; i</bits/stdc++.h>…