제출 #1213994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213994		minhpk	Group Photo (JOI21_ho_t3)	C++20	64 / 100	5093 ms	5432 KiB

Main

#include <bits/stdc++.h>

using namespace std;
int a;
int z[1000005];
int pos[1000005];

int smol[801][801];
int big[801][801];

int f[1000005];
int bruh=1e18;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         pos[z[i]]=i;
    }

    for (int i=0;i<a;i++){
        for (int j=i+1;j<=a;j++){
             for (int id=i+1;id<j;id++){
                  if (pos[id]<pos[j]){
                      smol[i][j]++;
                  }
             }
        }
    }

    for (int i=a;i>=1;i--){
         for (int j=i;j>=1;j--){
                for (int k=i+1;k<=a;k++){
                     if (pos[k]<pos[j]){
                         big[i][j]++;
                     }
                }
         }
    }

    for (int i=0;i<=a;i++){
         int prefix=0;
         for (int j=i+1;j<=a;j++){
              prefix+=smol[i][j];
              smol[i][j]=prefix;
         }
    }

    for (int i=1;i<=a;i++){
         int prefix=0;
         for (int j=1;j<=i;j++){
              prefix+=big[i][j];
              big[i][j]=prefix;
         }
    }
    for (int i=0;i<=a;i++){
         f[i]=bruh;
    }
    f[0]=0;
    for (int i=1;i<=a;i++){
         for (int j=0;j<i;j++){
              int inversion= big[i][i]-big[i][j];
              inversion+= smol[j][i]-smol[j][j];

              f[i]=min(f[i],f[j]+inversion);
         }
    }
    cout << f[a] << "\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:12:10: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | int bruh=1e18;
      |          ^~~~

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