akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) (S & (-S))
#define ll long long
#define two pair<int,int>
#define four pair<two,two>
#define pb push_back
#define mk make_pair
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
vector<int>visited(100003);
vector<int>ans;
int n,fix[100003];
int m;
int a,b;
int pas[100003];
vector<int>adj[100004];
void dfs(int v) {
    visited[v] = true;
    for (int i=0;i<adj[v].size();i++) {
    	int u=adj[v][i];
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
    reverse(ans.begin(), ans.end());
}
void go(int sad,int parent=0){
	fix[sad]=1;
	for(int i=0;i<(int)adj[sad].size();i++){
		if(fix[adj[sad][i]]==1)continue;
		pas[sad]=parent;
		go(adj[sad][i],sad);
	}
}
set<int>s[100003];
set<int>::iterator it;
int main(){std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n+m-1;i++){
	cin>>a>>b;
	a--;b--;
	adj[a].pb(b);
	s[a].insert(b);
}
topological_sort();
/*for(int i=0;i<ans.size();i++){
	cout<<ans[i]<<" ";
}*/
for(int o=0;o<n;o++){
	int i=ans[o];
	for(it=s[i].begin();it!=s[i].end();it++){
		if(fix[(*it)]==0){
			pas[(*it)]=i+1;
		}
	}
}
for(int i=0;i<n;i++){
	cout<<pas[i]<<endl;
}
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/





Measured memory_bytes: 17916
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size() 

ll power(ll x,ll y,ll p) 
{ 
    ll res = 1;      
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 
const ll MD=1e9+7;
vector<ll>v;
ll f[200005];
ll C(ll N,ll K)
{
	if(N<K)
		return 0;

	ll deno=(f[K]*f[N-K])%MD;
	ll num=f[N];

	ll invdeno=power(deno,MD-2,MD);

	return (num*invdeno)%MD;
}

int main()
{
    ios_base::sync_with_stdio(false);
	ll n,i,j,k,x,y,t,m;

	cin >> n >> k;

	f[0]=1;
	for(i=1;i<=n+5;i++)
		f[i]=(f[i-1]*i)%MD;

	for(i=0;i<n;i++)
	{
		cin >> x;
		v.pb(x);
	}
	sort(all(v));

	// cout<<C(5,3)<<endl;

	ll ans=0;
	for(i=0;i<n;i++)
	{
		ans=(ans-(v[i]*C(n-1-i,k-1))%MD+MD)%MD;
		ans=(ans+(v[i]*C(i,k-1))%MD)%MD;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;

int main(){
  string N,m;
  cin >> N;
  int x,y = 0;
  for(int i = 0; i < int(N.size()); i++){
    istringstream n;
    m = N[i];
  	n = istringstream(m);
  	n >> x;
    y += x;
  }
  if (stoi(N) % y == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3624
#include <stdio.h>
 
int main() {
  int a[101][101] = {0};
  int b[101] = {0};
  int d[101] = {0};
  int i,j,r,c;
  int x;
  int e = 0;
 
  scanf("%d %d" , &r,&c);
 
  for(j=0; j<r; j++) {
    for(i=0; i<c; i++) {
      scanf("%d",&x);
      a[j][i] = x;
    }
  }
 
  for(j=0; j<r; j++){
    for(i=0; i<c; i++) {
      b[i] += a[j][i];
    }
  }
 
  for(j=0; j<r; j++){
    for(i=0; i<c; i++){
      d[j] += a[j][i];
    }
  }
 
  for(j=0; j<r; j++) {
    for(i=0; i<c; i++) {
      printf("%d ",a[j][i]);
    }
    printf("%d\n", d[j]);
  }
  for(i =0; i<c; i++) {
    printf("%d " ,b[i]);
    e += b[i];
  }
  printf("%d\n", e);
 
  return 0;
}


Measured memory_bytes: 2144
/*
sonu_verma1
*/
#include <bits/stdc++.h>
// For policy based data structure
/*#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> */
using namespace std;
/*using namespace __gnu_pbds; 
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set;*/
 
#define MD 1000000007
#define X first
#define Y second
#define pb push_back
#define debug(val, ch) cout <<val <<ch
#define FOR(i, st, en, ch) for(register int i = (st); i <= (en) ; i += (ch))
#define RFOR(i, st, en, ch) for(register int i = (st); i >= (en) ; i -= (ch))
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
 
typedef long long int ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
typedef pair<bool, int> pbi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
/*********************************************************************/
void test(int r)
{
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int sm=0;
	sm+=min(a,k);
	k=max(0,k-a);
	// sm+=min(b,k);
	k=max(0,k-b);
	sm-=min(c,k);
	cout<<sm;

}
/***********************************************************************/
int main()
{
	fast();
    int t=1,r;
    // cin>>t;
    for(r=1;r<=t;r++)
        test(r);
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

void solve() {
    int m, k;
    cin >> m >> k;
    if (k >= ((1 << m))) {
        cout << "-1" << endl;
        return;
    }
    if (m == 1) {
        if (k == 1) cout << "-1" << endl;
        else cout << "0 0 1 1" << endl;
    }
    else {
        fori (i, 0, (1 << m)) {
            if (i != k) cout << i << " ";
        }
        cout << k << " ";
        ford (i, (1 << m) - 1, 0) {
            if (i != k) cout << i << " ";
        }
        cout << k << " ";
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}



Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int top, S[1000];

void push(int x) {
  top++;
  S[top] = x;
}

int pop() {
  top--;
  return S[top+1];
}

int main() {
  int a, b;
  top = 0;

  char s[100];

  while( scanf("%s", s) != EOF) {
    if (s[0] == '+' ) {
      a = pop();
      b = pop();
      push(a + b);
    }

    else if (s[0] == '-' ) {
      b = pop();
      a = pop();
      push(a - b);
    }

    else if (s[0] == '*' ) {
      a = pop();
      b = pop();
      push(a * b);
    }

    else {
      push(atoi(s));
    }
  }

  printf("%d\n", pop());

  return 0;

}

Measured memory_bytes: 980
#include <stdio.h>

int main(void)
{
  int n,w,h,x,y,s,t,i,j,k,l,sum,max;

  for(;;){
    scanf("%d", &n);
    if(n==0) break;

    int per[100][100]={0};
    sum=0;
    max=0;
    scanf("%d %d", &w, &h);
    for(i=0;i<n;i++){
      scanf("%d %d", &x, &y);
      per[x-1][y-1]=1;
    }
    scanf("%d %d", &s, &t);
    for(i=0;i+t-1<h;i++){
      for(j=0;j+s-1<w;j++){
	for(k=i;k<t+i;k++){
	  for(l=j;l<s+j;l++){
	    if(per[l][k]==1) sum++;
	  }
	}
	if(sum>max) max=sum;
	sum=0;
      }
    }
    printf("%d\n", max);
  }

  return 0;
}


Measured memory_bytes: 648
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(2e4) + 17;

int n;
int a[100][100];
ll cost[1 << 17], dp[1 << 17];

bool read() {
    if (!(cin >> n))
        return false;

    forn (i, n)
        forn (j, n)
            cin >> a[i][j];

    return true;
}

void solve() {
    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i)
            if ((mask >> i) & 1)
                for (int j = i + 1; j < n; ++j)
                    if ((mask >> j) & 1)
                        cost[mask] += a[i][j];

        dp[mask] = cost[mask];

        for (int smask = mask; smask > 0; smask = ((smask - 1) & mask))
            dp[mask] = max(dp[mask], dp[mask ^ smask] + cost[smask]);
    }

    cout << dp[(1 << n) - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif
    
    while (read())
        solve();
    
    return 0;
}



Measured memory_bytes: 1280
N = int(input())
x = [None] * N
y = [None] * N
h = [None] * N

for i in range(N):
    x[i], y[i], h[i] = map(int, input().split())    

def height(i, j, xn, yn, hn):
    return abs(j - xn) + abs(i - yn) + hn

def check(i, j, x, y, h, H):
    N = len(x)
    for n in range(N):
        if h[n] > 0:
            if height(i, j, x[n], y[n], h[n]) != H:
                return False
        else:
            if H - abs(j - x[n]) - abs(i - y[n]) > 0:
                return False
    return True


ok = False
for i in range(101):
    for j in range(101):
        for n in range(N):
            if h[n] > 0:
                H = height(i, j, x[n], y[n], h[n])
                ok = check(i, j, x, y, h, H)
                break
            if ok:
                break
        if ok:
            break
    if ok:
        break

print(j, i, H)


Measured memory_bytes: 3064
// file creato da gio il 2020-08-08 14:32:07.892729

#include <bits/stdc++.h>
#define FAST 

#ifdef FAST
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#define MOD 1000000007
#define S second
#define F first
#define PB push_back
#define ll long long
using namespace std;

int main(){
	//freopen("output","w",stdout);
	//freopen("input","r",stdin);
#ifdef FAST
	ios::sync_with_stdio(0);
  	cin.tie(0);
#endif

	ll n,d;
	cin >> n>>d;
    ll r=0;
    for(int i=0;i<n;i++){
        ll a,b;
        cin >>a>>b;
        r+=d*d>=(a*a+b*b);
    }
    cout <<r<<endl;


}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
    vector<int> dp(n,INT_MAX);
    dp[0]=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<=i+k;j++){
			if(j<n)
			 dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
		}
	}
	cout<<dp[n-1]<<" ";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(pos,mp) for(ll pos=mp.begin();pos!=mp.end();pos -++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;

int main(){
    string s, t;
    cin >> s >> t;

    vector<vector<ll>> vec(26);
    rep(i, s.size()){
        vec[s[i]-'a'].push_back(i+1);
    }

    ll ans = 0;
    ll pos = -1;
    for(char c : t){
        if(vec[c-'a'].empty()){
            cout << -1 << endl;
            return 0;
        }

        auto itr = upper_bound(ALL(vec[c-'a']), pos);
        if(itr == vec[c-'a'].end()){
            ans += s.size();
            pos = vec[c-'a'].front();
        }
        else pos = *itr;
    }
    
    cout << ans + pos;
}


Measured memory_bytes: 4628
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int i,a,b;
char logg[200];

int main(){
	while(scanf("%s",logg)!=EOF){
		if(logg[0]=='0')break;
		a=0;b=0;
		for(i=1;i<strlen(logg);i++){
			if(logg[i]=='A')a++;
			if(logg[i]=='B')b++;
		}
		if(a>b)a++; else b++;
		printf("%d %d\n",a,b);
	}
	return 0;
}

Measured memory_bytes: 536
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
////////////////////////////

int main(){fastio
    ll h;cin>>h;
    ll ans=0;
    ll c=1;
    while(h>0){
        ans+=c;
        h/=2;
        c*=2;
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <cctype>
#include <algorithm>
using namespace std;

int expr();
int term();
int fact();

char *p;
char inp[101];

int main(){
    int n;
    cin >> n;
    cin.ignore();
    while (n--){
	cin.getline(inp, sizeof(inp));
	p = inp;
	cout << expr() << endl;
    }
}

int expr(){
    int m = 0;
    m = term();
    while (*p == '+' || *p == '-'){
	if (*p == '+')
	    p++, m += term();
	else if (*p == '-')
	    p++, m -= term();
    }
    return m;
}

int term(){
    int m = 0;
    m = fact();
    while (*p == '*' || *p == '/'){
	if (*p == '*')
	    p++, m *= fact();
	else if (*p == '/')
	    p++, m /= fact();
    }
    return m;
}

int fact(){
    int m = 0;
    if (*p == '('){
	p++;
	m = expr();
	p++;
	return m;
    }
    else {
	while ('0' <= *p && *p <= '9'){
	    m *= 10;
	    m += *p - '0';
	    p++;
	}
    }
    return m;
}

Measured memory_bytes: 0
#include<math.h>
int isprime(int);

int main(){
  int x,n[10000],i,count=0;
  scanf("%d",&x);
  for(i=0;i<x;i++){
    scanf("%d",&n[i]);
  }
  for(i=0;i<x;i++){
    if(isprime(n[i])==1)
      count++;
  }
  printf("%d\n",count);
  return 0;
}

int isprime(int x)
{
  int i;
  if(x==2) return 1;
  if(x<2 || x%2==0)
    return 0;
  i=3;
  while(i<=sqrt(x)){
    if(x%i==0)
      return 0;
      i=i+2;
  }
      return 1;
    }

Measured memory_bytes: 632
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}

int is_Prime(int x){
    if(x<2){
        return 0;
    }
    int xx = sqrt(x);
    xx = min(x-1,xx+100);
    for(int i=2;i<=xx;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}

int main(){
    int n;
    cin >> n;
    int ans = 0;
    rep(i,n){
        int a; cin >> a;
        ans += is_Prime(a);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
const int M=3e3+4;
string s,t,ans="";
int dp[M][M],a,b,cnt,vis[M][M];
void fun(int x,int y)
{
	if(x<=0 || y<=0 || cnt<0) return;
	if(s[x]==t[y] && dp[x][y]==cnt)
	{
		ans+=s[x];
		cnt--;
		fun(x-1,y-1);
	}
	else
	{
		if(dp[x][y-1]>dp[x-1][y])
		fun(x,y-1);
		else
		fun(x-1,y);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>s>>t;
	a=s.length();
	b=t.length();
	s=" "+s;
	t=" "+t;
	for(int i=1;i<=a;i++)
	{
		for(int j=1;j<=b;j++)
		{
			if(s[i]==t[j])
			dp[i][j]=max(dp[i][j],1+dp[i-1][j-1]);
			else
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	cnt=dp[a][b];
	fun(a,b);
	reverse(ans.begin(),ans.end());
	cout<<ans;
	return 0;
}

Measured memory_bytes: 35968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (INT_MAX / 4)
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define TIMER_S(start) chrono::system_clock::time_point start = chrono::system_clock::now();
#define TIMER_E(end) chrono::system_clock::time_point end = chrono::system_clock::now();
#define TIME(start, end) cout << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count()) << "ms" \
                              << "\n";

int main()
{
    int n;
    unordered_map<int, int> cnt;
    cin >> n;
    REP(i, n)
    {
        int a;
        cin >> a;
        if (cnt.count(a))
        {
            cout << "NO" << "\n";
            return 0;
        }
        else
        {
            cnt[a] = 0;
        }
    }
    cout << "YES" << "\n";
    return 0;
}


Measured memory_bytes: 8520
S = list(str(input()))
max1 = 0
now_max = 0
for i in S:
    if i == "R":
        max1 += 1
        if now_max < max1:
            now_max = max1
    elif i == "S":
        if now_max < max1:
            now_max = max1
        max1 = 0

print(now_max)

Measured memory_bytes: 61692
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
vector<vector<ll>> t;
vector<ll> v, s;
vector<bool> ok;
void dfs(ll p, ll c ){
    s[p] = c + v[p];
    ok[p] = 1;
    for (auto q : t[p]) {
        if (!ok[q]) dfs(q, c + v[p]);
    }
}
int main() {
    ll n, q;
    cin >> n >> q;
    t.resize(n, vector<ll>(0));
    v.resize(n, 0);
    s.resize(n, 0);
    ok.resize(n, 0);
    ll a, b;
    rep(i, n - 1){
        cin >> a >> b;
        t[a - 1].push_back(b - 1);
        t[b - 1].push_back(a - 1);
    }
    ll p, x;
    rep(i, q) {
        cin >> p >> x;
        v[p - 1] += x;
    }
    //cout << 'a' << endl;
    dfs(0,0);
    rep(i, n) cout << s[i] << endl;
    return 0;
}


Measured memory_bytes: 26760
#include <bits/stdc++.h>
using namespace std;

int main (void) {
    int N, M;
    vector<int> favorite;

    cin >> N >> M;

    favorite.resize(M + 1);
    fill(favorite.begin(), favorite.end(), 0);
    for (int i = 0; i < N; i++) {
        int K;
        cin >> K;
        for (int j = 0; j < K; j++) {
            int A;
            cin >> A;
            favorite[A]++;
        }
    }

    int ans = 0;
    for (int i = 1; i <= M; i++) {
        if (favorite[i] == N) ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,m;
  cin >> n >> m;
  if(n >= m){
    cout << 0 << endl;
    return 0;
  }
  vector<int>data(m);
  vector<int>s(m-1);
  for(int i = 0;i < m;i++){
    cin >> data.at(i);
  }
  sort(data.begin(),data.end());
  for(int i = 0;i < m-1;i++){
    s.at(i) = data.at(i+1)-data.at(i);
  }
  sort(s.begin(),s.end());
  int sum = data.at(m-1)-data.at(0);
  for(int i = 0;i < n-1;i++){
    sum -= s.at(m-2-i);
  }
  cout << sum << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long

void solve()
{
    ll n;
    cin>>n;
    vector<pair<ll,ll>> v;
    for(ll i=0;i<n;i++)
    {
        ll x,y;
        cin>>x>>y;
        v.push_back({x,y});
    }
    ll flag=0;
    for(ll i=0;i<=n-3;i++)
    {
        ll t11=v[i].first;
        ll t12=v[i].second;
        ll t21=v[i+1].first;
        ll t22=v[i+1].second;
        ll t31=v[i+2].first;
        ll t32=v[i+2].second;
        if(t11==t12 && t21==t22 && t31==t32) flag=1;
    }
    if(flag) cout<<"Yes";
    else cout<<"No";
}

int main()
{
    IOS
    ll t=1;
    //cin>>t;
    for(ll i=0;i<t;i++) solve();
    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;

#define rep(i, a, b) for(ll (i) = (a); (i) < (b);++i)

ll gcd(ll x, ll y)
{
  if (x % y == 0)
  {
    return y;
  }
  return gcd(y, x % y);
}

int main()
{
  char A, B;
  cin >> A >> B;
  if (A == 'H' && B == 'H')cout << "H" << endl;
  if (A == 'H' && B == 'D')cout << "D" << endl;
  if (A == 'D' && B == 'H')cout << "D" << endl;
  if (A == 'D' && B == 'D')cout << "H" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<complex>
#include<vector>
using namespace std;
typedef complex < double > P;
typedef vector< P > G;
struct L:public vector< P >{ // L:線分
  L(const P& a,const P& b){push_back(a);push_back(b);}
};
const double EPS = 1e-8;
const double INF = 1e12;
double cross(const P& a,const P& b){
  return imag(conj(a) * b);
}
double dot(const P& a,const P& b){
  return real(conj(a) * b);
}
int ccw(P a,P b,P c){
  b -= a; c -= a;
  if(cross(b,c) > 0) return 1;
  if(cross(b,c) < 0) return -1;
  if(dot(b,c) < 0) return 2; // c--a--b
  if(norm(b) < norm(c)) return -2; // a--b--c
  return 0; // a--c--b
}
bool intersect(const L& s,const L& t){
  return ccw(s[0],s[1],t[0]) * ccw(s[0],s[1],t[1]) <= 0 &&
    ccw(t[0],t[1],s[0]) * ccw(t[0],t[1],s[1]) <= 0;
}
bool isconvex(const G& g){
  return intersect(L(g[0],g[2]),L(g[1],g[3])) && intersect(L(g[1],g[3]),L(g[0],g[2]));
}
int main(){
  double x1,y1,x2,y2,x3,y3,x4,y4;
  char o;
  while(cin >> x1 >> o >> y1 >> o >> x2 >> o >> y2 >> o >> x3 >> o >> y3 >> o >> x4 >> o >> y4){
    G g(4);
    g[0] = P(x1,y1);
    g[1] = P(x2,y2);
    g[2] = P(x3,y3);
    g[3] = P(x4,y4);
    cout << (isconvex(g) ? "YES" : "NO") << endl;
  }
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
int x,mp[10];
int main(){
	for (int i=1;i<=6;i++){
		scanf("%d",&x);
		mp[x]++;
	}int ans=mp[1];
	for (int i=2;i<=4;i++) ans&=mp[i];
	if (ans%2) puts("NO");
	else puts("YES");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, t;
    cin >> n >> t;
    t /= 2;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int mx = 0;
    int ans = 0;
    for (int i = n  - 1; i >= 0; i--) {
        if (mx > a[i]) {
            ans = max(ans, mx - a[i]);
        }
        mx = max(mx, a[i]);
    }
    int res = 0;
    map <int, int> c;
    for (int i = n - 1; i >= 0; i--) {
        c[a[i]]++;
        if (c[a[i] + ans]) {
            res++;
        }
    }
    cout << res << '\n';
    return 0;
}

Measured memory_bytes: 9984
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define SZ(a) int((a).size())
#define _REP(_1,_2,_3,_4,name,...) name
#define _REP4(i,b,e,s) for(decltype(e) _b=(b),_e=(e),i=_b+(0<(s)?0:(s));(0<(s)?i<_e:_e<=i);i+=(s))
#define _REP3(i,b,e) for(decltype(e) _b=(b),_e=(e),i=(_b<_e?_b:_b-1);(_b<_e?i<_e:_e<=i);(_b<_e?i++:i--))
#define _REP2(i,n) for(decltype(n) i=0,_n=(n);i<_n;i++)
#define _REP1(n) for(decltype(n) _i=0,_n=(n);_i<_n;_i++)
#define REP(...) _REP(__VA_ARGS__,_REP4,_REP3,_REP2,_REP1)(__VA_ARGS__)
#define FOR(it,c) for(auto&& it=begin(c);it!=end(c);it++)
#define ROF(it,c) for(auto&& it=rbegin(c);it!=rend(c);it++)
#define PB push_back
#define INT(n) int n;scanf("%d",&n)
#define VI(v,n) vector<int> v(n);REP(i,n){scanf("%d",&v[i]);}
#define MSET(arr,val)  memset(arr,val,sizeof(arr))

int main(){
  INT(N); VI(As, N); sort(As.begin(), As.end());
  vector<LL> v;
  LL s = 0;
  FOR(it, As){
    s += *it;
    v.PB(s);
  }
  int ans = 1;
  REP(i, N - 1, 0){
    if (As[i + 1] <= 2 * v[i]){
      ans++;
    }
    else{
      break;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 1912
#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

int main() {
  while(1) {
    int n,l;
    cin>>n>>l;
    if(!n)break;
    vector<tuple<int, int, int>> ant;
    REP(i,n) {
      string d;
      int p;
      cin>>d>>p;
      ant.emplace_back(p, d=="L" ? -1 : 1, i);
    }
    REP(i,150) {
      REP(j,n) {
        int p,d,k;
        tie(p,d,k) = ant[j];
        p += d;
        ant[j] = make_tuple(p,d,k);
      }
      sort(begin(ant),end(ant));
      REP(j,n-1) {
        auto p1 = ant[j];
        auto p2 = ant[j+1];
        if (get<0>(p1) == get<0>(p2)) {
          swap(get<2>(ant[j]),get<2>(ant[j+1]));
        }
      }
      bool isin = false;
      int isinid = 0;
      int isinp = 10000;
      REP(j,n) {
        int p = get<0>(ant[j]);
        if (0 < p && p < l) {
          isin = true;
        } else if (p == 0 || p == l) {
          if (isinp > p) {
            isinid = get<2>(ant[j]);
            isinp = p;
          }
        }
      }
      if (!isin) {
        cout << i+1 << ' ' << isinid+1 << endl;
        break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
using namespace std;

int main()
{
  string s, t;
  bool flag;

  cin >> s >> t;
  for (int i = 0; i < s.size(); i++)
  {
    flag = true;
    for (int j = i; j < s.size(); j++)
    {
      if (s[j - i] != t[j])
      {
        flag = false;
        break;
      }
    }
    if (!flag)
      continue;
    for (int j = 0; j < i; j++)
    {
      if (s[s.size() - i + j] != t[j])
      {
        flag = false;
        break;
      }
    }
    if (flag)
      break;
  }
  cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

long long N, M, K;
long long res = 0;

// mod. m での a の逆元 a^{-1} を計算する
long long Modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}



long long ModComb(long long n, long long a, long long mod){
  long long i = 0;
  long long res = 1;
  while(a > 0){
    res *= ((n-i) * Modinv(a, MOD)) % MOD;
    res %= MOD;
    --a; ++i;
  }

  return res;
}


int main(){
  cin >> N >> M >> K;

  long long MC = ModComb(N * M - 2, K - 2, MOD);

  for(int d = 1; d < N; d++)
    res = ((d * ((((N-d) * M * M) * MC) % MOD)) % MOD + res) % MOD;

  for(int d = 1; d < M; d++)
    res = ((d * ((((M-d) * N * N) * MC) % MOD)) % MOD + res) % MOD;

  cout << res << endl;
  return 0;

}




    

Measured memory_bytes: 256
import java.util.Scanner;

/**
 *
 * @author ena000078
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int g = sc.nextInt();
        int b = sc.nextInt();
        
        int inputval = r * 100 + g * 10 + b;

        if (inputval % 4 == 0) {
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }        
}

Measured memory_bytes: 21716
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Simultaneous_Equation
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string input = Console.ReadLine();
                if (input == null)
                { break; }

                string[] nums = input.Split(' ');
                double a = double.Parse(nums[0]);
                double b = double.Parse(nums[1]);
                double c = double.Parse(nums[2]);
                double d = double.Parse(nums[3]);
                double e = double.Parse(nums[4]);
                double f = double.Parse(nums[5]);

                double x = (c * e - f * b) / (a * e - b * d);
                double y = (c * d - a * f) / (b * d - a * e);

                Console.Write("{0:0.000}", x);
                Console.Write(" ");
                Console.Write("{0:0.000}", y);
                Console.WriteLine();
            }
        }
    }
}



Measured memory_bytes: 15916
#include <iostream>
#include <math.h>
#include<vector>
#include<cstdio>
#include<string.h>
using namespace std;
#define ll long long
const int N=50+5;

ll a[N];
int main(){
    ios::sync_with_stdio(false);
    ll k,n=50,t,m;
    cin>>k;

    t=k%n;
    m=k/n;
    for(int i=0;i<n;++i){
        if(i<t){
            a[i]=n-1+(m+1)*n-(k-m-1);
        }
        else{
            a[i]=n-1+m*n-(k-m);
        }
    }
    cout<<n<<endl;
    for(int i=0;i<n;++i) cout<<a[i]<<' ';
    cout<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;
#define int long long

int rec(string t){

   int ret=0;
   int n=t.size();
   if(n==0){
      ret=0;
   }else{
      for(int i=1; i<=n; i++){
         if(i==n){
            ret+=stoll(t);
         }else{
            ret+=(1<<(n-i-1))*stoll(t.substr(0, i))+rec(t.substr(i));
         }
      }
   }

   return ret;
}

signed main(){

   string S;
   cin>> S;

   cout<< rec(S)<< endl;

   return 0;
}



Measured memory_bytes: 256
import sys
import numpy as np

n, s, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353

dp = np.zeros(s + 1, np.int64)
dp[0] = 1

for a in aaa:
    ndp = dp * 2 % MOD
    if a <= s:
        ndp[a:] += dp[:-a]
    dp = ndp % MOD

print(dp[s])


Measured memory_bytes: 27464
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;

int main(){
  int n;
  cin>>n;
  if(n==1)cout<<"Hello World"<<endl;
  else {
    int a,b;
    cin>>a>>b;
    cout<<a+b<<endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	int n; int test[31] = { 0 };
	for (int h = 0; h < 28; h++) {
		cin >> n;
		test[n]++;
	}
	for (int h = 1; h <= 30; h++) {
		if (test[h] == 0) {
			cout << h << endl;
		}
	}
	cin >> n;
}


Measured memory_bytes: 3100
#include <map>
#include <set>
#include <unordered_set>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <climits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#define _USE_MATH_DEFINES
#include <math.h>
#include <complex>
#include <atomic>
#include <thread>

using namespace std;
typedef long long ll;
#define ln '\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define drep(i,n) int i = 0;for(;i<(n);++i)
#define FOR(i,s,e) for(int i=s;i<=(e);++i)
#define DFOR(i,s,e) int i = s;for(;i<=(e);++i)
#define FORR(i,s,e) for(int i=s;i>=(e);--i)
#define DFORR(i,s,e) int i = s;for(;i>=(e);--i)
#define fore(a, x) for(auto& a : x)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ft first
#define sd second
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define Fill(a,b) memset(a,b,sizeof(a))
template<typename T1, typename T2> bool Max(T1& a, T2 b) { return a<b ? a = b, 1 : 0; }
template<typename T1, typename T2> bool Min(T1& a, T2 b) { return a>b ? a = b, 1 : 0; }


const int N = 100001, inf=1e9;


void solve() {
  int n, k, v;
  cin >> n >> k;
  map<int, int> mp;
  while (n--) {
    cin >> v;
    mp[v]++;
  }
  vector<int> vec;
  fore(e, mp)vec.push_back(e.sd);
  sort(all(vec));
  if (vec.size() <= k) {
    cout << 0 << ln;
    return;
  }
  vec.resize(vec.size()-k);
  int ans = 0;
  fore(e, vec)ans += e;
  cout << ans << ln;
  
}


void init() {
}

int main(void) {
  ios::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
  //freopen("C:\\Users\\LENOVO\\Documents\\Visual Studio 2015\\Projects\\Test\\Input\\in.in", "r", stdin);

  init();
  int TC = 1;
#if 0
  cin >> TC; cin.get();
#endif
  FOR(TI, 1, TC) {
    //cout << "Case #" << TI << ": ";
    solve();
  }


  return 0;
}

Measured memory_bytes: 10744
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <math.h>

typedef long long int ll;

using namespace std;

int main()
{
    ll  X,P,Q,R,S;
    ll A;
    cin >> X;

    P = X / 100;
    Q = X % 100;

    if(Q==0||X%105==0){
        cout << 1 << endl;
    }
    else{
        R = Q / 5;
        A = X / 105+1;
        if (R + 1 <= P)
        {
            cout << 1 << endl;
        }
        else{
            cout << 0 << endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
using namespace std; 
inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
} 
const int Mod = 924844033, G = 5; 
int fpow(int x, int y) { 
	int res = 1; 
	while (y) { 
		if (y & 1) res = 1ll * res * x % Mod; 
		x = 1ll * x * x % Mod; 
		y >>= 1; 
	} 
	return res; 
} 
const int iG = fpow(G, Mod - 2); 
const int MAX_N = 2e5 + 5; 
int Limit, rev[MAX_N << 2]; 
void FFT_prepare(int len) { 
	int p = 0; 
	for (Limit = 1; Limit <= len; Limit <<= 1) ++p; 
	for (int i = 1; i < Limit; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (p - 1)); 
} 
void NTT(int *p, int op) { 
	for (int i = 1; i < Limit; i++) if (i < rev[i]) swap(p[i], p[rev[i]]); 
	for (int i = 1; i < Limit; i <<= 1) { 
		int rot = fpow(op == 1 ? G : iG, (Mod - 1) / (i << 1)); 
		for (int j = 0; j < Limit; j += i << 1) 
			for (int k = 0, w = 1; k < i; k++, w = 1ll * w * rot % Mod) { 
				int x = p[j + k], y = 1ll * w * p[i + j + k] % Mod; 
				p[j + k] = (x + y) % Mod, p[i + j + k] = (x - y + Mod) % Mod; 
			} 
	} 
	if (!op) { 
		int inv = fpow(Limit, Mod - 2); 
		for (int i = 0; i < Limit; i++) p[i] = 1ll * p[i] * inv % Mod; 
	} 
} 
struct Graph { int to, next; } e[MAX_N << 1]; 
int fir[MAX_N], e_cnt; 
void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; } 
void Add_Edge(int u, int v) { e[e_cnt] = (Graph){v, fir[u]}, fir[u] = e_cnt++; } 
int N, f[MAX_N << 2], g[MAX_N << 2], h[MAX_N << 2];
int siz[MAX_N], cnt[MAX_N]; 
void dfs(int x, int fa) { 
	siz[x] = 1; 
	for (int i = fir[x]; ~i; i = e[i].next) {
		int v = e[i].to; if (v == fa) continue; 
		dfs(v, x), siz[x] += siz[v]; 
		cnt[siz[v]]++; 
	} 
	cnt[N - siz[x]]++; 
} 
int fac[MAX_N], ifc[MAX_N]; 
int C(int n, int m) { 
	if (n < 0 || m < 0 || n < m) return 0; 
	else return 1ll * fac[n] * ifc[n - m] % Mod * ifc[m] % Mod; 
} 
int main () { 
	clearGraph(); 
	N = gi(); 
	for (int i = 1; i < N; i++) { 
		int u = gi(), v = gi(); 
		Add_Edge(u, v), Add_Edge(v, u); 
	} 
	fac[0] = 1; for (int i = 1; i <= N; i++) fac[i] = 1ll * fac[i - 1] * i % Mod; 
	ifc[N] = fpow(fac[N], Mod - 2); 
	for (int i = N - 1; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % Mod;
	dfs(1, 0); 
	for (int i = 1; i <= N; i++) g[i] = 1ll * cnt[i] * fac[i] % Mod; 
	for (int i = 0; i <= N; i++) h[i] = ifc[i]; 
	reverse(&g[0], &g[N + 1]); 
	FFT_prepare(N << 1); 
	NTT(g, 1), NTT(h, 1); 
	for (int i = 0; i < Limit; i++) f[i] = 1ll * g[i] * h[i] % Mod; 
	NTT(f, 0); 
	for (int i = 1; i <= N; i++) { 
		int ans = 1ll * N * C(N, i) % Mod; 
		ans = (ans - 1ll * ifc[i] * f[N - i] % Mod + Mod) % Mod; 
		printf("%d\n", ans); 
	} 
    return 0; 
} 

Measured memory_bytes: 28544
N,L = map(int,(input().split()))
apple = [L+i-1 for i in range(1,N+1)]
apple_sum = sum(apple)
List = []
for i in range(N):
    List.append(abs(apple_sum-sum(apple[:i]+apple[i+1:])))

print(apple_sum-apple[List.index(min(List))])



Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define endl '\n'
using namespace std;


typedef long long ll;
typedef pair<int,int> pii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string a;
	cin >> a >> a;

	cout << "A" << a[0] << "C" << endl;

	return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[]) {
	int n;
	std::cin >> n;
	std::vector<long long> v(5,0);
	string march = "MARCH";
	for (size_t i = 0; i < n; i++) {
		string temp;
		std::cin >> temp;
		for (size_t im = 0; im < march.size(); im++) {
			if (temp[0] == march[im]) {
				v[im]++;
			}
		}
	}


	long long ans = 0;
	for (size_t i = 0; i < v.size(); i++) {
		for (size_t j = i + 1; j < v.size(); j++) {
			for (size_t k = j + 1; k < v.size(); k++) {
				ans = ans + v[i] * v[j] * v[k];
			}
		}
	}

	std::cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int i, j, k, n, array[100];

	scanf("%d", &n);
	for(i = 0; i < n; i++)  scanf("%d", &array[i]);  
	for(i = 0; i < n; i++){
		j = i;
		while(j > 0 && array[j] < array[j-1]){
			k = array[j];
			array[j] = array[j-1];
			array[j-1] = k;
			j--;
		}
		for(j = 0; printf("%d", array[j]), j < n-1; j++)  printf(" ");
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 604
# Bite Eating
N, L = map(int, input().split())

tast = [L+i for i in range(N)]
tast_abs = [t if t>0 else -t for t in tast]
tast_min_idx = sorted(range(len(tast_abs)), key = lambda x : tast_abs[x])
tast_min = tast[tast_min_idx[0]]

tast_sum = sum(tast) - tast_min

print(tast_sum)

Measured memory_bytes: 3064
#include "bits//stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define REP(i,a,n) for(int i = (a); i < (n); i++)
#define ALL(v) v.begin(), v.end()
ll dp[100000][2];
ll A[100000];
int main() {
	int N;
	cin >> N;
	rep(i, N) cin >> A[i];
	fill((ll*)dp, (ll*)(dp + N), -INF);
	dp[1][0] = A[0];
	dp[1][1] = -A[0];
	for (int i = 1; i + 1 < N; i++) {
		dp[i + 1][0] = max(dp[i][0] + A[i], dp[i][1] - A[i]);
		dp[i + 1][1] = max(dp[i][0] - A[i], dp[i][1] + A[i]);
	}
	ll ans = max(dp[N - 1][0] + A[N - 1], dp[N - 1][1] - A[N - 1]);
	cout << ans << endl;
}

Measured memory_bytes: 2560
/*######################################################
#########~~~~~####~~~~###~~##~~##~~##~~##~~##~~#########
#########~~##~~##~~##~~##~~~#~~##~~~#~~##~~##~~#########
#~~~~~~##~~~~~###~~~~~~##~~#~~~##~~#~~~##~~##~~##~~~~~~#
#########~~######~~##~~##~~##~~##~~##~~##~~##~~#########
#########~~######~~##~~##~~##~~##~~##~~###~~~~##########
######################################################*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
#define rtn return
#define endl '\n'
#define F first
#define S second
#define mt make_tuple
#define pb push_back
#define int long long
#define sz(x) (int) x.size()
#define value_at find_by_order
#define index_of order_of_key
#define fill(a, v) memset(a,v,sizeof(a))
#define copy(a, b) memcpy(b,a,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i, n) for(int i=0;i<(int)n;++i)
#define per(i, n) for(int i=(int)n-1;i>=0;--i)
#define rep1(i, n) for(int i=1;i<=(int)n;++i)
#define per1(i, n) for(int i=(int)n;i>=1;--i)
#define loop(i, begin, end) for(int i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " = " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << " |";
  __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef string str;
typedef long double db;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<str> vstr;
typedef vector<db> vdb;

template<class T, class V> void remin(T &a, V b) { a > b ? a = b : a = a; }
template<class T, class V> void remax(T &a, V b) { a < b ? a = b : a = a; }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


const int INF = 1e18;
const db EPS = 1e-15;
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

//

int32_t main() {
  FAST_IO;
  int k, a, b;
  cin >> k >> a >> b;
  for (int i = a; i <= b; i++) {
    if (i % k == 0) {
      cout << "OK";
      rtn 0;
    }
  }
  cout << "NG";
  rtn 0;
}


Measured memory_bytes: 3664
#include <stdio.h>

int main()
{
	int N, L[10];
	scanf("%d", &N);

	int lmax = 0, lmaxindex = -1;
	for(int n=0; n<N; n++){
		scanf("%d", L+n);
		if(L[n] > lmax){
			lmax = L[n];
			lmaxindex = n;
		}
	}

	int rem = 0;
	for(int n=0; n<N; n++){
		if(n != lmaxindex){
			rem += L[n];
		}
	}

	if(lmax < rem){
		printf("Yes\n");
	} else {
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct Edge{int from, to; ll cost;};

const int MAX_N = 200000;

int n;
vector<ll> a(MAX_N), imos(MAX_N+1, 0LL);

ll calc_diff(int start, int mid, int end) {
    if(mid <= start || end <= mid) return LLONG_MAX;
    return abs((imos[end-1] - imos[mid-1]) - (imos[mid-1] - imos[start-1]));
}

ll calc_mid(int start, int end) {
    int ret = lower_bound(imos.begin(), imos.begin()+n+1, (imos[end-1]-imos[start-1])/2 + imos[start-1]) - imos.begin();
    if(calc_diff(start, ret-1, end) < calc_diff(start, ret, end)) { 
        if(calc_diff(start, ret+1, end) < calc_diff(start, ret-1, end)) {
            ret += 1;
        } else {
            ret -= 1;
        }
    } else {
        if(calc_diff(start, ret+1, end) < calc_diff(start, ret, end)) {
            ret += 1;
        }
    }
    return ret;
}

int main(){
    cin >> n;
    rep(n) cin >> a[i];
    rep(n) imos[i+1] = imos[i] + a[i];

    ll diff = LLONG_MAX;
    for(int j=3;j<=n-1;j++) {
        int i = calc_mid(1, j);
        int k = calc_mid(j, n+1);
        ll tmp_max = max({
            imos[i-1], 
            imos[j-1]-imos[i-1], 
            imos[k-1]-imos[j-1], 
            imos[n]-imos[k-1]
        });
        ll tmp_min = min({
            imos[i-1], 
            imos[j-1]-imos[i-1], 
            imos[k-1]-imos[j-1], 
            imos[n]-imos[k-1]
        });
        diff = min(diff, tmp_max-tmp_min);
    }

    cout << diff << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;

ll c(ll a,ll b){
  if(a*b==0)return 1;
  ll res=1;
  rep(i,b){
    res=res*(a-i)/(i+1);
  }
  return res;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  double ok=0,ng=1e16;
  ll n;cin>>n;
  ll a,b;
  cin>>a>>b;
  vector<double>v(n);
  rep(i,n)cin>>v[i];
  auto check=[&](double k){
    auto tv=v;
    rep(i,n)tv[i]-=k;
    sort(all(tv),greater<double>());
    double su=0LL;
    rep(i,a){
      su+=tv[i];
    }
    rep(j,b+1){
      if(tv[j+a]>0)su+=tv[j+a];
    }
    if(su<0)return 0;
    return 1;
  };
  rep(i,100){
    double nn=(ng+ok)/2;
    if(check(nn))ok=nn;
    else ng=nn;
  }

  cout<<fixed<<setprecision(7)<<ok<<endl;
  double e=1e-2;
  auto tv=v;
  rep(i,n)tv[i]-=ok;
  sort(all(tv),greater<double>());
  //ll sum=0;
  if(abs(tv[a-1])<e){
    double d=tv[a-1];
    ll cnt=0,cnt2=0;
    rep(i,n)cnt+=(abs(tv[i]-d)<e);
    rep(i,a)cnt2+=(abs(tv[i]-d)<e);
    ll res=0LL;
    repi(i,cnt2,min(b-a,cnt-cnt2)+cnt2+1)res+=c(cnt,i);
    //cout<<d<<endl;
    //cout<<cnt<<cnt2<<endl;;
    //cout<<(1LL<<50)<<endl;
    cout<<res<<endl;
  }else {
    double d=tv[a-1];
    ll cnt=0,cnt2=0;
    rep(i,n)cnt+=(abs(tv[i]-d)<e);
    rep(i,a)cnt2+=(abs(tv[i]-d)<e);
    ll res=c(cnt,cnt2);
    //repi(i,cnt2,min(b-a,cnt-cnt2)+cnt2+1)res+=c(cnt,i);
    //cout<<d<<endl;
    //cout<<cnt<<cnt2<<endl;;
    //cout<<(1LL<<50)<<endl;
    cout<<res<<endl;

  }



  return 0;

}


Measured memory_bytes: 256
N = int(input())
ratio = [ list(map(int, input().split())) for i in range(N)]


t1 = 1
t2 = 1
for T1, T2 in ratio:
        tmp_a = -( - t1 // T1)
        tmp_b = -( - t2 // T2)
        n = max(tmp_a, tmp_b)
        t1 = n * T1 
        t2 = n * T2
print(t1 + t2)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
const ll MOD = 1000000007;

struct edge{
    int to,weight;
    edge(int to,int weight):to(to),weight(weight){}
};
using Graph = vector<vector<int>> ;
using GraphEdge = vector<vector<int>> ;

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}

bool sor(pair<ll,ll> &a, pair<ll,ll> &b){
    return a.first < b.first;
}
int main(){
    ll N,M;cin >> N >> M;
    const int MAXN = 100001;
    pair<ll,ll> P[MAXN];
    rep(i,N){
        cin >> P[i].first>> P[i].second;
    }

    sort(P,P+N,sor);

    ll count = 0;
    ll price = 0;
    // rep(i,N)cout << P[i].first << " ";
    // cout << endl;
    for(int i=0;i<N;i++){
        if(P[i].second + count <= M){
            count += P[i].second ;
            price += P[i].second * P[i].first;
        }else {
            price += P[i].first * (M-count);
            count = M;
        }
        if(count == M)break;
    }

    cout << price << endl;

    return 0;
}

Measured memory_bytes: 5160
# frozen_string_literal: true

n, m = gets.split(' ').map!(&:to_i)

students = []
n.times do
  students << gets.split(' ').map!(&:to_i)
end

check_points = []
m.times do
  check_points << gets.split(' ').map!(&:to_i)
end

ans_indexs = []

students.each do |x, y|
  near = Float::INFINITY
  index = 1
  check_points.each.with_index(1) do |(c_x, c_y), i|
    distance = (x - c_x).abs + (y - c_y).abs
    if distance < near
      near = distance
      index = i
    end
  end

  ans_indexs << index
end

ans_indexs.each do |e|
  puts e
end


Measured memory_bytes: 1788