akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    int N;
    cin >> N;
    int *W;
    W = new int [N];
    urept(i,0,N){
        cin >> W[i];
    }
    int thresh=0;
    int sumleft = 0;
    int sumright = 0;
    int min = W[0];
    urept(i,1,N){
        sumright += W[i];
    }
    min = abs(min - sumright);
    sumright = 0;
    urept(i,0,N){
      urept(k,0,i){
        sumleft += W[k];
      }
        drept(j,N-1,i-1){
            sumright += W[j];
        }
        if(abs(sumleft-sumright)<min){
            min = abs(sumleft-sumright);      	
        sumleft = 0;
      	sumright = 0;
        }else{
        sumleft = 0;
      	sumright = 0;
        }
    }

    cout << min << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll gcd(ll a, ll b)
{
	if (b == ll(0)) return a;
	return gcd(b, a%b);
}

int main()
{
	ll A,B;
	cin >> A >> B;
	//cout << gcd(A,B) << endl;
	cout << A * B / gcd(A,B) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>

using namespace std;

string DATA[8];

void dfs(int x, int y)
{
	DATA[y][x] = '0';

	for (int dx = -3; dx <= 3; dx++)
	{
		if (x + dx >= 0 && x + dx < 8)
		{
			if (DATA[y][x + dx] == '1')
			{
				dfs(x + dx, y);
			}
		}
	}

	for (int dy = -3; dy <= 3; dy++)
	{
		if (y + dy >= 0 && y + dy < 8)
		{
			if (DATA[y + dy][x] == '1')
			{
				dfs(x, y + dy);
			}
		}
	}
}

int main()
{
	string ANS[1000][8];

	int N;

	int x, y;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int i = 0; i < 8; i++)
		{
			cin >> DATA[i];
		}

		cin >> x >> y;

		dfs(x - 1, y - 1);

		for (int j = 0; j < 8; j++)
		{
			ANS[i][j] = DATA[j];
		}
	}

	for (int i = 0; i < N; i++)
	{
		cout << "Data " << i + 1 << ":" << endl;

		for (int j = 0; j < 8; j++)
		{
			cout << ANS[i][j] << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1276
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int n;
    cin >> n;

    map<string, ll> m;

    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;

        m[s]++;
    }

    cout << "AC x " << m["AC"] << endl;
    cout << "WA x " << m["WA"] << endl;
    cout << "TLE x " << m["TLE"] << endl;
    cout << "RE x " << m["RE"] << endl;
}


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

int64_t mod=998244353;

int64_t jo(int64_t a,int64_t b){
  int64_t c=a;
  for(int i=0; i<b-1; i++){
    c = c*a;
    c = c%mod;
  }
  if (b==0) c=1;
  return c;
}

int main(){
  int n;
  cin >> n;
  int64_t ans=1;
  vector<int64_t> cnt(n);
  for(int i=0; i<n; i++){
    int64_t x;
    cin >> x;
    cnt.at(x)++;
    if (x==0&&i!=0) ans=0;
    if (x!=0&&i==0) ans=0;
  }
  for(int i=0; i<n-1; i++){
    ans = ans*jo(cnt[i],cnt[i+1]);
    ans = ans%mod;
  }

  cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
vector<bool> fu(1e6+1,1);
bool nopair=0;

vector<bool> furui_bool2(int n) {
  vector<bool> fu2(n + 1, 1);
  fu2.at(0) = 0; fu2.at(1) = 0;
  for (int i=2; i <= n/2 + 1; i++) {
    if (fu2.at(i) == 1) {
      int j = 2 * i;
      while (j <= n) {
        fu2.at(j) = 0;
        j += i;
      }
    }
  }
  return fu2;
}

set<int> prime_fac(ll n) {
  ll sq = sqrt(n);
  set<int> pr;
  vector<bool> fu3 = furui_bool2(sq+2);
  for (int i=2; i <= sq; i++) {
    if (fu3.at(i)) {
      while (n % i == 0) {
        n /= i;
        pr.insert(i);
      }
    }
  }
  if(n>1)pr.insert(n);
  return pr;
}

void furui_bool(int x) {
  set<int> out=prime_fac(x);
  for(auto y : out){
    if(fu.at(y) == 1) {
      fu.at(y)=0;
      int j = 2 * y;
        while (j <= 1e6) {
          if(fu.at(j)==1)fu.at(j) = 0;
          j += y;
      }
    }
    else{nopair=1;break;} 
  }
}

int main() {
  fu.at(0) = 0; fu.at(1) = 0;
  ll n;
  cin>>n;
  ll a[n];
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  ll wgcd=a[0];
  for(int i=0;i<n;i++)wgcd=gcd(wgcd,a[i]);
  for(int i=0;i<n;i++){
    if(a[i]>1)furui_bool(a[i]);
    if(nopair)break;
  }
  if(!nopair)cout<<"pairwise coprime"<<endl;
  else if(wgcd==1)cout<<"setwise coprime"<<endl;
  else cout<<"not coprime"<<endl;
}


Measured memory_bytes: 11396
"use strict";
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

console.log(main());
function main(){
  var n = o.a();
  var s = o.a(1);
  var ans = 0;
  var x = 0;
  for(var i = 0; i < n; i++){
    if(s[i] === "A")x = 1;
    else if(x === 1 && s[i] === "B")x = 2;
    else if(x === 2 && s[i] === "C")ans++, x = 0;
    else x = 0;
  }
  return ans;
}

Measured memory_bytes: 21064
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;

int main(void){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int count=0;
    for(int i=0; i<n; i++){
        if(a[i]>=k)count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 640
# ABC140E
import sys
input = sys.stdin.readline
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

q=int(input())
xs = []
ys = []
qs = dict()
c = 0
for _ in range(q):
    xy = list(map(int,input().split()))
    if len(xy) == 1:
        if c not in qs:
            qs[c] = 0
        qs[c] += 1
    else:
        c += 1
        xs.append(xy[1])
        ys.append(xy[2])

N=len(xs)
sxs=sorted(xs)
zxs = [0]*N
for i, x in enumerate(sorted(range(N), key=lambda x : xs[x])):
    zxs[x] = i

seg_sum_tree = Bit(N)
seg_count_tree = Bit(N)

sy = 0
for i in range(c+1):
    if i in qs:
        x1i=bsearch(i//2 + (-1 if i % 2 == 0 else 0) ,0 ,N ,lambda x : seg_count_tree.sum(x))
#        print(x1i, i//2, seg_count_tree.query(0, 2))
        if i % 2:
        #print(sy, seg_sum_tree.query(0, x1i))
            r = sy - seg_sum_tree.sum(x1i) + \
                   seg_sum_tree.sum(N) - seg_sum_tree.sum(x1i+1)
        else:
            r = sy - seg_sum_tree.sum(x1i+1) + \
                   seg_sum_tree.sum(N) - seg_sum_tree.sum(x1i+1)
        for _ in range(qs[i]):
            print(sxs[x1i], r)
    if i == c:
        break
    x, y = xs[i], ys[i]
    xi = zxs[i]
    sy += y
    seg_sum_tree.add(xi+1, x)
    seg_count_tree.add(xi+1, 1)


Measured memory_bytes: 104924
#include <iostream>
#include <algorithm>
#include <cmath>


const int MAXN = 1e5;

int height[MAXN];
int dp[MAXN];


int main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);

    int rocks; std::cin >> rocks;
    for (int iRock = 0; iRock < rocks; iRock++)
        std::cin >> height[iRock];

    dp[rocks - 2] = std::abs(height[rocks - 2] - height[rocks - 1]);
    for (int iRock = rocks - 3; iRock > -1; iRock--)
        dp[iRock] = std::min(std::abs(height[iRock] - height[iRock + 1]) + dp[iRock + 1], std::abs(height[iRock] - height[iRock + 2]) + dp[iRock + 2]);
    std::cout << dp[0] << '\n';

    return 0;
}


Measured memory_bytes: 1024
try:
    K, N = map(int,input().split())
    A = list(map(int, input().split()))

    li = []
    for i in range(N - 1):
        li.append(A[i + 1] - A[i]) 

    li.append(abs(A[0] + (K - A[-1])))
    print(sum(li) - max(li))
except:
    pass

Measured memory_bytes: 31992
#include<bits/stdc++.h>
typedef long long int lli;

#define em emplace_back
#define rep(i,j,n) for(lli i=j;i<n;i++)
#define repf(i,a,j,n) for(lli i=j,a=0;i<n;i++,a++)
#define repg(i,j,n) for(int i=j;i>n;--i)
using namespace std;

void dbg(vector<long long int > v){
  for(long long int i = 0 ; i<v.size(); ++i){
   cerr<<v[i]<<" ";
  }
  cerr<<endl;
}
void prt(vector<long long int > v){
  for(long long int i = 0 ; i<v.size() ; ++i){
   cout<<v[i]<<" "; 
  }
  cout<<endl;
}
 
void solve(){
    lli n;
    cin>>n;

    lli ans = 0;
    rep(i,1,n+1){
        rep(j,1,n+1){
            if(i*j<n){
                ans++;
            }else{
                break;
            }
        }
    }

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

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
	const int inf = 100000000;
	int n, m;
	int a[1000], b[1000], c[1000], dist[100][100];
	cin >> n >> m;
	for (int i=0; i<m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--;b[i]--;
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (i==j) 
				dist[i][j] = 0;
			else 
				dist[i][j] = inf;
		}
	}
	for (int i=0; i<m; i++) {
		dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i]);
		dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i]);
	}
	for (int k=0; k<n; k++) {
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
			}
		}
	}
	int ans=m;
	for(int i = 0; i < m; ++i){
		bool shortest=false;
		for(int j = 0; j < n; ++j) if(dist[j][a[i]]+c[i]==dist[j][b[i]]) shortest=true;
		if(shortest==true){
			ans=ans-1;
		}
	}

	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>

using namespace std;

int main(){

int N;
cin >> N;
int A[N+1];
int ans=0;
for(int i=1;i<=N;i++){
    cin >>A[i];
    if(A[i]!=i){
        ans++;
    }
}
if(ans==2 || ans==0){
    cout<<"YES"<<endl;
}
else{
    cout<<"NO"<<endl;
}

    

 return 0;
}

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

int main() {
  long a,b,ans=0;
  cin >> a >> b;
  for(long i=a;i<=b;i++) {
    if(i/10000==i%10&&i/1000%10==i/10%10) ans++;
  }
  cout << ans << endl;
}

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

int main(){
    int c;
    string n;
    cin >> n;
    for(int i=0;i<n.length();i++){
        c=count(n.begin(),n.end(),n[i]);
        if(c%2==0){
            continue;
        }else{
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int i,j,s;
  for(i=1;i < 10; i++){
    for(j=1;j < 10;j++){
      s = i * j;
      printf("%dx%d=%d\n",i, j, s);
    }
  }
    return 0;
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl

#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()

#define pb push_back
#define ff first
#define ss second
#define hell 1000000007

#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 300009

ll power(ll a,ll b,ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
        
	ll x,y;cin>>x>>y;
	rep(i,0,x+1)
	{
		ll rem=x-i;
		ll curr=i*2+(rem*4);
		if(curr==y)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using vi = vector<int>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

const int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    string s; cin >> s;
    map<char, int> m;
    rep(i, 4) m[s[i]]++;
    bool f = true; for (auto && p : m) if (p.second != 2) f = false;
    if (f) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

const int N = 55;

ll dp[N][N][N*N];

int n, av;

int main() {
  cin >> n >> av;
  
  vector<int> a(n + 1);
  
  int sm = 0;
  
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sm += a[i];
  }
  
  dp[0][0][0] = 1;
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k <= sm; k++) {
        if (dp[i][j][k]) {
          dp[i+1][j][k] += dp[i][j][k];
          dp[i+1][j+1][k + a[i]] += dp[i][j][k];
        }
      }
    }
  }
  
  ll ans = 0;
  
  for (int i = 1; i <= n; i++) {
    ans += dp[n][i][i * av];
  }
  
  cout << ans << '\n';
  
  return 0;
}

Measured memory_bytes: 65792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N ; 
  vector <int> c(N);
  for ( int i=0 ; i<N ; i++ ){
    cin >>c.at(i) ;
  }
  sort (c.begin() , c.end());
  int sum=1;
  for (int i=0 ; i<N-1 ; i++){
    if(c.at(i)<c.at(i+1)) {
      sum++;
    }
  }
    cout << sum << endl;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(rng(x))
#define RSORT(x) sort(rrng(x))
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main () {
  double a, b, x;
  cin >> a >> b >> x;
  double s0 = a*b/2;
  double s = x/a;
  double ans;
  if (s >= s0) {
    ans = atan2(2*a*a*b-2*x, a*a*a)*180/M_PI;
  }
  else {
    ans = atan2(a*b*b, 2*x)*180/M_PI;
  }
  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main p = new Main();
	}


	final int MAX_N = 1000000;
	boolean[] hurui = new boolean[MAX_N+1];
	int[] primeCount = new int[MAX_N+1];
	
	public Main() {
		Scanner sc = new Scanner(System.in);
		String str = "";
		solve();
		while(sc.hasNextLine()){
			str = sc.nextLine();
			System.out.println(primeCount[Integer.parseInt(str)]);
		}
	}

	public void solve() {
		int count = 0;
		for(int i=2;i<=MAX_N;i++){
			int t = i;
			if(hurui[t]){
				primeCount[t] = count;
				continue;
			}
			
			count++;
			primeCount[t] = count;
			while(t<=MAX_N){
				hurui[t] = true;
				t+=i;
			}
		}		
	}

}

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

typedef long long ll;

ll h,cnt,ans;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>h;
    cnt=1;
    while(h){
        ans+=cnt;
        h>>=1;
        cnt<<=1;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n,q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(n-1)]
PX = [[int(x) for x in input().split()] for _ in range(q)]

Graph = [[] for _ in range(n+1)]
for a,b in AB:
    Graph[a].append(b)
    Graph[b].append(a)

#print(Graph)
Value = [0]*(n+1)
for p,x in PX:
    Value[p] += x
#print(Value)

q = [(1,0)]
while q:
    x,parent = q.pop()
    Value[x] += Value[parent]  #親の値を子に入れる
    for y in Graph[x]:
        if y == parent:
            continue
        q.append((y,x))
print(*Value[1:])

Measured memory_bytes: 125404
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>

//ACL
#include <atcoder/all>
using namespace atcoder;
//ACL END

#define int long long

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;

using P = std::pair<int, int>;
using ll = long long;
using ld = double;

//using bint = boost::multiprecision::cpp_int;


template<typename T, typename U>
std::istream& operator>>(std::istream& in, std::pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}

const int MOD = 998244353;

// https://twitter.com/vane11ope ←フォローしましょう
// (ノ)>◡<(ヾ)ﾓﾁﾓﾁ
signed main(signed argc, char* argv[]) {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int n,m;
    cin>>n>>m;
    dsu d(n);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        d.merge(a-1,b-1);
    }
    cout<<d.groups().size()-1<<endl;
}


Measured memory_bytes: 8980
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void run(void){
  char s[11];
  scanf("%s",s);
  int min=1000;
  int i;
  for(i=0;s[i+2]!='\0';i++){
    min=MIN(min,ABS(100*(s[i]-'0')+10*(s[i+1]-'0')+s[i+2]-'0'-753));
  }
  printf("%d\n",min);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();
        int[][] field = new int[h][w];

        for(int i = 0; i < h; i++){
            String str = sc.next();
            for(int j = 0; j < w; j++){
                field[i][j] = str.charAt(j) == '.' ? 1 : 2;
            }
        }

        int ans = 0;

        for(int hbit = 0; hbit < (1 << h); hbit++){
            for(int wbit = 0; wbit < (1 << w); wbit++){
                int[][] f = new int[h][w];
                for(int i = 0; i < h; i++){
                    for(int j = 0; j < w; j++){
                        f[i][j] = field[i][j];
                    }
                }

                for(int i = 0; i < h; i++){
                    if((hbit & (1 << i)) == (1 << i)){
                        for(int j = 0; j < w; j++){
                            f[i][j] = 3;
                        }
                    }
                }

                for(int i = 0; i < w; i++){
                    if((wbit & (1 << i)) == (1 << i)){
                        for(int j = 0; j < h; j++){
                            f[j][i] = 3;
                        }
                    }
                }

                int count = 0;
                for(int i = 0; i < h; i++){
                    for(int j = 0; j < w; j++){
                        if(f[i][j] == 2){
                            count++;
                        }
                    }
                }

                if(count == k){
                    ans++;
                }

            }
        }

        System.out.println(ans);

    }
}

Measured memory_bytes: 38712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,a,b) for(int i=(a);i<(b);i++)
#define frr(i,a,b) for(ll i=(a-1);i>=(b);i--)
#define vi vector<int>
#define de deque<int>
#define del deque<ll>
#define vl vector<ll>
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define mpp map<ll,ll>
#define rev(a) reverse(a.begin(),a.end())
#define srt(a) sort(a.begin(),a.end())
#define ln(a) a.length()
#define sz(a) a.size()
#define endl "\n"
int M=1000000007;
int n;int h[100005];int dp[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

cin>>n;int k;cin>>k;
f(i,0,n)cin>>h[i];int r;
dp[0]=0;
f(i,1,n)
   {
       dp[i]=M;
       f(j,1,min(i+1,k+1))
       {
           r=abs(h[i]-h[i-j])+dp[i-j];
           dp[i]=min(dp[i],r);
       }

       //cout<<dp[i]<<endl;
   }
cout<<dp[n-1]<<endl;

}


Measured memory_bytes: 1024
// C - Five Transportations
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	ll N; cin>>N;
	ll mini = LLONG_MAX;
	for(int i=0; i<5; ++i){
		ll t; cin>>t;
		mini = min(mini, t);
	}
	ll d = N/mini + (N%mini? 0:-1);
	cout<< d + 5 <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define elif else if
#define ffast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define filoop(n) for(ll i=0;i<(n);i++)
#define fjloop(n) for(ll j=0;j<(n);j++)

int main()
{
    ffast;
    //freopen("0in.txt","r",stdin);
    //freopen("0out.txt","w",stdout);

        int n;
        cin>>n;
        cout<<(n+1)/2<<"\n";

    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7+1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n,m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

/*--------------------template--------------------*/

int main()
{
	while (1) {
		cin >> n >> m;
		if (n == 0 && m == 0) {
			return 0;
		} else {
			vi va(n), vb(m);
			REP(i, n) cin >> va[i];
			REP(i, m) cin >> vb[i];
			ll ansa = 0, ansb = 0;
			ansa = accumulate(ALL(va), 0LL);
			ansb = accumulate(ALL(vb), 0LL);
			ll diff = ansa - ansb;
			ll a = 0, b = 0;
			ans = 0;
			sum = INF;
			REP(i, n)
			{
				REP(j, m)
				{
					if (2 * (va[i] - vb[j]) == diff) {
						ans++;
						if (sum >= va[i] + vb[j]) {
							a = i;
							b = j;
						}
						sum = min(sum, va[i] + vb[j]);
					}
				}
			}
			if (ans == 0) {
				cout << -1 << endl;
			} else {
				cout << va[a] << ' ' << vb[b] << endl;
			}
		}
	}
}

Measured memory_bytes: 2988
#include<stdio.h>
int main()
{
    int n,x,i,j,k,way;
    while(1)
    {
        scanf("%d %d",&n,&x);
        if(n==0 && x==0)
        {
            return 0;
        }
        way=0;
        for(i=1; i<=n; i++)
        {
            for(j=i+1; j<=n; j++)
            {
                for(k=j+1; k<=n; k++)
                {
                        if(i+j+k==x)
                        {
                            way++;
                        }
                }
            }
        }
        printf("%d\n",way);
    }
    return 0;
}



Measured memory_bytes: 2032
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define r0 return 0;
#define f(k,i,n,j) for(ll k=i;k<=n;k=k+j)
#define cin(a) cin>>a;
#define loop while(t--)
#define vi vector<int>
#define vii vector<long long int>
#define SORT(v) sort(v.begin(),v.end());
#define mod (1e9+7)
#define crap ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
signed main()
{
    crap;
    int n;
    cin>>n;
    int a[n];
    int f=0;
    unordered_map<int,int> m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        m[a[i]]++;
        if(m[a[i]]>1)
        {
            f=1;
            break;
        }
    }
    if(f==1)
    cout<<"NO"<<endl;
    else
    cout<<"YES"<<endl;
}

Measured memory_bytes: 10056
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long A,B,C,K,cnt = 0;
  cin >> A >> B >> C >> K;
  if(K <= A){
    cnt = K;
    K = 0;
  }else{
    cnt = A;
    K -= A;
  }
  if(K <= B){
    K = 0;
  }else{
    K -= B;
  }
  if(K <= C){
    cnt -= K;
  }else{
    cnt -= C;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3636
#include <cstdio>

int main(void){
    int H, W;

    while (1){
        scanf ("%d %d", &H, &W);
        if (H == 0 && W == 0){
            break;
        }

        for (int i = 0; i < H; i++){
            for (int j = 0; j < W; j++){
                if (i == 0 || i == H - 1 || j == 0 || j == W - 1){
                    printf("#");
                }
                else {
                    printf(".");
                }
            }
            printf("\n");
        }
        
        printf("\n");
    }

    return 0;
}

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

int N,L;
int t[100005];
int ans[100005];

int main(){
  cin>>N>>L;
  for(int i=1;i<=N;i++)cin>>t[i];

  queue<int> Q;
  for(int i=1;i<=N;i++){
    if(t[i-1]<t[i]&&t[i]>t[i+1]){
      Q.push(i);
      ans[i]=L-t[i];
    }
  }
  while(!Q.empty()){
    int p=Q.front();Q.pop();
    t[p]=0;
    if(1<=p-1){
      if(t[p-2]<t[p-1]){
	ans[p-1]=ans[p]+L-t[p-1];
	Q.push(p-1);
      }
    }
    if(p+1<=N){
      if(t[p+1]>t[p+2]){
	ans[p+1]=ans[p]+L-t[p+1];
	Q.push(p+1);
      }
    }
  }

  int maxm=0;
  for(int i=1;i<=N;i++)maxm=max(maxm,ans[i]);
  cout<<maxm<<endl;
  return 0;
}

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

int main(){  
 
  int A,B,C,D,E;
  cin >> A >> B;
  
  C = A+B;
  D = A-B;
  E = A*B;
  
    
  cout << max(max(C, D),E) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a[105];
	int n,l;
	cin>>n>>l;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		cout<<a[i];
	cout<<endl; 
} 

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

int main(){
  int K, A, B;
  cin >> K >> A >> B;
  
  if(A%K == 0 || B%K == 0) cout << "OK" << endl;
  else{
    int x = A / K;
    int y = B / K;
    if(x == y) cout << "NG" << endl;
    else cout << "OK" << endl;
  }
}

Measured memory_bytes: 3624
//AOJ:0528 common sub-string
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s, t; int roop1, ans = 0, memo[4000][4000];
int main() {
	while (cin >> s >> t){
		ans = 0;
		for (int i = 0; i<s.size(); i++){
			for (int j = 0; j<t.size(); j++){
				if (s[i] == t[j]&&memo[i][j]==0){
					memo[i][j]=1;
					roop1 = 1;
					while (1){
						if (s[i + roop1] == 0 || t[j + roop1] == 0){
							break;
						}
						else{
							if (s[i + roop1] == t[j + roop1]){
								memo[i+roop1][j+roop1]=1;
								roop1++;
							}
							else if (s[i + roop1] != t[j + roop1]){
								break;
							}
						}
					}
					ans = max(ans, roop1);
				}
			}
		}
		cout << ans << endl;
		for (int i = 0; i<s.size(); i++){
			for (int j = 0; j<t.size(); j++){
				memo[i][j]=0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 63708
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ll> p;
typedef unsigned long long int ull;
const ll MOD=998244353;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e9;

ll N,M,V,P;
ll A[100000];

bool C(int x){
    if(x<P) return true;
    if(A[x]+M<A[P-1]) return false;
    ll sum=0;
    sum+=M*P;
    sum+=M*(N-1-x);
    for(int i=P-1;i<x;i++){
        sum+=min(M,A[x]+M-A[i]);
    }
    return sum>=M*V;
}

int main(){
    string a;cin>>a;
    ll n=(int)a.size();
    vector<ll> cnt(26,0);
    for(int i=0;i<n;i++){
        cnt[a[i]-'a']++;
    }
    ll ans=n*(n-1)/2+1;
    for(int i=0;i<26;i++){
        ans-=cnt[i]*(cnt[i]-1)/2;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3712
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long int arr[10001][10001];
long long int knapsack(long long int weight[],long long int value[],long long int n,long long int w)
{
    if(n==-1  || w==0)
    {
        return 0;
    }
        if(arr[n][w]!=-1)
    {
        return arr[n][w];
    }
    if(weight[n]>w)
    {
       return knapsack(weight,value,n-1,w);
    }
    else
    {
      long long int temp1=knapsack(weight,value,n-1,w);
      long long int temp2=knapsack(weight,value,n-1,w-weight[n])+value[n];
       long long int p=max(temp1,temp2);
        arr[n][w]=p;
        return p;
    }
}
int main()
{
   long long int n,w;
    cin>>n>>w;
   long long int weight[n],value[n];
    long long int dp[n+1][w+1]={0};
    for(long long int i=0;i<n;i++)
    {
        cin>>weight[i];
        cin>>value[i];
    }
    for(long long int i=0;i<=n;i++)
    {
        for(long long int j=0;j<=w;j++)
        {
            if(i==0 || j==0)
            {
                dp[i][j]=0;
            }
            else
            {
              long long  int inc=0,excl=0;
                if(weight[i-1]<=j)
                {
                    inc=value[i-1]+dp[i-1][j-weight[i-1]];

                }
                excl = dp[i-1][j];
                dp[i][j]=max(inc,excl);
            }
        }
    }
    cout<<dp[n][w]<<endl;
}



Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define ll long long
#define int long long
using namespace std;
void boost()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}
void free()
{
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
}
main()
{
	//free();
	boost();
	int a, b, c;
	cin >> a >> b >> c;
	int mn = min(a, min(b, c));
	int md = 0;
	if(a >= b && b >= c) md = b;
	if(a >= c && c >= b) md = c;
	if(b >= a && a >= c) md = a;
	if(b >= c && c >= a) md = c;
	if(c >= b && b >= a) md = b;
	if(c >= a && a >= b) md = a;
	//int ans = min(a * b, min(b * c, c * a));
	if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0) cout << 0, exit(0);
	cout << md * mn;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, M;
bool flag[int(1e5 + 5)];
ll DP[int(1e5 + 5)];

int main(){
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++){
    int A; scanf("%d", &A);
    flag[A] = true;
  }

  DP[0] = 1;
  if (!flag[1]) DP[1] = 1;
  for (int i = 2; i <= N; i++){
    if (flag[i]) continue;
    DP[i] = DP[i - 1] + DP[i - 2];
    DP[i] %= MOD;
  }
  cout << DP[N] << endl;

  return 0;
}


Measured memory_bytes: 4508
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define forx(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)

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

    int n;
    cin >> n;
    int k;
    cin >> k;

    if (k == 1)
        cout << 0 << endl;
    else
        cout << n - k << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

using ll = long long;
template <ll MOD = 1000000007>
struct Mint{
    ll x;

    Mint() : x(0) {}
    Mint(ll t){
        x = t % MOD;
        if(x < 0) x += MOD;
    }
    
    Mint pow(ll n){
        Mint res(1), t(x);
        while(n > 0){
            if(n & 1) res *= t;
            t *= t;
            n >>= 1;
        }
        return res;
    }

    Mint inv() const {
        ll a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return Mint(u);
    }

    Mint & operator += (Mint a){
        x += a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    Mint & operator -= (Mint a){
        x += MOD - a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    Mint & operator *= (Mint a){
        x = 1LL * x * a.x % MOD;
        return *this;
    }
    Mint & operator /= (Mint a){
        return (*this) *= a.inv();
    }

    Mint operator + (Mint a) const { return Mint(x) += a; }
    Mint operator - (Mint a) const { return Mint(x) -= a; }
    Mint operator * (Mint a) const { return Mint(x) *= a; }
    Mint operator / (Mint a) const { return Mint(x) /= a; }

    Mint operator - () const{ return Mint(-x); }

    bool operator == (const Mint a){ return x == a.x; }
    bool operator != (const Mint a){ return x != a.x; }
    bool operator < (const Mint a){ return x < a.x; }

    friend ostream & operator << (ostream & os, const Mint &a){
        return os << a.x;
    }

    friend istream & operator >> (istream & is, Mint &a){
        ll t;
        is >> t;
        a = Mint<MOD>(t);
        return (is);
    }
};

signed main(){
    int n;
    cin >> n;
    Mint<> dp[n + 1][4][4][4]; //dp[何文字目][3文字前][2文字前][1文字前], AGCT = 0123
    dp[0][3][3][3] = 1;
    for(int i = 0; i < n; i++){
        for(int a = 0; a < 4; a++){
            for(int b = 0; b < 4; b++){
                for(int c = 0; c < 4; c++){
                    for(int now = 0; now < 4; now++){
                        if(b == 0 && c == 1 && now == 2 || //?AGC
                        b == 0 && c == 2 && now == 1 || //?ACG
                        b == 1 && c == 0 && now == 2 || //?GAC
                        a == 0 && c == 1 && now == 2 || //A?GC
                        a == 0 && b == 1 && now == 2 //AG?C
                        ) continue;
                        dp[i + 1][b][c][now] += dp[i][a][b][c];
                    }
                }
            }
        }
    }
    Mint<> ans;
    REP(a,4){
        REP(b,4){
            REP(c,4){
                ans += dp[n][a][b][c]; 
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
	string a, b, c; cin >> a >> b >> c;
	cout << "A" << b[0] << "C" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++)

#define ALL(x) (x).begin(), (x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

using namespace std;
using ll = long long;
using vel = vector<ll>;
using ves = vector<string>;
using veb = vector<bool>;
using qul = queue<ll>;

int binary_search(ll x, vel a){
    auto ite = lower_bound(ALL(a), x);
    if(ite != a.end() && *ite == x) {
        return ite - a.begin() ;
    } else {
        return -1;
    }

}

ll modpow(ll a, ll n, ll mod) {
    if(n == 0)
        return 1;
    if(n == 1)
        return a % mod;
    if(n % 2 == 1)
        return (a * modpow(a, n - 1, mod)) % mod;
    ll t = modpow(a, n / 2, mod);
    return (t * t) % mod;
}

int main() {
    ll N,l=0, r=0,ans = 0;
    cin >> N;
    string C;
    cin >> C;
    r = N - 1;
    REP(i, N){
        if(C[l] == 'W' && C[r] == 'R'){
            ans++;
            r--;
            l++;
        } else if(C[l] == 'R' && C[r] == 'R') {
            l++;
        } else if(C[l] == 'W' && C[r] == 'W') {
            r--;
        } else if(C[l] == 'R' && C[r] == 'W') {
            r--;
            l++;
        }

        if(l >= r){
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3756
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String[] ary = s.split("");
        List<String> sary = new ArrayList<>();
        for (int i = 0; i < ary.length; i++) {
            String a = ary[i];
            if (a.equals("0") || a.equals("1")) {
                sary.add(a);
            } else if (sary.size() != 0){
                sary.remove(sary.size() - 1);
            }
        }
        for (String ans: sary) {
            System.out.print(ans);
        }
    }
}

Measured memory_bytes: 21332
//From Naruto to Hokage
//#include <RJ>
#include<bits/stdc++.h>
using namespace std;

#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define endl        '\n'
#define mii         map<ll,ll>
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define INF         (1ll<<60)
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define rrep(i,a,b)  for(ll i=a;i>=b;i--)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
const int N=3005;
vi v;
ll dp[N][N];
ll rec(ll l,ll r){
    ll &ans=dp[l][r];
    if(ans!=-1) return ans;
    if(l==r) return ans=v[l];
    return ans=max(v[l]-rec(l+1,r),v[r]-rec(l,r-1));
}
void solve(){
    ll n,x;
    cin>>n;
    rep(i,0,n-1) cin>>x,v.push_back(x);
    rep(i,0,N-1) rep(j,0,N-1) dp[i][j]=-1;
    // memset(dp,0,sizeof(dp));
    cout<<rec(0,n-1);
}
signed main()
{
    ios
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
        solve();
    }
    time
    return 0;
}

Measured memory_bytes: 71040
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)1e9 + 7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int add(int &a, int b) { return (a += b) >= MOD ? a -= MOD : a; }

int main() {
    int H, W; cin >> H >> W;
    vector<string> a(H);
    for (int i = 0; i < H; i++) cin >> a[i];

    vector<vector<int>> dp(H, vector<int>(W, 0));
    dp[0][0] = 1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (i + 1 < H && a[i + 1][j] == '.') add(dp[i + 1][j], dp[i][j]);
            if (j + 1 < W && a[i][j + 1] == '.') add(dp[i][j + 1], dp[i][j]);
        }
    }
    cout << dp[H - 1][W - 1] << endl;
    return 0;
}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N, M, K;
    cin >> N >> M >> K;
    Vl A(N), B(M);
    ll sa = 0, sb = 0;
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (ll i = 0; i < M; i++) {
        cin >> B[i];
        sb += B[i];
    }

    ll ans = 0;
    ll idx = M;
    for (ll i = 0; i <= N; i++) {
        if (sa > K) break;
        while (idx >= 0 && sa + sb > K) {
            sb -= B[--idx];
        }
        ans = max(ans, i + idx);
        if (i < N) {
            sa += A[i];
        }
    }

    cout << ans << "\n";
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 6368
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    int a, b, k;
    cin >> a >> b >> k;
    for(int i = a; i <= min(b, a+k-1); i++)
        cout << i << endl;
    for(int i = max(a+k, b-k+1); i <= b; i++)
        cout << i << endl;
}


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

int main(){
    int n,k;
    cin>>n>>k;
    rep(i,n){
        int a;
        cin>>a;
    }
    
    
    cout<< 1 + (n-2)/(k-1)<<endl;
    
    return 0;
}


Measured memory_bytes: 256
N, K = map(int,input().split())
A = list(map(int,input().split()))

a = list(set((A)))
check = len(a)
dff = check - K
if dff <= 0:
  print(0)
  exit(0)
ans_list = [0]*check
A.sort()
index = 0
for i in range(len(A)):
  
  if i >= 1 and A[i] != A[i-1]:
    index += 1
  ans_list[index] += 1
ans_list.sort()
result = sum(ans_list[:dff])
print(result)

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

int main(){
  string s;
  int g,m,d;
  bool flg;
  while(1){
    flg=false;
    cin>>s;
    if(s=="#") break;
    cin>>g>>m>>d;
    if(g>=32){
      flg=true;
    }
    if(g>=31&&m>=5){
      flg=true;
    }
    if(flg){
      s="?";
      g-=30;
    }
    cout<<s<<" "<<g<<" "<<m<<" "<<d<<endl;
  }
  return 0;
}



Measured memory_bytes: 3204
#include<stdio.h>
#define N 100
int main(){

  int num[N],i,j,l=1,n,v;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&num[i]);
  }
  i=0;
  while(l){
    l=0;
    for(j=1;j<n;j++){
      if(num[j]<num[j-1]){
	v=num[j];
	num[j]=num[j-1];
	num[j-1]=v;
	l++;
	i++;
      }
    }
  }
  for(j=0;j<n-1;j++) printf("%d ",num[j]);
  printf("%d\n%d\n",num[n-1],i);
  return 0;
}



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

int H,W,D;
int Q;
pair<int,int> mapw[90001];
int L,R;
int l=911111,r=-1;
bool ch[90001]={};
int dia[90001]={};
int ll[100000]={};
int lr[100000]={};
int ansdi[90001]={};

int main(){
  int i,j,k,ans[100000]={};
  int x,y;
  scanf("%d%d%d",&H,&W,&D);

  for(i=1;i<=H;i++){
    for(j=1;j<=W;j++){
      scanf("%d",&k);
      mapw[k].first=i;
      mapw[k].second=j;
    }
  }
  scanf("%d",&Q);
  for(i=0;i<Q;i++){
    scanf("%d%d",&ll[i],&lr[i]);
    if(ll[i]<l)l=ll[i];
    if(lr[i]>r)r=lr[i];
  }
  for(j=D+1;j<=r;j++){
    x = mapw[j-D].first-mapw[j].first;
    if(x<0)x*=-1;
    y = mapw[j-D].second-mapw[j].second;
    if(y<0)y*=-1;
    dia[j]=x+y;
  }
  for(i=1;i<=r;i++){
    // printf("%d%d\n",ansdi[i-1],dia[i]);
    if(i<=D)ansdi[i]=0;
    else ansdi[i] =ansdi[i-D]+dia[i];
  }
  for(i=0;i<Q;i++){
    ans[i]=ansdi[lr[i]]-ansdi[ll[i]];
    
  }
    
  /* for(i=0;i<Q;i++){
     scanf("%d%d",&L,&R);*/
  /*   for(j=L+D;j<=R;j+=D){
       if(ch[j]==0){
       x = mapw[j-D].first-mapw[j].first;
       if(x<0)x*=-1;
       y = mapw[j-D].second-mapw[j].second;
       if(y<0)y*=-1;
       ch[j]++;
       dia[j]=x+y;
       }

       ans[i] += dia[j];*/
  /*    if(L!=R){
	j=L+D;
	while(j<l){
	x = mapw[j-D].first-mapw[j].first;
	if(x<0)x*=-1;
	y = mapw[j-D].second-mapw[j].second;
	if(y<0)y*=-1;
	//     ch[j]++;
	dia[j]=x+y;
	ans[i]+=dia[j];
	if(j==R)break;
	j+=D;
	}
	if(j!=R){
	while(j<r){
	ans[i]+=dia[j];
	if(j==R)break;
	j+=D;
	}
	}
	if(j!=R){
	while(j<=R){
	x = mapw[j-D].first-mapw[j].first;
	if(x<0)x*=-1;
	y = mapw[j-D].second-mapw[j].second;
	if(y<0)y*=-1;
	//     ch[j]++;
	dia[j]=x+y;
	ans[i]+=dia[j];
	if(j==R)break;
	j+=D;
	}
	}
	}*/
      
    
  
 
  for(i=0;i<Q;i++)printf("%d\n",ans[i]);
  return 0;
}


Measured memory_bytes: 3712
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


int main()
{
	double r;
	cin >> r;

	printd(2 * r * M_PI, 10);
}


Measured memory_bytes: 3736