#743705 (C++17) No.1867 Partitions and Inversions

提出ソース

結果

問題	No.1867 Partitions and Inversions
ユーザー	👑 Nachia
提出日時	2022-03-04 23:58:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,839 ms / 5,000 ms
コード長	784 bytes
コンパイル時間	969 ms
コンパイル使用メモリ	84,000 KB
実行使用メモリ	38,448 KB
最終ジャッジ日時	2024-07-18 23:03:03
合計ジャッジ時間	105,082 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2,788 ms 37,428 KB
testcase_03	AC	2,839 ms 37,772 KB
testcase_04	AC	2,764 ms 37,648 KB
testcase_05	AC	2,806 ms 38,044 KB
testcase_06	AC	2,776 ms 37,336 KB
testcase_07	AC	2,782 ms 37,580 KB
testcase_08	AC	2,754 ms 37,732 KB
testcase_09	AC	2,766 ms 38,052 KB
testcase_10	AC	2,799 ms 37,632 KB
testcase_11	AC	2,764 ms 38,260 KB
testcase_12	AC	2,755 ms 38,172 KB
testcase_13	AC	2,726 ms 37,860 KB
testcase_14	AC	2,738 ms 37,704 KB
testcase_15	AC	2,693 ms 37,876 KB
testcase_16	AC	2,726 ms 37,720 KB
testcase_17	AC	2,690 ms 37,732 KB
testcase_18	AC	2,657 ms 38,032 KB
testcase_19	AC	2,784 ms 37,424 KB
testcase_20	AC	2,559 ms 37,600 KB
testcase_21	AC	2,592 ms 38,272 KB
testcase_22	AC	2,750 ms 37,528 KB
testcase_23	AC	2,784 ms 37,576 KB
testcase_24	AC	2,780 ms 37,748 KB
testcase_25	AC	2,656 ms 38,448 KB
testcase_26	AC	2,586 ms 37,852 KB
testcase_27	AC	2,609 ms 37,352 KB
testcase_28	AC	2,586 ms 38,392 KB
testcase_29	AC	2,661 ms 38,084 KB
testcase_30	AC	2,608 ms 38,264 KB
testcase_31	AC	2,471 ms 38,044 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	2 ms 6,944 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	14 ms 10,260 KB
testcase_39	AC	14 ms 9,808 KB
testcase_40	AC	14 ms 9,752 KB
testcase_41	AC	15 ms 10,036 KB
testcase_42	AC	15 ms 10,284 KB
testcase_43	AC	762 ms 27,900 KB
testcase_44	AC	763 ms 27,636 KB
testcase_45	AC	770 ms 27,456 KB
testcase_46	AC	771 ms 27,516 KB
testcase_47	AC	771 ms 28,768 KB
testcase_48	AC	770 ms 27,904 KB
testcase_49	AC	807 ms 27,104 KB
testcase_50	AC	806 ms 27,084 KB
testcase_51	AC	781 ms 27,824 KB
testcase_52	AC	746 ms 27,112 KB
testcase_53	AC	756 ms 27,788 KB
testcase_54	AC	745 ms 27,880 KB
testcase_55	AC	750 ms 26,920 KB
testcase_56	AC	779 ms 27,028 KB
testcase_57	AC	753 ms 28,372 KB
testcase_58	AC	759 ms 27,368 KB
testcase_59	AC	755 ms 27,512 KB
testcase_60	AC	738 ms 27,072 KB
testcase_61	AC	742 ms 28,668 KB
testcase_62	AC	768 ms 28,780 KB
testcase_63	AC	2,504 ms 37,776 KB
testcase_64	AC	2 ms 6,940 KB
testcase_65	AC	2 ms 6,940 KB
testcase_66	AC	2 ms 6,940 KB
testcase_67	AC	2,638 ms 30,976 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)


int N;
int P[3001];
int I[3001][3001];
int dp[3001] = {};

int main(){
	int N; cin >> N;
	rep(i,N){ cin >> P[i]; P[i]--; }
	rep(i,N) rep(j,i) if(P[j] > P[i]) I[j][i+1]++;
	for(int l=N; l>=0; l--) for(int r=l+1; r<=N; r++) I[l][r] += I[l+1][r];
	for(int l=N; l>=0; l--) for(int r=l+1; r<=N; r++) I[l][r] += I[l][r-1];

	for(int k=0; k<N; k++){
	    const int n = N-k;
		for(int l=0; l<n; l++){
			dp[l] = 0;
			for(int r=l+1; r<=n; r++){
				dp[l] = max(dp[l], dp[r] + I[l][r]);
			}
		}
		cout << (I[0][N] - dp[0]) << '\n';
	}

	return 0;
}

yukicoder

結果

テストケース

ソースコード