답안 #917361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917361	2024-01-28T02:29:26 Z	Cookie	Group Photo (JOI21_ho_t3)	C++14	100 / 100	261 ms	134828 KB

Main

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7;
const int mxn = 1e6 + 69, mxq = 1e5 + 5, sq = 500, mxv = 1e6 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int x[9] = {0, 1, 1, -1, -1, 2, -2, 2, -2};
//const inty[9] = {0, 2, -2, 2, -2, 1, 1, -1, -1};

int n;
int dp[5005], a[5005], toa[5005], inv[5005][5005], inv2[5005][5005];
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i]; toa[a[i]] = i;
    }
    for(int i = n - 1; i >= 1; i--){
        for(int j = i + 1; j <= n; j++){
            inv[i][j] = inv[i + 1][j] + inv[i][j - 1] - inv[i + 1][j - 1] + (toa[i] < toa[j]);
            inv2[i][j] = inv2[i + 1][j] + inv2[i][j - 1] - inv2[i + 1][j - 1] + (toa[i] > toa[j]);
        }
    }
    for(int i = 1; i <= n; i++){
        dp[i] = inf;

        for(int j = i; j >= 1; j--){
            
            int cost = inv[j][i] + inv2[1][i] - inv2[1][j - 1] - inv2[j][i];
            dp[i] = min(dp[i], dp[j - 1] + cost);
        }
        //cout << dp[i] << " ";
    }
    cout << dp[n];
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("COLLEGE.INP", "r", stdin);
    //freopen("COLLEGE.OUT", "w", stdout);

    int tt; tt = 1;
    while(tt--){
        solve();

    }
    return(0);
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	856 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct

Subtask #3
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	856 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	1 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	2 ms	2140 KB	Output is correct
26	Correct	1 ms	2136 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	1 ms	2140 KB	Output is correct
29	Correct	1 ms	2140 KB	Output is correct
30	Correct	1 ms	2140 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	856 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	1 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	2 ms	2140 KB	Output is correct
26	Correct	1 ms	2136 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	1 ms	2140 KB	Output is correct
29	Correct	1 ms	2140 KB	Output is correct
30	Correct	1 ms	2140 KB	Output is correct
31	Correct	6 ms	9308 KB	Output is correct
32	Correct	6 ms	9280 KB	Output is correct
33	Correct	6 ms	9228 KB	Output is correct
34	Correct	6 ms	9308 KB	Output is correct
35	Correct	9 ms	9304 KB	Output is correct
36	Correct	6 ms	9308 KB	Output is correct
37	Correct	6 ms	9188 KB	Output is correct
38	Correct	6 ms	9312 KB	Output is correct
39	Correct	6 ms	9312 KB	Output is correct
40	Correct	7 ms	9364 KB	Output is correct

Subtask #5
36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	856 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	1 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	2 ms	2140 KB	Output is correct
26	Correct	1 ms	2136 KB	Output is correct
27	Correct	1 ms	2140 KB	Output is correct
28	Correct	1 ms	2140 KB	Output is correct
29	Correct	1 ms	2140 KB	Output is correct
30	Correct	1 ms	2140 KB	Output is correct
31	Correct	6 ms	9308 KB	Output is correct
32	Correct	6 ms	9280 KB	Output is correct
33	Correct	6 ms	9228 KB	Output is correct
34	Correct	6 ms	9308 KB	Output is correct
35	Correct	9 ms	9304 KB	Output is correct
36	Correct	6 ms	9308 KB	Output is correct
37	Correct	6 ms	9188 KB	Output is correct
38	Correct	6 ms	9312 KB	Output is correct
39	Correct	6 ms	9312 KB	Output is correct
40	Correct	7 ms	9364 KB	Output is correct
41	Correct	258 ms	134352 KB	Output is correct
42	Correct	255 ms	134388 KB	Output is correct
43	Correct	259 ms	134828 KB	Output is correct
44	Correct	254 ms	134388 KB	Output is correct
45	Correct	258 ms	134428 KB	Output is correct
46	Correct	257 ms	134472 KB	Output is correct
47	Correct	258 ms	134368 KB	Output is correct
48	Correct	257 ms	134584 KB	Output is correct
49	Correct	257 ms	134228 KB	Output is correct
50	Correct	260 ms	134484 KB	Output is correct
51	Correct	255 ms	134224 KB	Output is correct
52	Correct	255 ms	134464 KB	Output is correct
53	Correct	257 ms	134228 KB	Output is correct
54	Correct	250 ms	134228 KB	Output is correct
55	Correct	261 ms	134224 KB	Output is correct

답안 #917361

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 32.0 / 32.0

Subtask #4 20.0 / 20.0

Subtask #5 36.0 / 36.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
32.0 / 32.0

Subtask #4
20.0 / 20.0

Subtask #5
36.0 / 36.0