Submission #412993

#	Time	Username	Problem	Language	Result	Execution time	Memory
412993		FerThugGato12500	Group Photo (JOI21_ho_t3)	C++11	64 / 100	5047 ms	139800 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int lmt  = 5005;    
const long long MOD = 1000000007;

#define f first 
#define S second
#define ll long long
#define ld long double
#define ull unsigned long long
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define for1(i, n) for(int i = 1; i < int(n); i++)
#define forv(i,a,n) for(int i = int(a); i < int(n); i++)
#define rof(i, n) for(int i = int(n); i >= 0; i--)
#define rofv(i,a,n) for(int i = int(n); i >= int(a); i--)
#define pb push_back
#define ins insert
#define pai pair<int, int>
#define pal pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define vld vector<long double>
int dp[lmt];
int n, p[lmt];
/*
struct wer{
    int a, b;
};
bool operator < (const wer &a, const wer &b){
    return a.a < b.a;
}*/
vi a[lmt];
int precalc[lmt][lmt];
int buc[lmt][lmt];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for1(i, n+1){
        cin>>p[i];
    }
    for1(i,n+1){
        for1(j,n+1){
            if(p[j]>=i){
                buc[i][p[j]] = a[i].size();
                a[i].pb(p[j]);
            }
        }
    }
    for1(i,n+1){
        int j = i;
        int D = 0;
        vi r;
        while(j<=n){
            D += buc[i][j];
            for(int g = 0; g < r.size(); g++){
                if(r[g]>buc[i][j]){
                    D--;
                }
            }
            precalc[i][j] = D;
            r.pb(buc[i][j]);
            j++;
        }
    }
    memset(dp, 1, sizeof(dp));
    dp[n+1]=0;
    for(int i = n; i > 0; i--){
        for(int j = i; j <= n; j++){
            dp[i] = min(dp[i], precalc[i][j] + dp[j+1]);
        }
    }
    cout<<dp[1];
    return 0;

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(int g = 0; g < r.size(); g++){
      |                            ~~^~~~~~~~~~

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