답안 #957257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957257	2024-04-03T10:28:14 Z	shadow_sami	Group Photo (JOI21_ho_t3)	C++17	100 / 100	771 ms	312976 KB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
// typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e3+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
ll a[mx];
ll dp[mx];
ll pd[mx][mx];
ll gett[mx][mx];
ll pref[mx];
ll to[mx];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n;
        fip(1,n+1){
        	cin>>a[i];
        	to[a[i]] = i;
        }
        fip(1,n+1){
        	for(ll j = 1 ; j + i - 1 <= n ; j++){
        		tp = j + i - 1;
        		pd[j][tp] = pd[j][tp-1] + pd[j+1][tp] - pd[j+1][tp-1] + (to[j] < to[tp]);
        	}
        }
        fin(n,1){
        	fjp(0,n+2)
        		pref[j] = 0;
        	fjp(i+1,n+1)
        		pref[to[j]]++;
        	fjp(1,n+1)
        		pref[j] += pref[j-1];
        	fjn(i,1){
        		gett[j][i] = pref[to[j]-1];
        		gett[j][i] += gett[j+1][i];        		
        	}
        	fjn(i,1)
        		gett[j][i] += pd[j][i];
        }  
        fip(0,n+2)
        	dp[i] = 1e18;
        dp[0] = 0;
        fip(1,n+1){
        	fjn(i-1,0){
        		dp[i] = min(dp[i],dp[j]+gett[j+1][i]);
        	}
        }
        cout<<dp[n]<<nli;
        
    cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 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	1 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	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 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	1 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	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	1 ms	600 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	856 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	1 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	1 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	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	1 ms	600 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	856 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	2 ms	7768 KB	Output is correct
22	Correct	2 ms	7772 KB	Output is correct
23	Correct	2 ms	7772 KB	Output is correct
24	Correct	2 ms	7772 KB	Output is correct
25	Correct	2 ms	7772 KB	Output is correct
26	Correct	2 ms	7772 KB	Output is correct
27	Correct	2 ms	7772 KB	Output is correct
28	Correct	3 ms	7772 KB	Output is correct
29	Correct	2 ms	7772 KB	Output is correct
30	Correct	2 ms	7772 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 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	1 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	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	1 ms	600 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	856 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	2 ms	7768 KB	Output is correct
22	Correct	2 ms	7772 KB	Output is correct
23	Correct	2 ms	7772 KB	Output is correct
24	Correct	2 ms	7772 KB	Output is correct
25	Correct	2 ms	7772 KB	Output is correct
26	Correct	2 ms	7772 KB	Output is correct
27	Correct	2 ms	7772 KB	Output is correct
28	Correct	3 ms	7772 KB	Output is correct
29	Correct	2 ms	7772 KB	Output is correct
30	Correct	2 ms	7772 KB	Output is correct
31	Correct	12 ms	37060 KB	Output is correct
32	Correct	11 ms	37080 KB	Output is correct
33	Correct	12 ms	36956 KB	Output is correct
34	Correct	11 ms	36956 KB	Output is correct
35	Correct	11 ms	36956 KB	Output is correct
36	Correct	12 ms	37036 KB	Output is correct
37	Correct	11 ms	36956 KB	Output is correct
38	Correct	11 ms	36952 KB	Output is correct
39	Correct	12 ms	37088 KB	Output is correct
40	Correct	13 ms	37092 KB	Output is correct

Subtask #5
36.0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 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	1 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	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	1 ms	600 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	856 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	2 ms	7768 KB	Output is correct
22	Correct	2 ms	7772 KB	Output is correct
23	Correct	2 ms	7772 KB	Output is correct
24	Correct	2 ms	7772 KB	Output is correct
25	Correct	2 ms	7772 KB	Output is correct
26	Correct	2 ms	7772 KB	Output is correct
27	Correct	2 ms	7772 KB	Output is correct
28	Correct	3 ms	7772 KB	Output is correct
29	Correct	2 ms	7772 KB	Output is correct
30	Correct	2 ms	7772 KB	Output is correct
31	Correct	12 ms	37060 KB	Output is correct
32	Correct	11 ms	37080 KB	Output is correct
33	Correct	12 ms	36956 KB	Output is correct
34	Correct	11 ms	36956 KB	Output is correct
35	Correct	11 ms	36956 KB	Output is correct
36	Correct	12 ms	37036 KB	Output is correct
37	Correct	11 ms	36956 KB	Output is correct
38	Correct	11 ms	36952 KB	Output is correct
39	Correct	12 ms	37088 KB	Output is correct
40	Correct	13 ms	37092 KB	Output is correct
41	Correct	771 ms	312520 KB	Output is correct
42	Correct	685 ms	312640 KB	Output is correct
43	Correct	695 ms	312656 KB	Output is correct
44	Correct	704 ms	312688 KB	Output is correct
45	Correct	712 ms	312592 KB	Output is correct
46	Correct	705 ms	312724 KB	Output is correct
47	Correct	696 ms	312896 KB	Output is correct
48	Correct	695 ms	312728 KB	Output is correct
49	Correct	696 ms	312656 KB	Output is correct
50	Correct	697 ms	312492 KB	Output is correct
51	Correct	694 ms	312904 KB	Output is correct
52	Correct	697 ms	312668 KB	Output is correct
53	Correct	700 ms	312976 KB	Output is correct
54	Correct	720 ms	312660 KB	Output is correct
55	Correct	692 ms	312656 KB	Output is correct

답안 #957257

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