akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1000000000000000001
#define ll long long
#define pll pair<ll, ll>
using namespace std;

//=============warshall_floyd============================
void  warshall_floyd(ll V, vector<vector<ll>>& d)
{
  for (ll k = 0; k < V; ++k)
  {
    for (ll i = 0; i < V; ++i)
    {
      for (ll j = 0; j < V; ++j)
      {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}
//=================================================


int main()
{
  ll N, M, R;
  cin >> N >> M >> R;
  vector<ll> rs(R);
  for (ll i = 0; i < R; ++i)
  {
    ll r;
    cin >> r;
    rs.at(i) = r - 1;
  }
  sort(rs.begin(), rs.end());
  // cout << "rs" << endl;
  // for (ll i = 0; i < R; ++i)
  // {
  //   cout << rs.at(i) << ' ';
  // }
  // cout << endl;
  vector<vector<ll>> dp(N, vector<ll>(N, INF));
  for (ll i = 0; i < N; ++i)
  {
    dp.at(i).at(i) = 0;
  }
  for (ll i = 0; i < M; ++i)
  {
    ll a, b, c;
    cin >> a >> b >> c;
    dp.at(a - 1).at(b - 1) = c;
    dp.at(b - 1).at(a - 1) = c;
  }
  warshall_floyd(N, dp);
  // cout << "wersahr" << endl;
  // for (ll i = 0; i < N; ++i)
  // {
  //   for (ll j = 0; j < N; ++j)
  //   {
  //     cout << dp.at(i).at(j) << ' ';
  //   }
  //   cout << endl;
  // }
  // cout << endl;
  ll ans = INF;
  while (true)
  {
    ll temp = 0;
    for (ll i = 0; i < R - 1; ++i)
    {
      temp += dp.at(rs.at(i)).at(rs.at(i + 1));
    }
    ans = min(ans, temp);
    if (!next_permutation(rs.begin(), rs.end()))
    {
      break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
//
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a,b,n;
    cin>>n>>a>>b;
    while(true){
        if (a+1!=b) {
			++a;
		}else{
			cout << "Borys" << endl;
			break;
		}
        if (a!=b-1) {
            --b;
        } else{
            cout<<"Alice"<<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
	
	int b1,b2,b3;
	cin >> b1 >> b2 >> b3;
	if((b1 == 1 && b2 == 1)||b3 ==1){
		cout << "Open" << endl;
	}else{
		cout << "Close" << endl;
	}
	
	return 0;
}

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

#define int long long
signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    cout << max (max(a * c, a * d), max(b * c, b * d));



    }



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

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

    vector<int> a(n), ball(n,0);// each element = 0 or 1
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    for(int i=0; i<n; i++){
        int k = 2;
        while((n - i) * k <= n){
            ball[(n - i) - 1] += ball[(n - i) * k - 1];
            k += 1;
        }
        ball[(n - i) - 1] += a[(n - i) * 1 - 1];
        ball[(n - i) - 1] %= 2;
    }
    
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += ball[i];
    }
    cout << sum << endl;
    for(int i=0; i<n; i++){
        if(ball[i] == 1) cout << i + 1 << " ";
    }
    return 0;
}

Measured memory_bytes: 2432
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solver {

    private final int[][] A;
    private final int[] P;

    Solver(Scanner in) {
        int N = in.nextInt();
        int Q = in.nextInt();
        IntStream.Builder[] builder = new IntStream.Builder[N];
        Arrays.setAll(builder, i -> IntStream.builder());
        for (int i = 0; i < N - 1; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            builder[a].accept(b);
            builder[b].accept(a);
        }
        A = new int[N][];
        for (int i = 0; i < N; i++) {
            A[i] = builder[i].build().toArray();
        }
        P = new int[N];
        for (int i = 0; i < Q; i++) {
            P[in.nextInt() - 1] += in.nextInt();
        }
        result = new int[N];
    }

    void solve() {
        dfs(-1, 0, 0);
        System.out.println(Arrays.stream(result).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }

    int[] result;

    void dfs(int root, int pos, int sum) {
        if (root == pos) return;
        sum += P[pos];
        result[pos] = sum;
        for (int b : A[pos]) {
            if (b == root) continue;
            dfs(pos, b, sum);
        }
    }
}

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

        new Solver(in).solve();

        in.close();
    }
}

Measured memory_bytes: 259048
#include <stdio.h>
int main(void){
    int a, b, c, d;
    
    scanf("%d %d %d %d", &a, &b, &c, &d);
    
    if(b < c || a > d || a >= b || (b == c && b >= d)){
        printf("0\n");
    } else if(b >= d && a <= c){
        printf("%d\n", d - c);
    } else if(b <= d && b >= c && a <= c){
        printf("%d\n", b - c);
    } else if(a >= c && d <= b){
        printf("%d\n", d - a);
    } else if(a >= c && d >= b){
        printf("%d\n", b - a);
    }
    
    return 0;
}


Measured memory_bytes: 1704
(r, c) = [int(i) for i in input().split()]

ct = [0 for d in range(c)]
tmp = []
for rc in range(r):
    tmp = [int(i) for i in input().split()]
    total = 0
    for cc in range(c):
        ct[cc] += tmp[cc]
        total += tmp[cc]
        print(tmp[cc], end=' ')
    print(total)
total = sum(ct)
print(' '.join([str(i) for i in ct]), total)

Measured memory_bytes: 6724
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	for(int i=0,num[3],ans;i<n;i++){
		for(int j=0;j<3;j++)cin>>num[j];
		num[0]--;
		num[1]--;
		if((num[0]+1)%3==0)ans=num[1]*20;
		else ans=num[1]/2*39+num[1]%2*20;
		cout<<196471-ans-num[0]/3*590-num[0]%3*195-num[2]<<endl;
	}
}

Measured memory_bytes: 1160
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws IOException {

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int K = Integer.parseInt(br.readLine());
	String[] array = br.readLine().split(" ");

	int A = Integer.parseInt(array[0]), B = Integer.parseInt(array[1]);

	String result = "NG";
	for (int i = A; i <= B; i++) {
	    if (i % K == 0) {
		result = "OK";
		break;
	    }
	}
	System.out.println(result);
    }
}

Measured memory_bytes: 32608
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
int main()
{
  //flash;
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  int ans=1;
  while(a!=0 && c!=0){
    c-=b;
    if(c<=0)break;
    a-=d;
    if(a<=0){ans=0;break;}
  }
  if(!ans)cout<<"No";
  else cout<<"Yes";
  return 0;
}
//code the AC sol !
// BS/queue/map

Measured memory_bytes: 3600
#include <iostream>
using namespace std;

int main()
{
    string S,T,U;
    int A,B;
    cin >> S >> T >> A >> B >> U;

    if(S == U)
        A = A-1;
    else
        B = B-1;

    cout << A << " " << B;

    return 0;
}

Measured memory_bytes: 256
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    d, t, s = nm()
    if d / s <= t:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


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

long long n, a[2010], k, ans = 0;
vector<long long> b;

int main() {
    memset(a, 0, sizeof(a));
    scanf("%lld", &n);
    for(long long i = 0; i < n; i++) scanf("%lld", &k), a[k]++, b.push_back(k);
    for(long long i = 1; i <= 2000; i++) a[i] += a[i-1];
    for(long long i = 0; i < b.size(); i++) {
        for(long long j = 0; j < b.size(); j++) {
            if(i == j) continue;
            long long c = b[i], d = b[j];
            ans += a[c+d-1] - a[abs(d - c)] - 1 - (abs(d-c)+1 <= min(c, d));
        }
    }
    ans /= 6;
    printf("%lld", ans);
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

int main () {
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    h += m/60;
    double x1 = a*cos(h*M_PI/6);
    double y1 = a*sin(h*M_PI/6);
    double x2 = b*cos(m*M_PI/30);
    double y2 = b*sin(m*M_PI/30);
    double dx = x1-x2, dy = y1-y2;
    //cout << x1 << y1 << x2 << y2 << endl;

    double ans = sqrt(dx*dx + dy*dy);
    printf("%.12lf\n", ans);

    return 0;
}

Measured memory_bytes: 4096
#include<stdio.h>
int main(){
  int A,n,i,j,p=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A);
    if(A >= 2){
      for(j=2;j*j<=A;j++){
	if(A % j == 0){
	  p++;
	  break;
	}
      }
    }
    else {
      p++;
    }
  }
  n=n-p;
  printf("%d\n",n);
  return 0;
}


Measured memory_bytes: 2060
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <time.h>
#include <queue>
#include <string.h>
#include <cmath>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define LL long long
int main(){
    ll a,b,k;
    sld(a) sld(b) sld(k);
    while(k){
        if(a&1){
            a--;
            b += a >> 1;
            a >>= 1;
        }else{
            b += a >> 1;
            a >>= 1;
        }

        k --;
        if(k == 0){
            pld(a) pk pld(b) pn
            return 0;
        }else if(b &1){
            b--;
            a += b>>1;
            b >>= 1;
        }else{
            a += b>>1;
            b >>= 1;
        }
        k--;
        if(k == 0){
            pld(a) pk pld(b) pn
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 256
import java.io.*;

class Main
{
    public static void main (String[ ] args) throws Exception
    {
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
        StringBuffer sb = new StringBuffer();
        
        while(true)
        {
            String[] strAry = (br.readLine()).split(" ");
            int a     = Integer.parseInt(strAry[0]);
            String op = strAry[1];
            int b     = Integer.parseInt(strAry[2]);
        
            if(true == op.equals("?"))
            {
                break;
            }

            switch(op.charAt(0))
            {
            case '*':
                sb.append(a * b).append("\n");
                break;
            case '/':
                sb.append(a / b).append("\n");
                break;
            case '+':
                sb.append(a + b).append("\n");
                break;
            case '-':
                sb.append(a - b).append("\n");
                break;
            }
        }
        System.out.print(sb);
    }
}

Measured memory_bytes: 24152
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#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 <numeric>
#include <iomanip>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int mx2[] = {1,0};
int my2[] = {0,1};

int main(){
        int s; cin >> s;
        vector<int> a(1000001);
        if(s == 1) {
          cout << 4 << endl;
          return 0;
        }if(s == 2) {
          cout << 4 << endl;
          return 0;
        }else{
            a[0] = s;
            for (int i = 0; i < 1000001; i++) {
                if (a[i] % 2 == 0) a[i + 1] = a[i] / 2;
                else a[i + 1] = 3 * a[i] + 1;
            }
            for (int i = 0; i < 1000000; i++) {
                if (a[i] == 4) {
                    cout << i + 4 << endl;
                    break;
                }
            }
        }
	}


Measured memory_bytes: 4096
#include<stdio.h>
#define MAX 100000

int A[MAX], n;

int partition(int p, int r){
  int x, i, j, t;
  x = A[r];
  i = p-1;
  for(j=p ; j<r ; j++){
    if(A[j] <= x){
      i++;
      t = A[i];
      A[i] = A[j];
      A[j] = t;
    }
  }
  t = A[i+1];
  A[i+1] = A[r];
  A[r] = t;
  return i+1;
}

int main(){
  int i, q;

  scanf("%d", &n);
  for(i=0 ; i<n ; i++)scanf("%d", &A[i]);

  q = partition(0, n-1);

  for(i=0 ; i<n ; i++){
    if(i)printf(" ");
    if(i==q)printf("[");
    printf("%d",A[i]);
    if(i==q)printf("]");
  }
  printf("\n");

  return 0;
}



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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int answer = n * (n - 1) / 2 + m * (m - 1) / 2;
    cout << answer << endl;
    return 0;
}


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

int main()
{
  int n;
  cin>>n;
  int k;
  cin>>k;
  int arr[n];
  int dp[n];
  int count;
  for(int i=0 ; i<n; i++)
  {
    cin>>arr[i];
  }
  dp[0] = 0;
  dp[1] = fabs(arr[1] - arr[0]);
  for(int i=2 ; i<n ; i++)
  {
    count = 2;
    dp[i] = dp[i-1] + fabs(arr[i] - arr[i-1]);
    while(count<=k && i-count>=0)
    {
      dp[i] = min(dp[i-count] + abs(arr[i] - arr[i-count]) , dp[i]);
      count++;
    }
    
  }
  cout<<dp[n-1];
  return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <iostream>

#define NDEBUG

int lcm(const int a, const int b)
{
	int s = std::max(a, b);
	int t = std::min(a, b);
	int r;
	for (;;) {
		r = s % t;
		if (r == 0) {
			return t;
		}
		s = t;
		t = r;
	}
}

int sub(const int a, const int b, const int k)
{
	int count = 0;
	int i = 1;
	int lcm_a_b = lcm(a, b);
	for (;;) {
		if (lcm_a_b % i == 0) {
			++count;
			if (count == k) {
				return lcm_a_b / i;
			}
		}
		++i;
		assert(i <= lcm_a_b);
	}
}

int main(void)
{
	int A, B, K;
	std::cin >> A >> B >> K;
	std::cout << sub(A, B, K) << std::endl;
	return 0;
}


Measured memory_bytes: 256
/** 
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

//#define DEBUG
#ifndef DEBUG
#define endl "\n"
#endif

const double PI=3.1415926535897932384626433;
typedef long long ll;
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }

typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;

const int MOD=1e9+7;

int mul(const int v1, const int v2, int mod=MOD) {
    return (int)((1LL * v1 * v2) % mod);
}

int toPower(int a, int p, int mod=MOD) {
    int res = 1;
    while (p != 0) {
        if (p & 1)
            res = mul(res, a, mod);
        p >>= 1;
        a = mul(a, a, mod);
    }
    return res;
}

int pl(int v1, int v2, int mod=MOD) {
    int res = v1 + v2;

    if (res < 0)
        res += mod;

    else if(res>=mod)
        res-=mod;

    return res;
}

void solve() {
    cini(n);
    vll a(n);
    vi b(60);   // b[i]== times bit i is set
    for(int i=0; i<n; i++) {
        cin>>a[i];
        for(int j=0; j<60; j++) {
            if(a[i]&(1LL<<j))
                b[j]++;
        }
    }
#ifdef DEBUG
cout<<"bitcnt:20=";
for(int i=0; i<20; i++) 
    cout<<b[i]<<" ";
cout<<endl;
#endif

    vi bmuls(60);   
    bmuls[0]=1;
    for(int i=1; i<60; i++)
        bmuls[i]=toPower(2,i);

    ll ans=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<60; j++) {
            int bsum;
            if(a[i]&(1LL<<j)) {
                b[j]--;
                bsum=(n-i-1)-b[j];
            } else {
                bsum=b[j];
            }
            if(j>0) {
                bsum=mul(bsum, bmuls[j]);
            }
            ans=pl(ans,bsum);

        }
    }
    cout<<ans<<endl;

}

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



Measured memory_bytes: 2560
def main(argv)
  n = gets.chomp.to_i
  s = gets.chomp
  
  t = 1
  c = s[0]
  i = 1
  while i < n do
    if s[i] != c then
      t += 1
      c = s[i]
    end
    
    i += 1
  end
  
  puts t.to_s
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 1916
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>


#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

using namespace std;

ll modd = 1000 * 1000 * 1000 + 7;

template<class T>
T fastpower(T x, ll pw) {
    T w = x, res = 1;
    while (pw>0) {
        if (pw&1) {
            res *= w; res %= modd;
        }
        pw >>= 1;
        w *= w; w %= modd;
    }
    return res;
}


int main()   {


      ios_base::sync_with_stdio(false);

      cout.precision(17);
      mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no



//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readll(n);
        ll ret = fastpower<ll>(10, n);
        ret += modd - fastpower<ll>(9,n);
        ret += modd - fastpower<ll>(9,n);
        ret += fastpower<ll>(8,n);
        cout << (ret%modd) << endl;
    }
    return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>
#define isNum(A) (A<='9' && A>='0')
#define SIZE 99
#define max(a,b) (a>b ? a : b)

int map[SIZE][SIZE];

int main(void)
{
     int i, j, n, t;
     char ch = getchar();

     /* init */
     for(i=0; i<SIZE; i++)
	  for(j=0; j<SIZE; j++)
	       map[i][j] = 0;
     
     /* input */
     i = j = n = 0;
     while(ch!=EOF){
	  t = 0;
	  while(isNum(ch)) t = t*10+ch-'0', ch = getchar();
	  map[i][j] = t;
 
	  j++;
	  if(ch == '\n'){
	       if(j>n) n = j;
	       j = 0, i++;
 	  }

	  ch = getchar();
     }

     /* calc */
     for(i=1; i<n; i++){
	  map[i][0] += map[i-1][0];

	  for(j=1; j<=i; j++)
	       map[i][j] += max(map[i-1][j], map[i-1][j-1]);
     }

     for(i=0; i<n-1; i++)
	  for(j=0; j<=n-i-1; j++)
	       map[n+i][j] += max(map[n+i-1][j], map[n+i-1][j+1]);

     printf("%d\n",map[n*2-2][0]);
     
     return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5;

int n, m;

int fa[N], size[N];
inline int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
inline bool merge(int x, int y) {
	x = find(x), y = find(y);
	if(x == y) return false;
	fa[x] = y;
	size[y] += size[x];
	size[x] = 0;
	return true;
}

int main() {
	std::scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) fa[i] = 0, size[i] = 1;
	for(int i = 1; i <= m; i++) {
		int x, y;
		std::scanf("%d%d", &x, &y);
		merge(x, y);
	}
	int mx = 0;
	for(int i = 1; i <= n; i++) mx = std::max(mx, size[i]);
	std::printf("%d\n", mx);
	return 0;
}

Measured memory_bytes: 3252
(* O(n^3) *)
let n = read_int ()
let s = read_line ()
let ans = ref 0
let _ =
  for i = 1 to n - 1 do
    let x = String.sub s 0 i in
    let y = String.sub s i @@ n - i in
    let flags = Array.make 128 false in
    let count = ref 0 in
    let f c =
      if not flags.(int_of_char c) then
        (flags.(int_of_char c) <- true;
        try (String.index y c |> ignore; incr count) with
        | _ -> ()) in
    String.iter f x;
    ans := max !ans !count
  done;
  Printf.printf "%d\n" !ans

Measured memory_bytes: 512
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 211;
int d[SIZE][SIZE];
char s[SIZE][SIZE];
int N;
int f(int st){
    int ma=0;
    REP(i,N)REP(j,N){
        if(s[i][j]=='1'){
            if(abs(d[st][i]-d[st][j])!=1)return -1;
        }
    }
    REP(i,N){
        ma=max(ma,d[st][i]);
    }
    return ma+1;
}
int main(){
    R(N);
    REP(i,N)RS(s[i]);
    REP(i,N){
        REP(j,N){
            if(s[i][j]=='1')d[i][j]=1;
            else if(i==j)d[i][j]=0;
            else d[i][j]=SIZE;
        }
    }
    REP(k,N)REP(i,N)REP(j,N){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
    REPP(i,1,N){
        if(d[0][i]>=N){
            W(-1);
            return 0;
        }
    }
    int an=-1;
    REP(i,N){
        an=max(an,f(i));
    }
    W(an);
    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
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 (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

using Graph = vector<vector<int>>;

void dfs1(ll now, ll par, Graph &G, ll d, vector<ll> &dA){
	dA[now] = d;
	for(auto next: G[now]){
		if(next == par) continue;
		dfs1(next, now, G, d+1, dA);
	}
}

ll res = 0;

void dfs2(ll now, ll par, Graph &G, ll d, vector<ll> &dA){
	chmax(res, dA[now]-1);
	if(dA[now]<=d) return;
	for(auto next: G[now]){
		if(next == par) continue;
		dfs2(next, now, G, d+1, dA);
	}
	return;
}

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

    ll N, u, v;
    cin >> N >> u >> v;
    u--, v--;

    Graph G(N);
    REP(i, N-1){
    	ll A, B;
    	cin >> A >> B;
    	A--, B--;
    	G[A].push_back(B);
    	G[B].push_back(A);
    }

    vector<ll> dA(N, 0);

    dfs1(v, -1, G, 0, dA);
    //cout << dA << endl;
    dfs2(u, -1, G, 0, dA);

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 12928
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int a,b,c;
int main(){
  int s,w;
  cin >> s >> w;
  if(s<=w){cout << "unsafe" <<endl;}
  else {cout << "safe" <<endl;}
  return 0;
}

Measured memory_bytes: 3632
import std.stdio, std.range, std.conv, std.string;
import std.algorithm.comparison, std.algorithm.iteration, std.algorithm.mutation, std.algorithm.searching, std.algorithm.setops, std.algorithm.sorting;

void main()
{
    long s = readln().strip.to!(long);
    long[] list;
    list ~= s;
    while(1)
    {
        auto p = list[$-1];
        auto n = p % 2 == 0 ? p/2 : p*3+1;
        foreach(e; list) {
            if(e==n){
                writeln(1+list.length);
                return;
            }
        }
        list ~= n;
    }
}


Measured memory_bytes: 256
import qualified Data.IntMap.Lazy as IM
main = do
  getLine
  nts <- IM.fromList . zip [1..] . map read . words <$> getLine
  getLine
  pxs <- f . map read . words <$> getContents
  mapM_ print [ IM.foldr (+) 0 (IM.union (IM.singleton p x) nts) | (p, x) <- pxs ]
  
f [] = []
f (p:x:pxs) = (p, x) : f pxs

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

int main() {
    int n;
    cin >> n;
    int p[n];
    for(int i=0; i<n; i++) cin >> p[n-i-1];
    int ans = 1, judge = 1;
    int a[n] = {};
    for(int i=0; i<n; i++) {
      a[p[i-1]] = 1;
      if (p[i-1] == judge) {
        ans++;
        while (a[judge]) judge++;
      }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define vll vector<ll>
#define pii pair<ll,ll>
#define sz(v) (v).size()
#define srt(v) sort(v.begin(),v.end())
#define ull unsigned long long
#define tell(a) cout<<a<<" "
#define el cout<<endl
#define rev(v) reverse(v.begin(),v.end())
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ld long double
#define mem(a,b) memset(a,b,sizeof(a) )
#define M 4000010
#define md 1000000007

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;}
/*inline ll add(ll a,ll b){return (a+b)%md;}
inline ll mul(ll a,ll b){return (a*b)%md;}
ll f[M],iv[M];
ll C(ll n,ll r){return mul(f[n],mul(iv[r],iv[n-r]));}
void prep_fac(){
    f[0]=1;
    rep(i,1,M)f[i]=mul(i,f[i-1]);
    iv[M-1]=power(f[M-1],md-2,md);
    for(ll i=M-2;i>=0;--i)iv[i]=mul(i+1,iv[i+1]);
}*/



int main()
{
	IOS;
	int n;
	cin>>n;
	ll a[n];
	rep(i,0,n)cin>>a[i];
	ll ans=0;
	for(int i=1;i<n;i++){
		if(a[i]<a[i-1]){
			ans+=a[i-1]-a[i];
			a[i]+=(a[i-1]-a[i]);
		}
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 5168
#!/usr/bin/python3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(S):
    N = len(S)
    a = 0
    ans = 0
    i = 0
    while i < N:
        if S[i] == 'A':
            a += 1
            i += 1
            continue
        if S[i:i + 2] == 'BC':
            ans += a
            i += 2
            continue
        a = 0
        i += 1
    return ans


def main():
    print(solve(inp()))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3500
#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;

signed main(){
    string s;
    cin >> s;
    int n = s.size();
    if(s[0] == '0' || s[n - 1] == '1'){
        cout << -1 << endl;
        return 0;
    }
    for(int i = 0; i < n / 2; i++){
        if(s[i] != s[n - 2 - i]){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << 1 << " " << 2 << endl;
    int now = 2;
    for(int i = 2; i < n; i++){
        cout << now << " " << i + 1 << endl;
        if(s[i - 1] == '1') now = i + 1;
    }
    return 0;
}

Measured memory_bytes: 1664
"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

# import itertools
# import math

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *H = map(int, read().split())
dp = [0] * N
dp[1] = abs(H[1] - H[0])

for i in range(2, N):
    dp[i] = min(dp[i - k] + abs(H[i] - H[i - k]) for k in [1, 2])

ans = dp[-1]
print(ans)


Measured memory_bytes: 12232
#include <bits/stdc++.h>
#define FOR(I,X,Y) for(int I=X;I<Y;I++)
#define REP(I,X,Y) for(int I=Y-1;I>=X;I--)
#define INF 1000000007
using namespace std;

int main(){
  int N,Y;
  bool ans = 0;
  cin >> N >> Y;
  FOR(i,0,N+1){
    FOR(j,0,N-i+1){
      if(10000*i+5000*j+1000*(N-i-j) == Y){
        ans = 1;
        cout << i << " " << j << " " << N-i-j << endl;
      }
    }
    if(ans)break;
  }
  if(!ans)cout << -1 << " " << -1 << " " << -1 << endl;
}


Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
#define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
inline int safe_mul(const int x, const int y) __attribute__ ((warn_unused_result));


int main() {
//    freopen("in.txt","r", stdin);
//    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n,m,k;
    cin >> n >> m >> k;
    vector<string> a(n);
    for (auto& s : a)
        cin >> s;

    vector<vector<int>> res(n, vector<int>(m));
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i].find('#') != string::npos) {
            ++cnt;
            bool fst = true;
            for (int j = 0; j < m; ++j) {
                if (a[i][j] == '#') {
                    if (!fst)
                        ++cnt;
                    fst = false;
                }
                res[i][j] = cnt;
            }
        }
    }

    for(int j = 0; j < m; ++j) {
        for (int i = 1; i < n; ++i)
            if (res[i][j] == 0 && res[i - 1][j] != 0)
                res[i][j] = res[i - 1][j];
        for (int i = n - 1; i >= 0; --i)
            if (res[i][j] == 0 && res[i + 1][j] != 0)
                res[i][j] = res[i + 1][j];
    }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cout << res[i][j] << " \n"[j == m - 1];
}


Measured memory_bytes: 1280
#include <cmath>
#include <iostream>
#include <vector>

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

int main() {
  int n;
  std::cin >> n;

  auto vals = std::vector<long>(n);

  int maxid = 0;
  rep(i, n) {
    long num;
    std::cin >> num;
    vals[i] = num;
    if (vals[maxid] < vals[i]) maxid = i;
  }

  double sdst = vals[maxid];
  long p = 0;
  rep(i, n) {
    if (i == maxid) continue;
    double dst = abs(vals[maxid] / 2.0 - vals[i]);
    if (dst < sdst) {
      sdst = dst;
      p = vals[i];
    }
  }

  std::cout << vals[maxid] << " " << p << std::endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,D,E,F;
  cin >> A >> B >> C >> D;
  E = A+B;
  F = C+D;
  if (E>F) {
 	 cout << "Left"  << endl;
  }
  if(E == F){
    cout << "Balanced"  << endl;
  }
  if (E<F) {
 	 cout << "Right"  << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct dish
{
    int a;
    int b;
}t[5];

bool cmp(dish x, dish y)
{
    return x.b < y.b;
}

int main()
{
    int ans = 0;
    for(int i = 0; i < 5; ++i)
    {
        scanf("%d", &t[i].a);
        if((t[i].a % 10) != 0)
            t[i].b = (t[i].a / 10 + 1) * 10 - t[i].a;
        else
            t[i].b = 0;
        ans += t[i].a;
    }
    sort(t, t + 5, cmp);
    int sum = 0;
    for(int i = 0; i < 4; ++i)
        sum += t[i].b;
    printf("%d\n", sum+ans);
    return 0;
}


Measured memory_bytes: 384
H, W = map(int, input().split())

field = []
dist = [[float('inf')] * (W * H) for h in range(W * H)]

for _ in range(H):
    field.append(input())

weight = 1
for i in range(H):
    for j in range(W):
        if j + 1 < W and field[i][j] == '.' and field[i][j + 1] == '.':
            dist[W * i + j][W * i + j + 1] = weight
            dist[W * i + j + 1][W * i + j] = weight
        if i + 1 < H and field[i][j] == '.' and field[i + 1][j] == '.':
            dist[W * i + j][W * (i + 1) + j] = weight
            dist[W * (i + 1) + j][W * i + j] = weight


def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


warshall_floyd(dist)

ans = 0
for i in range(H * W):
    for j in range(i + 1, H * W):
        if dist[i][j] != float('inf'):
            ans = max(ans, dist[i][j])

print(ans)


Measured memory_bytes: 133472
n=int(input())
s=input()
ans=0
for i in range(1,n-1):
    a=s[:i]
    b=s[i:]
    c=0
    for j in range(97,97+26):
        if a.count(chr(j))!=0 and b.count(chr(j))!=0:
            c+=1
    if c>ans:
        ans=c
print(ans)


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

using pii = pair<int, int>;
using ll = long long;

int main() {
    int N, C;
    cin >> N >> C;
    vector<vector<int>> v(C, vector<int>(200010));
    for(int i = 0; i < N; ++i) {
        int s, t, c;
        cin >> s >> t >> c;
        v[c - 1][s * 2] += 1;
        v[c - 1][t * 2] += -1;
    }
    for(int i = 0; i < C; ++i) {
        for(int j = 0; j < v[i].size(); ++j) {
            if(v[i][j] == 1) {
                v[i][j - 1] = 1;
                v[i][j] = 0;
            }
        }
    }
    int cnt = 0;
    int res = 0;
    for(int i = 0; i < 200010; ++i) {
        int inc = 0, dec = 0;
        for(int j = 0; j < C; ++j) {
            inc += v[j][i] == 1;
            dec += v[j][i] == -1;
        }
        if(inc > cnt) {
            res += inc - cnt;
            cnt = 0;
        } else {
            cnt -= inc;
        }
        cnt += dec;
    }
    cout << res << endl;
}


Measured memory_bytes: 24576
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

int n,m;
vector<string>a;
vector<vector<int> > rig,dow;

bool valid(int i, int j){
	if(i <= 0 || j<=0) return 0;
	if(i > n || j > m) return 0;
	return 1;
}
int dp[200][200][2];

int f(int i, int j, int bad){
	// cout<<i<<" "<<j<<endl;
	if(i==n && j == m){
		return 0;
	}
	if(dp[i][j][bad] != -1){
		return dp[i][j][bad];
	}
	int ans = INT_MAX;
	if(valid(i+1,j)){
		if(a[i+1][j] == '.'){
			ans = min(ans, f(i+1,j,0));
		}	
		else{
			ans = min(ans, (1-bad)+f(i+1,j,1));
		}
	}
	if(valid(i,j+1)){
		if(a[i][j+1] == '.'){
			ans = min(ans, f(i,j+1,0));
		}	
		else{
			ans = min(ans, (1-bad)+f(i,j+1,1));
		}
	}
	dp[i][j][bad] = ans;
	return ans;
}

int main(){
	fastread;
	cin>>n>>m;
	memset(dp,-1,sizeof(dp));
	string b(m+1,'.');
	a.pb(b);
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		s = '.'+s;
		a.pb(s);
	}

	cout<<min(f(0,1,0),f(1,0,0))<<endl;
	return 0;
}


Measured memory_bytes: 640
n,m = (int(x) for x in input().split())
#S = []
#C = []
x = [-1] * n
res = -1
for i in range(m):
    s,c = (int(a) for a in input().split())
    #S.append(s)
    #C.append(c)
    if not(x[s-1] == -1) and not(x[s-1] == c):
        break
    else:
        x[s-1] = c
else:
    if x[0] != 0 or n == 1:
        res = 0
        for i in range(len(x)):
            if x[i] == -1 :
                if i != 0 or n == 1:
                    th = 0
                else:
                    th = 1
            else:
                th = x[i]
            res *= 10
            res += th
        
print(res)

    




Measured memory_bytes: 3064
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
        int a = sc.nextInt();
        String op = sc.next();
        int b = sc.nextInt();
            if(op.equals("+")) 
                System.out.println(a+b);
            if(op.equals("-"))
                System.out.println(a-b);
            if(op.equals("*"))
                System.out.println(a*b);
            if(op.equals("/"))
                System.out.println(a/b);
            if(op.equals("?"))
                break;
        }
        sc.close();
    }
}


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

#define endl "\n"
#define all(x) x.begin(),x.end()
#define pb push_back
#define ff first 
#define ss second 
#define pii pair<int,int>
#define vi vector<int>
#define vc vector<char>
#define vii vector<pii>
#define vvi vector<vi>
#define fori(i,n) for(int i=1;i<=n;++i)
#define forn(i,n) for(int i=0;i<n;++i)
#define sz(x) int(x.size())
#define error(x) cout<<#x<<" "<<x<<endl
#define IOS  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N=100*1000;
const int mod=1e9+7;

int min3(int a,int b,int c){return min(a,min(b,c));}
int max3(int a,int b,int c){return max(a,max(b,c));}
int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

#define int int64_t
int a[N+2];
int dp[N+2][2];
int32_t  main(){
	IOS;
  int n;cin>>n;
  fori(i,n)cin>>a[i];
  memset(dp,0,sizeof(dp));
  dp[1][0]=a[1];
  dp[1][1]=-a[1];
  for(int i=2;i<n;++i){
    dp[i][0]=max(dp[i-1][0]+a[i],dp[i-1][1]-a[i]);
    dp[i][1]=max(dp[i-1][0]-a[i],dp[i-1][1]+a[i]);
  }
  cout<<max(dp[n-1][0]+a[n],dp[n-1][1]-a[n])<<endl;
  return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define lc (rt << 1)
#define rc (rt << 1) | 1
using namespace std;
typedef long long LL;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

int n, a[MAXN], mx[MAXN];

struct SegmentTree {
	int seg[MAXN << 2];
	
	void Update(int rt, int b, int e, int p, int v) {
		if (b == e) {
			seg[rt] = v;
			return;
		}
		int mid = (b + e) >> 1;
		if (p <= mid) Update(lc, b, mid, p, v);
		else Update(rc, mid + 1, e, p, v);
		seg[rt] = max(seg[lc], seg[rc]);
	}
	
	int Query(int rt, int b, int e, int l, int r) {
		if (l <= b && e <= r) return seg[rt];
		int mid = (b + e) >> 1;
		if (r <= mid) return Query(lc, b, mid, l, r);
		if (l > mid) return Query(rc, mid + 1, e, l, r);
		return max(Query(lc, b, mid, l, r), Query(rc, mid + 1, e, l, r));
	}
} T1, T2;

bool Try(int p, int m1, int m2, int c1, int c2) {
	int need = c1 + mx[p] - c2;
	if (need >= 0 && (need & 1? T1 : T2).Query(1, 1, n, m2, n) >= need) return 1;
	need = c2 + mx[p] - c1;
	if (need >= 0 && (need & 1? T1 : T2).Query(1, 1, n, m1, n) >= need) return 1;
	return 0;
}

void init() {
	read(n);
	for (int i = 1, b = 0; i <= n; ++i) {
		read(a[i]);
		if (a[i] > b) mx[i] = 1;
		b = max(b, a[i]);
	}
	for (int i = n; i >= 1; --i) {
		mx[i] += mx[i + 1];
	}
}

void solve() {
	mset(T1.seg, 0x80);
	for (int i = n; i >= 1; --i) {
		int v1 = T1.Query(1, 1, n, a[i], n);
		int v2 = T2.Query(1, 1, n, a[i], n);
		T1.Update(1, 1, n, a[i], (mx[i] > mx[i + 1]? v1 + 2 : v2 + 1));
		T2.Update(1, 1, n, a[i], (mx[i] > mx[i + 1]? v2 + 2 : v1 + 1));
	}
	int m1 = 1, m2 = 1, c1 = 0, c2 = 0;
	string ans;
	for (int i = 1; i <= n; ++i) {
		T1.Update(1, 1, n, a[i], -INF);
		T2.Update(1, 1, n, a[i], 0);
		if (Try(i + 1, max(m1, a[i]), m2, c1 + (a[i] >= m1), c2)) {
			ans += '0';
			c1 += (a[i] >= m1);
			m1 = max(m1, a[i]);
		} else {
			ans += '1';
			c2 += (a[i] >= m2);
			m2 = max(m2, a[i]);
		}
	}
	if (c1 == c2) cout << ans << endl;
	else puts("-1");
}

int main() {
	init();
	solve();
	return 0;
}


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

using namespace std;

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

    string s;
    cin >> s;

    int ans = 1;

    for (int i=1; i<n; i++){
        char pre_s = s[i-1];
        if (pre_s != s[i])
            ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 760
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main(void)
{
	ll n,k;
	scanf("%lld%lld",&n,&k);
	ll sum1=0;
	for(ll i=k;i<=n+1;i++)
	{
		ll a=0,b=i-1;
		ll c=n-i+1,d=n;
		ll x=(a+b)*i/2;
		ll y=(c+d)*i/2;
		sum1+=y-x+1;
	}
	sum1=sum1%mod;
	sum1=(sum1+mod)%mod;
	printf("%lld",sum1);
}

Measured memory_bytes: 3824
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  int N;
  cin >> N;

  vector<int> A(N);
  REP(i, N) cin >> A[i];
  
  sort(ALL(A), greater<int>());

  map<int, int> m;
  REP(i, N) m[A[i]]++;

  int cur = 2;
  while(cur <= A[0]) cur *= 2;

  int ans = 0;
  for(int i : A){
    if(m[i] == 0) continue;
    while(i*2 < cur) cur /= 2;

    if(i == cur-i){
      if(m[i] >= 2){
        m[i] -= 2;
        ans++;
      }
    }else if(m[cur-i] >= 1){
      m[i]--; m[cur-i]--;
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 26752
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner s=new Scanner(System.in);
    char[] sa= s.next().toCharArray();
    char[] sb= s.next().toCharArray();
    char[] sc= s.next().toCharArray();

    int i1=0;
    int i2=0;
    int i3=0;
    char next='a';
    while(true) {
      if(next=='a') {
        if(i1==sa.length) {
          System.out.println("A");
          break;
        }
        next=sa[i1++];
      }

      if(next=='b') {
        if(i2==sb.length) {
          System.out.println("B");
          break;
        }
        next=sb[i2++];
      }

      if(next=='c') {
        if(i3==sc.length) {
          System.out.println("C");
          break;
        }
        next=sc[i3++];
      }
    
      
    }

  }
}

Measured memory_bytes: 21844