#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int main()
{
    int n;
    cin>>n;
    int a[N];
    for (int i = 0; i < n; i ++ ) cin>>a[i];
    sort(a,a+n);
    int res=0;
    for (int i = 0; i < n; i ++ ) res=res+abs(a[i]-a[n>>1]);
    cout<<res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 1e5+10;
struct duan{
    int l,r;
}a[N];
bool cmp(duan a,duan b){
    return a.l<b.l;
}
int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n; i ++ ) cin>>a[i].l>>a[i].r;
    sort(a,a+n,cmp);
    priority_queue<int,vector<int>,greater<int>> heap;
    for (int i = 0; i < n; i ++ ){
        if(heap.empty()|| a[i].l<=heap.top()) heap.push(a[i].r);
        else{
            heap.pop();
            heap.push(a[i].r);
        }
    }
    cout<<heap.size();
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 1e5+10;
using namespace std;
struct duan{
    int start,end;
}a[N];
bool cmp(duan s1,duan s2)
{
    return s1.end<s2.end;
}
int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n; i ++ ) cin>>a[i].start>>a[i].end;
    sort(a,a+n,cmp);
    int ed=-2e9;
    int res=0;
    for (int i = 0; i < n; i ++ ){
        if(ed<a[i].start) {
            res++;
            ed=a[i].end;
        }

    }
    cout<<res;
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int t[N];
bool cmp(int a,int b){
    return a>b;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]);

    sort(t, t + n,cmp);


    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += t[i] * i;

    printf("%lld\n", res);

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 1e5+10;
using namespace std;
struct duan{
    int start,end;
}a[N];
bool cmp(duan s1,duan s2)
{
    return s1.end<s2.end;
}
int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n; i ++ ) cin>>a[i].start>>a[i].end;
    sort(a,a+n,cmp);
    int ed=-2e9;
    int res=0;
    for (int i = 0; i < n; i ++ ){
        if(ed<a[i].start) {
            res++;
            ed=a[i].end;
        }

    }
    cout<<res;
    return 0;
}

#include<iostream>
#include <queue>

using namespace std;
const int N = 1e5+10;
int a[N];
int main()
{
    priority_queue<int, vector<int>, greater<int>> q;
    int n,x;
    cin>>n;
    int cost=0;
    for(int i=0;i<n;i++) {
        cin>>x;
        q.push(x);
    }
    while(q.size()!=1){
        int small1=q.top();
        q.pop();
        int small2=q.top();
        q.pop();
        int small3=small1+small2;
        cost+=small3;
        q.push(small3);
    }
    cout<<cost;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 5e4+10;
PII a[N];
int totalw[N];
bool cmp(PII a,PII b){
    return a.first+a.second<b.first+b.second;
}
int main()
{
    int n;
    int w,s;
    cin>>n;
    for (int i = 1; i <= n; i ++ ){
        cin>>w>>s;
        a[i].first=w;
        a[i].second=s;
    }
    sort(a+1,a+n+1,cmp);
    int res=-2e9;
    int b[N];
    for (int i = 1; i <= n; i ++ ){
        totalw[i]=totalw[i-1]+a[i].first;//类似前缀和
        b[i]=totalw[i-1]-a[i].second;
        res=max(res,b[i]);
    }
    cout<<res;
    return 0;

}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int map[N][N];
int f[N][N];
    int n,m,res;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dfs(int x,int y){
    if(f[x][y]!=-1) return f[x][y];
    f[x][y]=1;
    for (int i = 0; i <= 3; i ++ ){
        int seex=x+dx[i];
        int seey=y+dy[i];
        if(seex>0&&seex<=n&&seey>0&&seey<=m&&map[x][y]>map[seex][seey]){
            f[x][y]=max(f[x][y],dfs(seex,seey)+1);        
        }
    }
    return f[x][y];
}
int main()
{

    cin>>n>>m;
    memset(f, -1, sizeof f);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin>>map[i][j];
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res=max(res,dfs(i,j));
    cout<<res;
    return 0;
}

#include<iostream>
using namespace std;
const int N = 1e9+7;
int f[1010][1010];

int main()
{
    int n;
    cin>>n;
    for (int i = 0; i <= n; i ++ ) f[i][0]=1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
           { 

            f[i][j] = f[i - 1][j] % N; 
            if (j >= i) 
            f[i][j]=f[i-1][j]%N+f[i][j-i]%N;

           }
    cout<<f[n][n]%N;
    return 0;
}
空间优化
#include<iostream>
using namespace std;
const int N = 1e9+7;
int f[1010];

int main()
{
    int n;
    cin>>n;
    f[0]=1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
           { 

            f[j] = f[j] % N; 
            if (j >= i) 
            f[j]=f[j]%N+f[j-i]%N;

           }
    cout<<f[n]%N;
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);

    for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];

    for (int len = 2; len <= n; len ++ )
        for (int i = 1; i + len - 1 <= n; i ++ )
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for (int k = l; k < r; k ++ )
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

    printf("%d\n", f[1][n]);
    return 0;
}
20230321
#include<iostream>
using namespace std;
int a[310];
int s[310];
int f[310][310];
int main()
{
    int n;
    cin>>n;
    for (int i = 1; i <= n; i ++ ) {
        cin>>a[i];
        s[i]=a[i]+s[i-1];
    }
    for(int len=2;len<=n;len++)
        for (int i = 1; i <= n-len+1; i ++ )
            {

                int j=i+len-1;
                // 右边界需要注意
                f[i][j]=2e9;
                for (int k = i; k < j; k ++ )
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
    cout<<f[1][n];
    return 0;
}