Submission #858889

#	Time	Username	Problem	Language	Result	Execution time	Memory
858889		Vladth11	Group Photo (JOI21_ho_t3)	C++14	100 / 100	199 ms	196436 KiB

Main

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 5002;
const ll INF = (1LL << 60);
const ll nrbits = 20;
const int MOD = 998244353;
const int bucket = 320;

int mici[NMAX][NMAX];
int v[NMAX];
int dp[NMAX];
int st[NMAX][NMAX];

int main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> v[i];
    }
    for(i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            mici[v[i]][v[j]]++;
        }
        for(int j = 1; j <= i; j++){
            st[v[i]][v[j]]++;
        }
        for(int j = 1; j <= n; j++){
            st[v[i]][j] += st[v[i]][j - 1];
            mici[v[i]][j] += mici[v[i]][j - 1];
        }
    }
    for(int i = n; i >= 1; i--) dp[i] = 1e9;
    for(int i = n; i >= 1; i--){
        int sum = 0;
        for(int j = i; j <= n; j++){
            int nou = j;
            sum += (mici[nou][i - 1] + st[nou][nou - 1] - st[nou][i - 1]);
            dp[i] = min(dp[i], dp[j + 1] + sum);
        }
    }
    cout << dp[1];
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36