oj.uz

답안 #419754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
419754 2021-06-07T12:17:45 Z Kerim Group Photo (JOI21_ho_t3) C++17
64 / 100
 5000 ms 752596 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=5002;
int n,arr[N],inv[N][N],dp[N][N],odp[N][N];
int F[N][N],AB[N][N],BA[N][N],par[N][N],G[N][N];
int g(int x,int y){
	if(x>=y)return 0;
	if(~odp[x][y])return odp[x][y];
	return odp[x][y]=g(x,y-1)+par[y][y]-par[x-1][y];
}
int cost(int a,int b,int c){
	return g(a+1,b-1)+F[a][b-1]+(BA[b][b-1]-BA[b][a])+AB[c][b];
}
int rec(int a,int b){
	if(b==n)return cost(a,b,0);
	int &ret=dp[a][b];
	if(~ret)return ret;
	ret=INF;
	for(int i=b+1;i<=n;i++)
		umin(ret,rec(b,i)+cost(a,b,i));
	return ret;
}
int main(){
	//freopen("file.in", "r", stdin);
	memset(dp,-1,sizeof dp);
	memset(odp,-1,sizeof odp);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",arr+i);
	for(int i=2;i<=n;i++)
		for(int j=1;j<i;j++)
			inv[arr[i]][arr[j]]++;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			par[i][j]=par[i-1][j]+inv[j][i];
	for(int z=1;z<=n;z++)
		for(int x=1;x<=n;x++)
			G[x][z]=G[x-1][z]+inv[x][z];
	for(int y=1;y<=n;y++)
		for(int z=y+1;z<=n;z++)
			F[y][z]=F[y][z-1]+G[y][z];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			BA[i][j]=BA[i][j-1]+inv[i][j];
			AB[i][j]=AB[i][j-1]+inv[j][i];
		}
	int ans=INF;
	for(int i=1;i<=n;i++)
		umin(ans,rec(0,i));
	printf("%d\n",ans);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
Main.cpp:45:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  for(int i=1;i<=n;i++)scanf("%d",arr+i);
      |                       ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 196164 KB Output is correct
2 Correct 94 ms 196212 KB Output is correct
3 Correct 88 ms 196180 KB Output is correct
4 Correct 97 ms 196292 KB Output is correct
5 Correct 85 ms 196328 KB Output is correct
6 Correct 92 ms 196324 KB Output is correct
7 Correct 88 ms 196312 KB Output is correct
8 Correct 93 ms 196288 KB Output is correct
9 Correct 86 ms 196356 KB Output is correct
10 Correct 86 ms 196268 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 196164 KB Output is correct
2 Correct 94 ms 196212 KB Output is correct
3 Correct 88 ms 196180 KB Output is correct
4 Correct 97 ms 196292 KB Output is correct
5 Correct 85 ms 196328 KB Output is correct
6 Correct 92 ms 196324 KB Output is correct
7 Correct 88 ms 196312 KB Output is correct
8 Correct 93 ms 196288 KB Output is correct
9 Correct 86 ms 196356 KB Output is correct
10 Correct 86 ms 196268 KB Output is correct
11 Correct 87 ms 196552 KB Output is correct
12 Correct 85 ms 196516 KB Output is correct
13 Correct 86 ms 196548 KB Output is correct
14 Correct 85 ms 196632 KB Output is correct
15 Correct 89 ms 196572 KB Output is correct
16 Correct 84 ms 196540 KB Output is correct
17 Correct 85 ms 196636 KB Output is correct
18 Correct 91 ms 196548 KB Output is correct
19 Correct 87 ms 196616 KB Output is correct
20 Correct 87 ms 196580 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 196164 KB Output is correct
2 Correct 94 ms 196212 KB Output is correct
3 Correct 88 ms 196180 KB Output is correct
4 Correct 97 ms 196292 KB Output is correct
5 Correct 85 ms 196328 KB Output is correct
6 Correct 92 ms 196324 KB Output is correct
7 Correct 88 ms 196312 KB Output is correct
8 Correct 93 ms 196288 KB Output is correct
9 Correct 86 ms 196356 KB Output is correct
10 Correct 86 ms 196268 KB Output is correct
11 Correct 87 ms 196552 KB Output is correct
12 Correct 85 ms 196516 KB Output is correct
13 Correct 86 ms 196548 KB Output is correct
14 Correct 85 ms 196632 KB Output is correct
15 Correct 89 ms 196572 KB Output is correct
16 Correct 84 ms 196540 KB Output is correct
17 Correct 85 ms 196636 KB Output is correct
18 Correct 91 ms 196548 KB Output is correct
19 Correct 87 ms 196616 KB Output is correct
20 Correct 87 ms 196580 KB Output is correct
21 Correct 109 ms 201796 KB Output is correct
22 Correct 107 ms 201808 KB Output is correct
23 Correct 108 ms 201804 KB Output is correct
24 Correct 107 ms 201844 KB Output is correct
25 Correct 106 ms 201824 KB Output is correct
26 Correct 106 ms 201852 KB Output is correct
27 Correct 107 ms 201844 KB Output is correct
28 Correct 113 ms 201836 KB Output is correct
29 Correct 110 ms 201868 KB Output is correct
30 Correct 113 ms 201836 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 196164 KB Output is correct
2 Correct 94 ms 196212 KB Output is correct
3 Correct 88 ms 196180 KB Output is correct
4 Correct 97 ms 196292 KB Output is correct
5 Correct 85 ms 196328 KB Output is correct
6 Correct 92 ms 196324 KB Output is correct
7 Correct 88 ms 196312 KB Output is correct
8 Correct 93 ms 196288 KB Output is correct
9 Correct 86 ms 196356 KB Output is correct
10 Correct 86 ms 196268 KB Output is correct
11 Correct 87 ms 196552 KB Output is correct
12 Correct 85 ms 196516 KB Output is correct
13 Correct 86 ms 196548 KB Output is correct
14 Correct 85 ms 196632 KB Output is correct
15 Correct 89 ms 196572 KB Output is correct
16 Correct 84 ms 196540 KB Output is correct
17 Correct 85 ms 196636 KB Output is correct
18 Correct 91 ms 196548 KB Output is correct
19 Correct 87 ms 196616 KB Output is correct
20 Correct 87 ms 196580 KB Output is correct
21 Correct 109 ms 201796 KB Output is correct
22 Correct 107 ms 201808 KB Output is correct
23 Correct 108 ms 201804 KB Output is correct
24 Correct 107 ms 201844 KB Output is correct
25 Correct 106 ms 201824 KB Output is correct
26 Correct 106 ms 201852 KB Output is correct
27 Correct 107 ms 201844 KB Output is correct
28 Correct 113 ms 201836 KB Output is correct
29 Correct 110 ms 201868 KB Output is correct
30 Correct 113 ms 201836 KB Output is correct
31 Correct 1141 ms 229136 KB Output is correct
32 Correct 1231 ms 229236 KB Output is correct
33 Correct 1177 ms 229212 KB Output is correct
34 Correct 1197 ms 229312 KB Output is correct
35 Correct 1219 ms 229280 KB Output is correct
36 Correct 1278 ms 229288 KB Output is correct
37 Correct 1174 ms 229208 KB Output is correct
38 Correct 1247 ms 229268 KB Output is correct
39 Correct 1230 ms 229324 KB Output is correct
40 Correct 1182 ms 229260 KB Output is correct

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 196164 KB Output is correct
2 Correct 94 ms 196212 KB Output is correct
3 Correct 88 ms 196180 KB Output is correct
4 Correct 97 ms 196292 KB Output is correct
5 Correct 85 ms 196328 KB Output is correct
6 Correct 92 ms 196324 KB Output is correct
7 Correct 88 ms 196312 KB Output is correct
8 Correct 93 ms 196288 KB Output is correct
9 Correct 86 ms 196356 KB Output is correct
10 Correct 86 ms 196268 KB Output is correct
11 Correct 87 ms 196552 KB Output is correct
12 Correct 85 ms 196516 KB Output is correct
13 Correct 86 ms 196548 KB Output is correct
14 Correct 85 ms 196632 KB Output is correct
15 Correct 89 ms 196572 KB Output is correct
16 Correct 84 ms 196540 KB Output is correct
17 Correct 85 ms 196636 KB Output is correct
18 Correct 91 ms 196548 KB Output is correct
19 Correct 87 ms 196616 KB Output is correct
20 Correct 87 ms 196580 KB Output is correct
21 Correct 109 ms 201796 KB Output is correct
22 Correct 107 ms 201808 KB Output is correct
23 Correct 108 ms 201804 KB Output is correct
24 Correct 107 ms 201844 KB Output is correct
25 Correct 106 ms 201824 KB Output is correct
26 Correct 106 ms 201852 KB Output is correct
27 Correct 107 ms 201844 KB Output is correct
28 Correct 113 ms 201836 KB Output is correct
29 Correct 110 ms 201868 KB Output is correct
30 Correct 113 ms 201836 KB Output is correct
31 Correct 1141 ms 229136 KB Output is correct
32 Correct 1231 ms 229236 KB Output is correct
33 Correct 1177 ms 229212 KB Output is correct
34 Correct 1197 ms 229312 KB Output is correct
35 Correct 1219 ms 229280 KB Output is correct
36 Correct 1278 ms 229288 KB Output is correct
37 Correct 1174 ms 229208 KB Output is correct
38 Correct 1247 ms 229268 KB Output is correct
39 Correct 1230 ms 229324 KB Output is correct
40 Correct 1182 ms 229260 KB Output is correct
41 Execution timed out 5090 ms 752596 KB Time limit exceeded
42 Halted 0 ms 0 KB -