akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>

const int max_n = 100000;

int n;
char s[max_n + 1];

char test(char type, char middle, char other) {
    if (middle == 'S') {
        return type == 'o' ? other : (other == 'S' ? 'W' : 'S');
    }
    else {
        return type == 'x' ? other : (other == 'S' ? 'W' : 'S');
    }
}

bool check(char a, char b) {
    char r[max_n + 1];
    
    r[0] = a;
    r[1] = b;
    
    for (int i = 2; i < n; i++) {
        r[i] = test(s[i - 1], r[i - 1], r[i - 2]);
    }
    
    if (r[n - 1] != test(s[0], r[0], r[1])) {
        return false;
    }
    if (r[n - 2] != test(s[n - 1], r[n - 1], r[0])) {
        return false;
    }
    
    r[n] = '\0';
    
    printf("%s\n", r);
    
    return true;
}

int main() {
    scanf("%d", &n);
    scanf("%s", s);
    
    if (!(check('W', 'W') || check('W', 'S') || check('S', 'W') || check('S', 'S'))) {
        printf("-1\n");
    }
    
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7;

int a[100005], b[45], _sum[45];
int *sum = _sum + 1;

int32_t main()
{
	IO_OP;
	
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < 40; i++)
		for (int j = 0; j < n; ++j)
			b[i] += a[j] >> i & 1;
	for(int i = 0; i < 40; i++)
		sum[i] = sum[i - 1] + max(b[i] << i, (n - b[i]) << i);
	int p = k ? __lg(k) + 1 : 1 , ans = 0, s = 0;
	for (int i = p - 1; i >= 0; --i) {
		if (k >> i & 1)
			ans = max(ans, s + (b[i] << i) + sum[i - 1]);
		s += (k >> i & 1) ? (n - b[i]) << i : b[i] << i;
	}
	ans = max(ans, s);
	for (int i = p; i < 40; ++i)
		ans += b[i] << i;
	cout << ans << endl;
}



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


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int n;
	cin >> n;
	vector<vector<int>> h(3, vector<int>(n));
	for (int i = 0; i < n; ++i) 
		cin >> h[0][i] >> h[1][i] >> h[2][i];

	vector<vector<int>> dp(n, vector<int>(3));

	for (int i = 0; i < 3; ++i) dp[0][i] = h[i][0];

	for (int i = 1; i < n; ++i) 
		for (int j = 0; j < 3; ++j) {
			int mx = 0;
			for (int k = 0; k < 3; ++k) {
				if (j != k) 
					mx = max(mx, dp[i - 1][k]);
			}
			dp[i][j] = mx + h[j][i];
		}

	cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << endl;
}



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

using ll = long long;

void solve(long long a, long long b, long long c, long long d){
    ll ans = max({a * c, a * d, b * c, b * d});
    cout<<ans<<endl;
}

int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long c;
    scanf("%lld",&c);
    long long d;
    scanf("%lld",&d);
    solve(a, b, c, d);
    return 0;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
#define N 100005
#define LL long long 
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
using namespace std;
LL int n,sum,c,m;
//~ void f2(int a,int b)
//~ {
	
//~ }
LL int  calc(LL int a,LL int b)
{
	if(!b)
		return 0;
	LL int tut1,tut2;
	//~ f2(a,b);
	tut1=a;
	tut2=b;
	a=max(tut1,tut2);
	b=min(tut1,tut2);	
	
	LL int tut=a/b;
	if(a%b==0)
		return 2*tut*b-b;
	return tut*2*b+calc(b,a%b);
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	sum+=n;
	sum+=calc(n-m,m);
	cout<<sum;
}


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

#define rep(i,n) for(ll i=0;i<(n);++i)
#define reps(i,n) for(ll i=1;i<=(n);++i)
using ll = long long;
using str = string;
constexpr long long INF = (1LL<<60);
constexpr long long MOD = (1e9+7);
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
inline void dump(){cout<<endl;}
template<class Head,class... Tail>inline void dump(Head&& head, Tail&&... tail){cout<<head<<", ";dump(forward<Tail>(tail)...);}
template<typename T>inline istream &operator>>(istream&input,vector<T>&v){for(auto &elemnt:v)input>>elemnt;return input;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}

main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);

  string s;
  ll k;
  cin>>s>>k;
  ll n = s.size();

  bool all_eq=true;
  rep(i,n-1){
    if(s[i]!=s[i+1])all_eq=false;
  }
  if(all_eq){
    cout<<n*k/2<<endl;
  }
  else{
    if(s[0]==s.back()){
      string t=s;
      ll a=1,b=1,c=0,ai,bi;
      rep(i,n-1){
        if(s[i]==s[i+1]){
          a++;
          //s[i+1]='#';
        }
        else {
          ai=i;
          break;
        }
      }
      for(ll i=n-1;i>0;--i){
        if(s[i]==s[i-1]){
          b++;
          //s[i]='#';
        }
        else {
          bi=i;
          break;
        }
      }
      ll cnt=0;
      rep(i,n-1){
        if(t[i]==t[i+1]){
          t[i+1]='#';
          cnt++;
        }
      }
      //dump(cnt,a,b);
      cnt*=k;
      ll ans=cnt;
      ans -= (k-1)*(a/2+b/2-(a+b)/2);
      cout<<(ans)<<endl;
    }
    else{
      ll ans=0;
      rep(i,n-1){
        if(s[i]==s[i+1]){
          ans++;
          s[i+1]='#';
        }
      }
      ans*=k;
      cout<<(ans)<<endl;
    }
  }


}


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

int a[110];

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

	int n;
	cin >> n;

	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}

	int cnt = 0;
	bool flag = true;
	while(flag){
		flag = false;
		for(int i = n - 1; i >= 1; --i){
			if(a[i] < a[i - 1]){
				++ cnt;
				swap(a[i], a[i - 1]);
				flag = true;
			}
		}
	}

	for(int i = 0; i < n; ++i){
		cout << a[i];
		if(i != n - 1)
			cout << " ";
		else
			cout << endl;
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define db long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define EB emplace_back
#define fi first
#define se second
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?x-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
 
#define INF ((1ll<<60)-233)
#define sqr(x) ((x)*(x))
#define debug puts("wzpkking")
using namespace std;
 
const int N=505;
const int LIM=8000;
int fl[LIM],pri[LIM],n;
void initprime(){
	For(i,2,LIM-1) For(j,2,(LIM-1)/i) fl[i*j]=1;
	For(i,1,LIM-1) if (!fl[i]) pri[++*pri]=i;
}
map<int,int> mp1,mp2;
map<ll,int> mp3;
ll ans[N][N];
ll gcd(ll x,ll y){
	return y?gcd(y,x%y):x;
}
void work(){
	int l=2;
	For(i,0,n-1) if ((n+1-i)&1){
		mp1[n+1-i]=pri[l++];
		if (i) mp1[n+1+i]=pri[l++];
		if (l>235) l=2;
	}
	l=2;
	For(i,1,n-1) if (i&1){
		mp2[i]=pri[l++];
		if (i) mp2[-i]=pri[l++];
		if (l>235) l=2;
	}	
	For(i,1,n) For(j,1,n) if ((i+j)&1){
		int v=mp1[i+j]*mp2[i-j]; ans[i][j]=v;
		assert(v);
		for (;mp3[ans[i][j]];ans[i][j]+=v);
		mp3[ans[i][j]]++;
	}
	ll mx=0;
	For(i,1,n) For(j,1,n) if (!ans[i][j]){
		ll lcm=1;
		if (i!=1) lcm*=ans[i-1][j]/gcd(ans[i-1][j],lcm);
		if (i!=n) lcm*=ans[i+1][j]/gcd(ans[i+1][j],lcm);
		if (j!=1) lcm*=ans[i][j-1]/gcd(ans[i][j-1],lcm);
		if (j!=n) lcm*=ans[i][j+1]/gcd(ans[i][j+1],lcm);
		ans[i][j]=lcm+1;
		for (;mp3[ans[i][j]];ans[i][j]+=lcm);
		mp3[ans[i][j]]=1;
		mx=max(mx,ans[i][j]);
	}
	For(i,1,n){
		For(j,1,n) printf("%lld ",ans[i][j]);
		puts("");
	}
}
 
int main(){
	scanf("%d",&n);
	initprime();
	work();
}

Measured memory_bytes: 20224
a,b = map(int,input().split())

x = 0

if a >= b:
  x += a
  if (a-1) >= b:
    x += (a-1)
  else:
    x += b
else:
  x = b
  if (b-1) >= a:
    x += (b-1)
  else:
    x += a

print(x)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int n, k, mod;
int dp[310][310], s[310][310];
int C[310][310];
int main() {
    scanf("%d%d%d", &n, &k, &mod);
    for (int i = 0; i <= n; i++) {
        C[i][i] = C[i][0] = 1;
        for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    for (int i = 0; i <= k; i++) dp[1][i] = 1;
    for (int i = 2; i <= n + 1; i++) {
        for (int j = k; j >= 0; j--) s[i - 1][j] = (dp[i - 1][j] + s[i - 1][j + 1]) % mod;
        for (int j = 0; j <= k; j++) {
            for (int f = 1; f < i; f++) dp[i][j] = (dp[i][j] + 1ll * dp[i - f][j] * s[f][j + 1] % mod * C[i - 2][f - 1]) % mod;
        }
    }
    return cout << dp[n + 1][0] << endl, 0;
}

Measured memory_bytes: 1408
import java.util.Scanner;

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

        if(A==B && A==C ){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21844
#include<stdio.h>
#include<math.h>
int n,m;
int a[55],b[55],c[55],d[55],x,min,ans;
int main(){
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a[i],&b[i]);	
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d",&c[i],&d[i]);	
	}

	for(int i=1;i<=n;i++){//第i个学生
		min=999999999;
		
		for(int j=1;j<=m;j++){//第j个检查站
			x=abs(a[i]-c[j])+abs(b[i]-d[j]);
			if(x<min){
				min=x;
				ans=j;
			}
		}
		printf("%d\n",ans);
	}	
}


Measured memory_bytes: 128
#include <stdio.h>
int main()
{
  int n,a[100],i,key,j,k;

  scanf("%d",&n);

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

  for(i=0; i<n; i++){
    key = a[i];
    j = i-1;

    while(j>=0 && a[j]>key){
      a[j+1]=a[j];
      j--;
    }
    a[j+1] = key;

    for(k=0; k<n; k++){
      if(k==0) printf("%d",a[k]);
      else printf(" %d",a[k]);
    }
      printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2072
#include <cstdio>
#include <cmath>

int max(int a, int b) {
    return a > b ? a : b;
}

int main(int argc, char const *argv[]) {
    int A, B;
    scanf("%d%d", &A, &B);
    int a[5];
    int b[5];
    int _A = A;
    int _B = B;
    for (int i = 4; i >= 0; i--) {
        a[4 - i] = _A / (int)pow(10, i);
        _A -= a[4 - i]*(int)pow(10, i);
        b[4 - i] = _B / (int)pow(10, i);
        _B -= b[4 - i]*(int)pow(10, i);
        // printf("%d\n", b[4 - i]);
    }
    int r = max(0, b[0] - a[0] - 1) * 100;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            int q = a[0] * (int)pow(10, 4);
            q += i * (int)pow(10, 3);
            q += j * (int)pow(10, 2);
            q += i * (int)pow(10, 1);
            q += a[0] * (int)pow(10, 0);
            if (q >= A && q <= B) {
                r++;
                // printf("%d\n", q);
            }

            if (a[0] == b[0]) continue;

            int q2 = b[0] * (int)pow(10, 4);
            q2 += i * (int)pow(10, 3);
            q2 += j * (int)pow(10, 2);
            q2 += i * (int)pow(10, 1);
            q2 += b[0] * (int)pow(10, 0);
            if (q2 <= B) {
                r++;
                // printf("%d\n", q2);
            }
        }
    }
    printf("%d\n", r);
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
inline int query(string S) {
	cout << "? " << S << endl;
	int res;
	cin >> res;
	return res;
}
int main() {
	string A;
	for (int i = 0; i < 26; i++) A += (char)(i + 'a');
	for (int i = 0; i < 26; i++) A += (char)(i + 'A');
	for (int i = 0; i < 10; i++) A += (char)(i + '0');
	vector<string> buck;
	int len = 0;
	for (int i = 0; i < 62; i++) {
		int x = 128 - query(string(128, A[i]));
		if (x) buck.push_back(string(x, A[i]));
		len += x;
	}
	while ((int)buck.size() > 1) {
		sort(buck.begin(), buck.end(), [](string s1, string s2) {
			return s1.size() > s2.size();
		});
		string s = buck.back(); buck.pop_back();
		string t = buck.back(); buck.pop_back();
		string st;
		while (s.size() && t.size()) {
			string nstr = st + t[0] + s;
			if ((int)nstr.size() + query(nstr) == len) {
				st += t[0];
				t.erase(t.begin());
			} else {
				st += s[0];
				s.erase(s.begin());
			}
		}
		if (s.size()) st += s;
		else st += t;
		buck.push_back(st);
	}
	cout << "! " << buck[0] << endl;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int a[110], sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    sum += a[i];
  }

  double average = (double)sum / N;

  int ans = 10000;
  double dif = 10000.0;
  for (int i = 0; i < N; i++) {
    if (abs(average - a[i]) < dif) {
      dif = abs(average - a[i]);
      ans = i;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
	public static int a[];
	public static String b[];
	public static int p[]=new int[9];
	public static String p2[]=new String[9];
	public static boolean judge;
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		int I=in.nextInt();
		while(I-->0)
		{
			a=new int[9];
			b=new String[9];
			judge=false;
			boolean use[]=new boolean[9];
			for(int i=0;i<9;i++)
				a[i]=in.nextInt();
			for(int i=0;i<9;i++)
				b[i]=in.next();

			make_perm(0,p,p2,use);
			System.out.println(judge ? 1:0);
		}
	}

	static void make_perm(int n,int p[],String p2[],boolean use[])
	{
		if(judge)
			return;
		if(n==9)
			check(p,p2);
		else 
		{
			for(int i=0;i<9;i++)
			{

				if(use[i]) 
					continue;
				p[n]=a[i];
				p2[n]=b[i];
				use[i] = true;
				make_perm(n+1,p,p2,use);
				use[i] = false;
			}
		}
	}

	static void check(int p[], String p2[])
	{
		if((p[0]+1==p[1]&&p[1]+1==p[2])||(p[0]==p[1]&&p[1]==p[2]))
		{
			if(p2[0].equals(p2[1])&&p2[1].equals(p2[2]))
				judge=true;
			else
				return;
		}
		else 
		{
			judge=false;
			return;
		}
		if(p[3]+1==p[4]&&p[4]+1==p[5]||(p[3]==p[4]&&p[4]==p[5]))
		{
			if(p2[3].equals(p2[4])&&p2[4].equals(p2[5]))
				judge=true;
			else
			{
				judge=false;
				return;
			}
		}
		else
		{
			judge=false;
			return;
		}
		if(p[6]+1==p[7]&&p[7]+1==p[8]||(p[6]==p[7]&&p[7]==p[8]))
		{
			if(p2[6].equals(p2[7])&&p2[7].equals(p2[8]))
				judge=true;
			else
			{
				judge=false;
				return;
			}
		}
		else
		{
			judge=false;
			return;
		}
	}

	static public void debug(Object... o)
	{
		System.out.println(Arrays.deepToString(o));
	}
}

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

char num[100];

main()
{
	scanf("%s",num);
	if(num[0]=='1')
	{
		int zero_c=1;
		for(int i=1;num[i];i++)
		{
			if(num[i]!='0')
			{
				zero_c=0;
				break;
			}
		}
		if(zero_c==1)
		{
			printf("10\n");
			return 0;
		}
	}
	int ans=0;
	for(int i=0;num[i];i++)
	{
		ans+=num[i]-'0';
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;


int main(void){
  int k,s,i,r,ans=0;
  
  cin >> k >> s;
  
  for (i=0;i<=min(k,s);i++){
    r=s-i;
    ans+=max(0,min(k,r)-max(0,r-k)+1);
  }
  
  cout << ans << endl;
  
  return 0;
}

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

for i in range(N):
    p_arr[i] -= 1

a_arr = [N*i + 1 for i in range(N)]
b_arr = [0]*N
for i in range(N):
    b_arr[p_arr[i]] = N*(N - p_arr[i]) + i + 1

a_output = ""
b_output = ""
for i in range(N):
    a_output += str(a_arr[i])
    b_output += str(b_arr[i])
    if i == N-1:
        continue
    else:
        a_output += " "
        b_output += " "

print(a_output)
print(b_output)


Measured memory_bytes: 6708
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    static long ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            int temp = Integer.parseInt(sc.next());
            a[i] = temp;
        }
        Map<Integer, Integer> map = new HashMap<>();
        long ans = 0;
        for (int i = 0; i < n - 1; i++) {
            map.merge(i + a[i], 1, Integer::sum);
        }
        for (int i = 1; i < n; i++) {
            if (map.containsKey(i - a[i])) {
                ans += map.get(i - a[i]);
            }
        }
        System.out.println(ans);
    }
}

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

/* Struct Declaration */
typedef struct card {
  char p;
  int num;
}Card;

/* Prototype Declaration */
int partition(Card *, int, int);
void quickSort(Card *, int, int);
void merge(Card *, int, int, int);
void mergeSort(Card *, int, int);

/* Global Variable */
Card L[(MAX/2)+1], R[(MAX/2)+1]; 
int n;

int main() {
  int i, flag = 0;
  char picture[2];
  Card A[MAX], B[MAX];

  //Input and Copy
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) {
    scanf("%s %d", picture, &A[i].num);
    A[i].p = picture[0];
    B[i].p = picture[0];
    B[i].num = A[i].num;
  }

  //Sort
  quickSort(A, 0, n - 1);
  mergeSort(B, 0, n);

  //Compare
  for ( i = 0; i < n; i++ ) {
    if ( A[i].p != B[i].p ) flag = 1;
  }

  //Output
  for ( i = 0; i < n; i++ ) {
    if ( flag == 1) {
      printf("Not stable\n");
      flag = -1;
    }else if ( flag == 0 ) {
      printf("Stable\n");
      flag = -1;
    }

    printf("%c %d\n", A[i].p, A[i].num);
  }

  return 0;
}

/* Partition */
int partition(Card *A, int p, int r) {
  Card x, temp;
  int i, j;

  x = A[r];
  i = p - 1;

  for ( j = p; j < r; j++ ) {
    if ( A[j].num <= x.num ) {
      i++;
      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
  }
  temp = A[i+1];
  A[i+1] = A[r];
  A[r] = temp;

  return i + 1;
}

/* Quick Sort */
void quickSort(Card *A, int p, int r) {
  int q;
  if ( p < r ) {
    q = partition(A, p, r);
    quickSort(A, p, q - 1);
    quickSort(A, q + 1, r);
  }
}

/* Merge */
void merge(Card *B, int left, int mid, int right){
  int n1, n2;
  int i, j, k;

  n1 = mid - left;
  n2 = right - mid;

  for ( i = 0; i < n1; i++ ) L[i] = B[i+left];
  for ( i = 0; i < n2; i++ ) R[i] = B[i+mid];

  L[n1].num = 1000000500;
  R[n2].num = 1000000500;

  i = 0;
  j = 0;

  for ( k = left; k < right; k++ ) {
    if ( L[i].num <= R[j].num ) {
      B[k] = L[i];
      i++;
    }else {
      B[k] = R[j];
      j++;
    }
  }

}

/* Merge Sort */
void mergeSort(Card *B, int left, int right) {
  int mid;
  
  if ( left + 1 < right ) {
    mid = (left + right) / 2;
    mergeSort(B, left, mid);
    mergeSort(B, mid, right);
    merge(B, left, mid ,right);
  }
}

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

#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 (int i=0    ;i<(n) ;i++)
#define RREP(i,n)     for (int i=(n)-1;i>=0  ;i--)
#define EACH(i,a,b)   for (int i=(a)  ;i<=(b);i++)
#define REACH(i,a,b)  for (int i=(b)  ;i>=(a);i--)
#define ALL(a)        (a).begin(),  (a).end()
#define RALL(a)       (a).rbegin(), (a).rend()

const int MOD = 1e9 + 7;
const int INF = 1 << 29;
const double EPS = 1e-10;

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

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

  int K,N;
  cin >> K >> N;
  int A[N+1];
  REP(i,N) cin >> A[i];
  A[N] = K + A[0];

  int maxlen = 0;
  REP(i,N) maxlen = max(maxlen, A[i+1] - A[i]);

  cout << K - maxlen << endl;

  return 0;
}



Measured memory_bytes: 4416
import bisect

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

cnt = 0
#S.sort()
for i in T:
    index = bisect.bisect_left(S, i)
    if index >= len(S):
        continue
    if S[bisect.bisect_left(S, i)] == i:
        cnt += 1
print(cnt)



Measured memory_bytes: 16736
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main(){
  double m;
  int n;

  while(true){
    cin>>n;
    if(n==0)break;
    double s[1000] = {};
    m = 0;
    for(int i=0; i<n; i++){
      cin >> s[i];
      m+=s[i];
    }
    m/=n;

    double sum_sq=0;
    for(int i=0; i<n; i++){
      sum_sq += pow(s[i] - m, 2);
    }
    cout << fixed << setprecision(8);
    cout << sqrt(sum_sq/n) << endl;
    }
}


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

int main()
{
    int N;
    cin >> N;
    int max = 0;
    int max_i = 0;
    for (int i=1; i<=N; i++) {
        int count = 0;
        int j = i;
        while (j % 2 == 0 && j != 0) {
            j /= 2;
            count ++;
        }
        if (count >= max)  {
            max = count;
            max_i = i;
        }
    }
    cout << max_i << endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
aa = a[:]
sa = list(sorted(a))
upper = sa[n//2]
down = sa[(n//2)-1]
mid = n//2

for i in range(n):
  if aa[i] <= down:
    print(upper)
  else:
    print(down)

Measured memory_bytes: 25556
def main():
    a1, a2, a3 = map(int, input().split())

    # 愚直に解くと3点のうち、1点とその他の点の距離を求める。これの最小化
    # 1,2,3 ならmax-min(中央との距離)
    # 3-1, 2-1 ではない(これはminとの距離、maxでも同様
    ans = max([a1,a2,a3]) - min([a1, a2, a3])
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;
typedef long long ll;


const int N=1e5+100;


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


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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;

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

    vector<pair<int,int>>j(n);
    rep(i,n){
        int x,l;
        cin>>x>>l;
        j[i].first=x+l;
        j[i].second=x-l;
    }

    sort(j.begin(),j.end());
    
    int ans=0, R=-mod;

    rep(i,n){
        if(R<=j[i].second){
            ans++;
            R=j[i].first;
        }
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
from itertools import count

n = int(input())

dp = [0]*(n+1)

def it(n):
  yield 1
  m = 6
  while m <= n:
    yield m
    m *= 6
  m = 9
  while m <= n:
    yield m
    m *= 9

for i in range(1,n+1):
  dp[i] = min(dp[i-t] for t in it(i))+1

print(dp[n])



Measured memory_bytes: 3828
n=int(input())
a=list(map(int,input().split()))

min=a[0]
max=a[0]
sum=a[0]
num=1
while True:
    if num==n:
        break
    if a[num]>max:
        max=a[num]
    if a[num]<min:
        min=a[num]
    sum=sum+a[num]
    num+=1
    

print("%d %d %d"%(min,max,sum))


Measured memory_bytes: 6592
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define lli long long int
#define llu unsigned long long int
#define pb push_back
#define rt return 0
#define endln "\n"
#define all(x) x.begin(), x.end()
#define sz(x) (lli)(x.size())
const lli MOD = 1e9 + 7;
const double PI = 2 * acos(0.0);
// cout << fixed << setprecision(0) << pi <<endl;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// for multiset
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

void solve() {
    lli n, a;
    cin >> n;
    if (n >= 1800) {
        cout << "1" << endl;
    } else if (n >= 1600) {
        cout << "2" << endl;
    } else if (n >= 1400) {
        cout << "3" << endl;
    } else if (n >= 1200) {
        cout << "4" << endl;
    } else if (n >= 1000) {
        cout << "5" << endl;
    } else if (n >= 800) {
        cout << "6" << endl;
    } else if (n >= 600) {
        cout << "7" << endl;
    } else {
        cout << "8" << endl;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // lli t; cin >> t; while(t--)
    solve();
    rt;
}

Measured memory_bytes: 3648
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 998244353;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll d,s,t; cin >> d >> t >> s;
  if(d <= t*s) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  
}

Measured memory_bytes: 3624
#include<stdio.h>
#define NUM 100

int main(void)
{
  char dance[NUM];
  int i;
  int ans1 = 1,ans2 = 1;
  int l = 0;
  
  scanf("%s",dance);
  
  for(i = 0;dance[i] != '\0';i++){
    l++;
  }

    
  
  for(i = 0;i <= l;i = i + 2){
    if(dance[i] == 'L'){
      ans1 = 0;
      break;
    }
  }
  
  for(i = 1;i <= l;i = i + 2){
    if(dance[i] == 'R'){
      ans2 = 0;
      break;
    }
  }
  
  if((ans1 == 1)&&(ans2 == 1)){
    printf("Yes\n");
  }
  
  else{
    printf("No\n");
  }
  
  return 0;
}
  

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
ll n;
//区間スケジュール問題
//締め切りが早いものから順にやっていく
int main(){
    cin>>n;
    vector<pair<int,int>> v;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        v.push_back(make_pair(b,a));   
    }
    sort(v.begin(),v.end());
    int now=0;
    for(int i=0;i<v.size();i++){
        int cost=v[i].second;
        int due=v[i].first;
        if(cost+now>due){
            cout<<"No"<<endl;
            return 0;
        }
        now+=cost;
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 2548
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;

int calc(int num){ // 1 + .. + num
  return (1+num)*num/2;
}

int main(){
  int a, b;cin>>a>>b;
  cout << calc(b-a)-b << endl;
}


Measured memory_bytes: 256
N,M = map(int,input().split())

l_max = 1
r_min = N
for i in range(0,M):
    l,r = map(int,input().split())
    if l_max < l:
        l_max = l
    if r_min > r:
        r_min = r

if l_max > r_min:
    print(0)
else:
    print(r_min-l_max+1)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int flag;
    double w,h,x,y;
    cin>>w>>h>>x>>y;
    if(fabs(w/2-x)<=0.000001&&fabs(h/2-y)<=0.000001) flag=1;
    else flag=0;
    printf("%f %d\n",w*h/2,flag);
    return 0;
}

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

int F[45];

int main() {
	int n;
	cin >> n;
	F[0] = 1;
	F[1] = 1;
	for (int i = 2; i <= n; i++)
		F[i] = F[i - 2] + F[i - 1];
	cout << F[n] << endl;
}

Measured memory_bytes: 1164
#include <iostream>
#include <algorithm>

using namespace std;

long min_dist(long * s, long * t, long x, int A, int B){
    long s2 = *lower_bound(s, s + A, x);
    long s1 = *(lower_bound(s, s + A, x) - 1);
    long t2 = *lower_bound(t, t + B, x);
    long t1 = *(lower_bound(t, t + B, x) - 1);
    long ans = min(max(s2, t2) - x, x - min(s1, t1));
    ans = min(ans, min(min(2 * s2 - t1 - x, 2 * t2 - s1 - x), min(s2 - 2 * t1 + x, t2 - 2 * s1 + x)));
    return ans;
}



int main(){
    int A, B, Q;
    cin >> A >> B >> Q;
    long s[A+2], t[B+2], x[Q+2];
    s[0] = -long(1e10)-1;
    t[0] = -long(1e10)-1;
    x[0] = -long(1e10)-1; 
    for(int i=0; i<A; i++) cin >> s[i+1];
    for(int i=0; i<B; i++) cin >> t[i+1];
    for(int i=0; i<Q; i++) cin >> x[i+1];
    s[A+1] = long(2e10)+1;
    t[B+1] = long(2e10)+1;
    x[Q+1] = long(2e10)+1; 



    for(int i=0; i<Q; i++){
        long ans = min_dist(s, t, x[i+1], A+2, B+2);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef vector<int> vi;

int main() {FIN
    
    int n, i;
    cin >> n;
    vi ns(n);
    for (i = 0; i < n; i++)
        cin >> ns[i];
    for (i = n - 1; i >= 0; i--) {
        if (i < n - 1) cout << " ";
        cout << ns[i];
    }
    cout << "\n";
        
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    if (N % 2 == 0) {
        cout << N*(N-2)/2 << endl;
        for (int i = 1; i <= N-1; i++) {
            for (int j = i+1; j <= N; j++) {
                if (i+j==N+1) continue;
                cout << i << " " << j << endl;
            }
        }
        return 0;
    }
    else if (N % 2 == 1) {
        cout << (N*(N-2)+1)/2 << endl;
        for (int i = 1; i <= N-1; i++) {
            for (int j = i+1; j <= N; j++) {
                if (i+j==N) continue;
                cout << i << " " << j << endl;
            }
        }
        return 0;
    }
    return 0;
}

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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll S = (int)1e9;

int main(){
  fastIO;
  ll s;
  cin >> s;
  cout << "0 0 1 " << S << " ";
  ll md = (s + S - 1) / S;
  ll rem = md * S;
  ll req = rem - s;
  cout << md << " " << req << "\n"; 
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

//update 2020/1/1 23:01

public class Main{

  static Scanner sc = new Scanner(System.in);
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) {

    double A = nextDouble();
    double B = nextDouble();
    double H = nextDouble();
    double M = nextDouble();

    double memoryJ = 5*(H+M/60);
    double memoryH = M;

    double sa = Math.abs(memoryJ-memoryH);

    double kakudo = Math.min(sa,60-sa);

    kakudo *= 6; //度

    double cos = Math.cos(Math.toRadians(kakudo));



    double ans = Math.sqrt(A*A + B*B - 2*A*B*cos);

    System.out.println(ans);

  }

  static int lcm(int a,int b){
    return a*b*gcd(a,b);
  }

  static int gcd(int a,int b){
    if(a%b!=0){
      return gcd(b,a%b);
    }
    else{
      return b;
    }
  }

  /*
    static String toSmall(String s){
      char c = s.charAt(0);
      //if(Character.isUpperCase(c)){
      if(c<=90){
        c += 32;
      }
      return String.valueOf(c);
    }
    static String toBig(String s){
      char c = s.charAt(0);
      //if(Character.isLowerCase(c)){
      if(c>=97){
        c -= 32;
      }
      return String.valueOf(c);
    }
  */

  static String toSmall(String s){
    return s.toLowerCase();
  }

  static String toBig(String s){
    return s.toUpperCase();
  }

  static String next(){
    return sc.next();
  }

  static int nextInt(){
    return Integer.parseInt(sc.next());
  }

  static long nextLong(){
    return Long.parseLong(sc.next());
  }

  static double nextDouble(){
    return Double.parseDouble(sc.next());
  }

  static String[] splitString(String s){
    return s.split("");
  }

  static char[] splitChar(String s){
    return s.toCharArray();
  }

  static int charToInt(char a){
    return a - 48;
  }

////////////////////////////////////////////
  public static int max(int[] a){
    int lng = a.length;
    int max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
  public static long max(long[] a){
    int lng = a.length;
    long max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
////////////////////////////////////////////

////////////////////////////////////////////
  public static int min(int[] a){
    int lng = a.length;
    int min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
  public static long min(long[] a){
    int lng = a.length;
    long min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
////////////////////////////////////////////

}


Measured memory_bytes: 36008
#include<bits/stdc++.h>
#include<iomanip>
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define mxn 2000
#define mod 1000000007
#define ld long double
#define pb push_back
#define inf 1e18
#define fi first
#define se second
#define ld long double
typedef long long int ll;
using  namespace std;
string s[mxn];
ll ans[mxn][mxn],n,m;
bool vis[mxn][mxn];
bool inside(ll x,ll y){
	if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==0&&s[x][y]=='.')
	return 1;
	else
	return 0;
}
void bfs(ll x,ll y){
//	cout<<x<<" "<<y<<" "<<cr<<endl;
	deque<pair<ll,ll>>q;
	q.pb({x,y});
	vis[x][y]=1;
	while(!q.empty()){
		pair<ll,ll>k=q.front();
		q.pop_front();
		vis[k.fi][k.se]=1;
		for(ll i=-1;i<=1;i++){
			for(ll j=-1;j<=1;j++){
				if((abs(i)+abs(j))!=1)
				continue;
				if(inside(k.fi+i,k.se+j)){
					vis[k.fi+i][k.se+j]=1;
				q.push_front({k.fi+i,k.se+j});
				ans[k.fi+i][k.se+j]=min(ans[k.fi+i][k.se+j],ans[k.fi][k.se]);
				}
		}
			}
		for(ll i=-2;i<=2;i++){
			for(ll j=-2;j<=2;j++){
				if(abs(i)+abs(j)==1||abs(i)+abs(j)==0)
				continue;
				if(inside(k.fi+i,k.se+j)){
					//vis[k.fi+i][k.se+j]=1;
				q.pb({k.fi+i,k.se+j});
				ans[k.fi+i][k.se+j]=min(ans[k.fi+i][k.se+j],ans[k.fi][k.se]+1LL);
			}
		}
	}
	}
}
int main(void){
	#ifndef ONLINE_JUDGE
	freopen("input1.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	fast;
	ll i,j,si,sj,ei,ej;
	cin>>n>>m;
	cin>>si>>sj>>ei>>ej;
	for(i=0;i<n;i++)
	cin>>s[i];
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)
		ans[i][j]=inf;
	}
	ans[si-1][sj-1]=0;
	bfs(si-1,sj-1);
	if(!vis[ei-1][ej-1])
	cout<<-1<<endl;
	else
	cout<<ans[ei-1][ej-1];
}


Measured memory_bytes: 19596
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
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);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

ld dp[3007][3007];

int main(){
  ll N;
  ld p[3007];
  cin >> N;
  rep(i,N){
    cin >> p[i];
  }
  dp[0][0]=1.0;
  rep(i,N){
    rep(j,i+1){
      dp[i+1][j]+=dp[i][j]*(1.-p[i]);
      dp[i+1][j+1]+=dp[i][j]*p[i];
    }
  }
  ld ans=0;
  Rep(i,(N+1)/2,N+1){
    ans+=dp[N][i];
  }
  cout << stpr(10) << ans << endl;
}

Measured memory_bytes: 139520
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    if n == 3:
        print(max(a))
        return
    dp = [[-inf] * 3 for i in range(n + 1)]
    dp[0] = [0, 0, 0]
    dp[1][0] = a[0]
    dp[2][1] = a[1]
    for i in range(3, n+1):
        dp[i][0] = dp[i - 2][0] + a[i-1]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0]) + a[i-1]
        dp[i][2] = max(dp[i - 2][2], dp[i - 3][1], dp[i - 4][0]) + a[i-1]
    if n & 1:
        print(max(dp[-3][0], dp[-1][1], dp[-1][2]))
    else:
        print(max(dp[-1][1], dp[-2][0]))
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 148548
#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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

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

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ; ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

#define FAST_IO std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()
#define endl "\n"

// priority_queue<ll, vector<ll>, less<ll>>pq;     // Max Heap
// priority_queue<ll, vector<ll>, greater<ll>>pq;  // Min Heap

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth (1 based indexing) smallest: " << *A.find_by_order(k - 1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

int main()
{
	FAST_IO;

	ll n, tot = 0, m;
	cin >> n >> m;    
	ll a[n];
	for(int i=0;i<n;i++) cin >> a[i], tot += a[i];
	sort(a, a + n);
	reverse(a, a + n);
	if(a[m - 1] * 4 * m >= tot)  cout << "Yes" << endl;
	else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int n[2], m, d;

  while (scanf("%d %d",&n[0], &n[1]) != EOF){
    d = 1;
    m = n[0] + n[1];
    while (m > 0){
      if (m > 9){
        m /= 10;
        d++;
      }
      else {
        break;
      }
    }
    printf("%d\n", d);
  }
  
  return (0);
}

Measured memory_bytes: 600
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define s(i,j) swap(C[i-1],C[j-1])
bool completion(vector<int> &C){
    bool OK = true;
    for(int i=1;i<9;++i) if(C[0] != C[i]) OK = false;
    for(int i=10;i<12;++i) if(C[9] != C[i]) OK = false;
    for(int i=13;i<15;++i) if(C[12] != C[i]) OK = false; 
    return OK;
}

void roll_1(vector<int>& C){s(1,28);s(2,29);s(3,30);s(15,16);s(19,21);}
void roll_2(vector<int>& C){s(7,22);s(8,23);s(9,24);s(13,18);s(10,12);}
void roll_3(vector<int>& C){s(1,24);s(4,27);s(7,30);s(10,21);s(16,18);}
void roll_4(vector<int>& C){s(3,22);s(6,25);s(9,28);s(15,13);s(19,12);}

int main(){
    int N;cin>>N;
    for(int i=0;i<N;++i){
        vector<int> P(30);
        for(int j=0;j<30;++j) cin>>P[j];
        queue<pair<vector<int>,int>> Q;
        Q.push({P,0});
        while(!Q.empty()){
            pair<vector<int>,int> p = Q.front(); Q.pop();
            if(completion(p.first)){cout<<p.second<<endl;break;}
            else{
                for(int i=1;i<5;++i){
                    vector<int> v = p.first; 
                    switch(i){
                        case 1: roll_1(v);break;
                        case 2: roll_2(v);break;
                        case 3: roll_3(v);break;
                        case 4: roll_4(v);break; 
                    }
                    Q.push({v,p.second+1});
                }
            }
        }
    }
}


Measured memory_bytes: 16252
import java.util.Arrays;
import java.util.Scanner;

import static java.lang.Math.max;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] s = new String[n];
        long count = 0;
        int tmpCount = 1;

        for (int i = 0; i < n; i++) {
            char[] tmp = scanner.next().toCharArray();
            Arrays.sort(tmp);
            s[i] = String.valueOf(tmp);
        }

        Arrays.sort(s);

        for (int i = 1; i < n; i++) {
            if(s[i-1].equals(s[i])) {
                count += tmpCount;
                tmpCount++;
            } else {
                tmpCount = 1;
            }
        }
        System.out.println(count);

    }

}



Measured memory_bytes: 51660
#include<bits/stdc++.h>
using namespace std;
using ll=int_fast64_t;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n,m,s,t;
    in>>n>>m;
    vector<vector<int>> v(n),e(n);
    fr(i,m) in>>s>>t,v[--s].emplace_back(--t),e[t].emplace_back(s);
    fr(i,n-1) sort(v[i].begin(),v[i].end());
    vector<double> p(n);
    ifr(j,n){
        for(auto k:e[j]){
            p[k]+=(p[j]+1)/(double)v[k].size();
        }
    }
    double ans=p[0];
    fr(i,n-1){
        if(v[i].size()==1) continue;
        int K=0;
        double D=-1;
        for(auto j:v[i]) if(p[j]>D) K=j,D=p[j];
        vector<double> dp(n,0);
        ifr(j,n){
            for(auto k:e[j]){
                if(k==i){
                    if(j!=K) dp[k]+=(dp[j]+1)/(double)(v[k].size()-1);
                }
                else{
                    dp[k]+=(dp[j]+1)/(double)v[k].size();
                }
            }
        }
        ans=min(ans,dp[0]);
    }
    printf("%.12lf\n",ans);
}

Measured memory_bytes: 4608
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

int main() {
  int N; cin >> N;
  int p[N+1];
  rep(i, N) {
    int A; cin >> A;
    p[A] = i+1;
  }

  for(int i=1; i<=N; i++) {
    if (i!=1) cout << " ";
    cout << p[i];
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

void bubblesort(int A[], int N) {
	bool flag = 1;
	for (int i=0; flag; i++) {
	flag = 0;
	 for (int j=N-1; j >i; j--) {
		if (A[j-1] > A[j]) {
		swap(A[j-1],A[j]);
		flag = 1;
		}
		}
	}
}



int main(){
	int n,k;
	int a[200001] = {};
	int count[200001] = {};
	scanf("%d %d", &n,&k);
	for (int i=0;i<n;i++)
	{scanf("%d",&a[i]);
	 count[a[i]-1]++;
	}
	int notzero=0;;
	for (int i=0;i<n;i++) {
	if (count[i]!=0) {notzero++;}
	}
	//0だったら配列に入れなくていいや。
	
/*	for (int i=0;i<n;i++) {
        printf("%d\n",count[i]);
        }
*/
	int j=0;
	int sub[notzero];
	for (int i=0; i<n;i++){
	if (count[i]!=0) {sub[j]=count[i];j++; if (j>=notzero) break;}
	}	
/*	for (int i=0;i<notzero;i++) {
        printf("before %d\n",sub[i]);
        }
*/
	//minからsortする。
	bubblesort(sub,notzero);
/*	for (int i=0;i<notzero;i++) {
        printf("%d\n",sub[i]);
        }		
	printf("notzero = %d\n", notzero);	
*/
	int cnt=0;
	int i = -1;

	if (notzero <= k) {printf("%d\n", cnt); return 0;};	
	while(notzero != k) {
	i++;
	if (sub[i]!=0){
	cnt += sub[i];
	notzero--;
	}
	}
		

	printf("%d\n", cnt);	
	return 0;
}
	
	
	


Measured memory_bytes: 2560