akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>


void input(); template<typename First,typename... Rest> void input(First&,Rest&...);
void inputVector(); template<typename First,typename... Rest>  void inputVector(std::vector<First>&,Rest&...);


void calculate(){
    std::string s;
    input(s);
    int N = s.size();
    for(int i = 0;i < N;++i)
    {
        std::cout << "x";
    }
    std::cout<<"\n";
}

int main(int,char**){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    calculate();
}



void input(){return;}
template<typename First,typename... Rest>
void input(First &first,Rest&... rest){
    std::cin >> first;
    input(rest...);
}

void inputVector(){return;}
template<typename First,typename... Rest> 
void inputVector(std::vector<First> &first,Rest&... rest){
    int N = first.size();
    for(int i = 0;i < N;i++){
        std::cin >> first[i];
    }
    inputVector(rest...);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
const ll mod=1e9+7;
template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
const ll N=1e5+8;
ll dp[103][N];
ll a[N][4],n,W;
ll func(ll w[],ll v[],ll W,ll a){
if(a>n||W==0)
return 0;
if(dp[a][W]!=-1)
return dp[a][W];
if(w[a]<=W)
return dp[a][W]=max(v[a]+func(w,v,W-w[a],a+1),func(w,v,W,a+1));
if(w[a]>W)
return dp[a][W]=func(w,v,W,a+1);
}
int main(){
	cin>>n>>W;
	ll v[n+1],w[n+1];
	for(ll i=1;i<=n;i++)
	cin>>w[i]>>v[i];
	memset(dp,-1,sizeof(dp));
	cout<<func(w,v,W,1ll);
}

Measured memory_bytes: 81792
#define _GLIBCXX_DEBUG
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>
//#include <bits/stdc++.h>

typedef long long ll;
const ll INF = 1e18 + 1;
const ll MOD = 1e9 + 7;

// print(x, y, z);
// print(va.begin(), va.end());
void print(){ std::cout << std::endl; }
template <typename Head> void print(Head&& head) { std::cout << head << std::endl; }
template <typename Head, typename... Tail> void print(Head&& head, Tail&&... tail)
{
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...); // or print(tail...);
}
template<typename Iterator> void printVec(Iterator begin, Iterator end)
{
  for (Iterator it = begin; it != end; it++) {
    std::cout << "[" << std::distance(begin, it) << "] " << *it << " ";
    if (std::distance(begin, it) % 50 == 49) { std::cout << std::endl; }
  }
  std::cout << std::endl;
}

template<typename T> T lminimum(const std::vector< T >& v) {return *std::min_element(v.begin(), v.end());}
template<typename T> T lmaximum(const std::vector< T >& v) {return *std::max_element(v.begin(), v.end());}
template<typename T> void lunique(std::vector< T >& v) {v.erase(std::unique(v.begin(), v.end()), v.end());}
template<typename T> void lsort(std::vector< T >& v) {std::sort(v.begin(), v.end());}
template<typename T> void lgreatersort(std::vector< T >& v) {std::sort(v.begin(), v.end(), std::greater<>());}
template<typename T> bool lnext_permutation(std::vector< T >& v) {return std::next_permutation(v.begin(), v.end());}

int main(int argc, char* argv[])
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  ll N;
  std::cin >> N;
  std::vector< ll > vh(N, 0LL);
  for (ll i = 0; i < N; i++) {
    std::cin >> vh[i];
  }

  ll ans = 0;
  ll max_val = *std::max_element(vh.begin(), vh.end());
  while (max_val > 0) {
    for (ll i = 0; i < N; i++) {
      if (i+1 < N && vh[i] == max_val && vh[i+1] != max_val) {
	ans++;
      }
      if (i+1 == N && vh[i] == max_val) {
	ans++;
      }
      if (vh[i] == max_val) {
	vh[i]--;
      }
    }
    max_val--;
  }

  print(ans);
  return 0;
}


Measured memory_bytes: 256
def judge(bit, n, v):
    # i 人目の証言を検証する
    for i in range(n):
        # 1人目が「不親切」だったら証言はすべて無視
        if not (bit & (1 << i)):
            continue

        for x, y in v[i]:
            # y == 1 なのに「不親切」だったらダメ
            if y == 1 and not (bit & (1 << x)):
                return False

            # y == 0 なのに「正直者」だったらダメ
            if y == 0 and (bit & (1 << x)):
                return False
    return True


n = int(input())
v = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = [int(i) for i in input().split()]
        v[i].append((x - 1, y))

ans = 0
for bit in range(1 << n):
    if not judge(bit, n, v):
        continue

    # bit に含まれる人数を数える
    cnt = 0
    for i in range(n):
        if bit & (1 << i):
            cnt += 1
    ans = max(ans, cnt)
print(ans)


Measured memory_bytes: 3064
n,m=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
b=[list(map(int,input().split()))for i in range(m)]
for i in a:
  t=10**18
  ans=0
  c=1
  for j in b:
    k=abs(i[0]-j[0])+abs(i[1]-j[1])
    if t>k:
      ans=c
      t=k
    c+=1
  print(ans)

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

#define pout(n)  printf ("%d\n", n)

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());

const int d4x[4] = {1, 0, -1, 0};
const int d4y[4] = {0, 1, 0, -1};
const int d8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const int d8y[8] = { 0,1,1,1,0,-1,-1,-1 };

#define MAX_N (int)2e5+20
#define INF 1e12+20

typedef long long ll;
using namespace std;

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

	rep(i,0,4){
		printf("%c",s[i]);
	}
	printf(" ");
	rep(i,4,s.size()){
		printf("%c",s[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int a, b, c, i,j=0,check=0;
	int yakusu[1000];
	scanf("%d%d%d", &a, &b, &c);
	for (i = 1;; i++){
		if (c%i == 0){
			yakusu[j] = i;
			if (i == c){
				break;
			}
			j++;
		}
	}

	for (i = 0; i <= j; i++){
		if (a <= yakusu[i] && yakusu[i] <= b){
			check++;
		}
	}

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

	return 0;
}

Measured memory_bytes: 1028
N = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(N-1):
  if p[i] == i+1:
    p[i], p[i+1] = p[i+1], p[i]
    ans += 1
if p[N-1]==N:
    ans+=1
print(ans)

Measured memory_bytes: 20500
#include <stdio.h>
#include <iostream>
#include <cstring>
typedef long long ll;
const int N=530000;
const int mod=924844033;
const int G=5;
int n,head[N],now=0,siz[N],A[N],B[N];
int tim[N],fac[N],ifac[N],rev[N];
using namespace std;

struct node
{
	int t,next;
}adj[N<<1];
void add(int s,int t)
{
	adj[++now]=(node){t,head[s]};
	head[s]=now;
}
int calc(int a,int b)
{
	int ans=1,tmp=a;
	while (b)
	{
		if (b&1) ans=(ll)ans*tmp%mod;
		tmp=(ll)tmp*tmp%mod,b>>=1;
	}
	return ans;
}
void dfs(int s,int fa)
{
	int i;siz[s]=1;
	for (i=head[s];i;i=adj[i].next)
	if (adj[i].t!=fa) dfs(adj[i].t,s),siz[s]+=siz[adj[i].t];
	for (i=head[s];i;i=adj[i].next)
	if (adj[i].t!=fa)
	{
		if (tim[siz[adj[i].t]]>0) tim[siz[adj[i].t]]--;
		else tim[siz[adj[i].t]]=mod-1;
	}
	if (tim[n-siz[s]]>0) tim[n-siz[s]]--;
	else tim[n-siz[s]]=mod-1;
	tim[n]=(tim[n]+1)%mod;
}
void NTT(int *a,int n,int flag)
{
	int i,j,k,x,y,w,wn;
	for (i=1;i<n;i++)
	if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (i=1;i<n;i<<=1)
	{
		wn=calc(G,(mod-1)/(i<<1));
		if (flag) wn=calc(wn,mod-2);
		for (j=0;j<n;j+=(i<<1))
		for (k=0,w=1;k<i;k++,w=(ll)w*wn%mod)
		x=a[j+k],y=(ll)a[j+k+i]*w%mod,a[j+k]=(x+y)%mod,a[j+k+i]=(x-y+mod)%mod;
	}
	if (flag)
	{
		int inv=calc(n,mod-2);
		for (i=0;i<n;i++) a[i]=(ll)a[i]*inv%mod;
	}
}
int main()
{
	#ifdef Kay
		freopen ("agc005_f.in","r",stdin);
		freopen ("agc005_f.out","w",stdout);
	#endif
	scanf ("%d",&n);
	int i,s,t;
	for (i=1;i<n;i++)
	scanf ("%d %d",&s,&t),add(s,t),add(t,s);
	dfs(1,0);
	fac[0]=ifac[0]=1;
	for (i=1;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
	ifac[n]=calc(fac[n],mod-2);
	for (i=n-1;i>=1;i--) ifac[i]=(ll)ifac[i+1]*(i+1)%mod;
	int tot,len;
	for (tot=0,len=1;len<=n;len<<=1,tot++);len<<=1,tot++;
	for (i=1;i<=n;i++) A[n-i]=(ll)tim[i]*fac[i]%mod;
	for (i=0;i<=n;i++) B[i]=ifac[i];
	for (i=1;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(tot-1));
	NTT(A,len,0),NTT(B,len,0);
	for (i=0;i<len;i++) A[i]=(ll)A[i]*B[i]%mod;
	NTT(A,len,1);
	for (i=1;i<=n;i++) printf ("%d\n",(ll)A[n-i]*ifac[i]%mod);
	return 0;
}


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

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

	cin >> n;
	for(i=1;i<=n;i++)
		cin >> a[i];

	ll ans=0;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			for(k=j+1;k<=n;k++)
			{
				x=a[i],y=a[j],z=a[k];
				if(x+y>z && x+z>y && y+z>x && x!=y && y!=z && x!=z)
					ans++;
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3644
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;
using ull = unsigned long long;

int main() {
    int X, Y;
    cin >> X >> Y;
    cout << X + Y / 2 << endl;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
mod=10**9+7
def cmb(n, r):#nCr 組合わせ
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
  
for i in range(1,k+1):
  if i==1:
    print(n-k+1)
  else:
    if k<i or n-k+1<i:
      print(0)
    else:
      print((cmb(n-k+1,i)*(cmb(k-1,i-1)))%mod)


Measured memory_bytes: 9184
/**************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

***************************/

#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define MAXI 1000000007
#define mp make_pair
using namespace std;
/*long long int fib(long long int n) 
{ 
  
  long long int f[n+2];   // 1 extra to handle case, n = 0 
  long long int i; 
  f[0] = 0; 
  f[1] = 1; 
  
  for (i = 2; i <= n; i++) 
  { 
      f[i] = f[i-1] + f[i-2]; 
  } 
  
  return f[n]; 
}*/ 
int main()
{   ll v=0,h=0,d,m,n,cnt=0,j=0,l=0,y=0,t,k=0,sum=1,x=0,i,mask,min,r=1,adv,g=0,low,high,yeah=0;
    string s1,s2,s3;
    map<char,long long int>mp;
    vector<long long int> v1;
    vector<long long int> v2;
    set<char> sy;
    char c;
    long long pos=0,pred=0;
    long long MAX=1e9+7;
    i=0;
    cin>>n>>k;
    if(n==1){cout<<k;}
    else{
        r*=k;
        for(i=0;i<(n-1);i++){
            r*=(k-1);
        }
        cout<<r;
    }
    
}

Measured memory_bytes: 256
/* [Template].cpp 
Example code to use when starting new code. This particular problem was problem 
977A_Wrong_Subtraction from CodeForces

Compile: g++  -o B.exe B.cpp 
Execute: ./B
*/ 

#include <cstdio>
#include <iostream>
#include <cmath> 
#include <limits> 
#include <iomanip>
#include <cstring> 
#include <bits/stdc++.h>
#include <string>  
#include <map>
using namespace std;

int main() { 	
	int n, table[4] = {0};
	string s; 
	cin >> n;
	
	for(int i = 0; i < n; i++) {
		cin >> s; 
		if(s.compare("AC") == 0) table[0]++;
		if(s.compare("WA") == 0) table[1]++;
		if(s.compare("TLE") == 0) table[2]++;
		if(s.compare("RE") == 0) table[3]++;
	}
	
	cout << "AC x " << table[0] << endl; 
	cout << "WA x " << table[1] << endl; 
	cout << "TLE x " << table[2] << endl; 
	cout << "RE x " << table[3] << endl; 
	
	return 0; 
} 


Measured memory_bytes: 3600
#include "bits/stdc++.h"
using namespace std;

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


int main() {
	int n;
	cin >> n;
	if (n / 100 == 7 || n % 10 == 7 || (n / 10) % 10 == 7) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 3636
import operator
N = int(input())
rests = []
for i in range(N):
  S, P = input().split()
  P = int(P)
  rest = (i + 1, S, P)
  rests.append(rest)
rests = sorted(rests, key = operator.itemgetter(2), reverse=True)
rests = sorted(rests, key = operator.itemgetter(1))
for row in rests:
  print(row[0])

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

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

    for(int i=0;i<1000;i++)
    {
    	if((a[0]*i)-(i-1)>=a[1])
    	{	cout<<i;
    		break;}

    }



    return 0;
}

Measured memory_bytes: 256
// abc049-c
#include <iostream>
#include <algorithm>
#include <string.h> // strdup
using namespace std;

int main() {
    string s;

    string sa[] = {
        "dream", "dreamer", "erase", "eraser"
    };

    cin >> s;
    reverse(s.begin(), s.end());
    for (int i = 0; i < 4; i++) {
        reverse(sa[i].begin(), sa[i].end());
    }

    bool valid = true;
    for (size_t pos = 0; valid && pos < s.size(); ) {
        size_t offset = 0;
        for (int i = 0; i < 4; i++) {
            int cmp = strncmp(s.c_str() + pos, sa[i].c_str(), sa[i].length());
            if (cmp == 0) {
                offset = sa[i].length();
                break;
            }
        }
        if (offset != 0) {
            pos += offset;
        } else {
            valid = false;
        }
    }

    string result = valid ? "YES": "NO";
    cout << result << endl;
    return 0;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  vector<ll> x(N);
  rep(i, N) cin >> x[i];
  ll mn = 1e11;
  rep(i, N - K + 1) {
    ll dist = x[i + K - 1] - x[i];
    mn = min(mn, dist + min(abs(x[i]), abs(x[i + K - 1])));
  }
  cout << mn << endl;
  return 0;
}


Measured memory_bytes: 1024
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
ab = []
for _ in range(n):
    abi = na()
    ab.append(abi)

ab.sort()
ai, bi = ab[0][0], ab[0][1]
c = 0
ans = 0
while m > 0:
    bi -= 1
    ans += ai
    m -= 1
    if bi == 0 and m != 0:
        c += 1
        ai, bi = ab[c][0], ab[c][1]

print(ans)

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

#define y1 as214
#define ii pair < int , ll >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define fr front()
#define pb push_back

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

#define ll long long
#define oo INT_MAX

/// dp[i][j] là giá trị nhiều nhất nhận được khi xét i vât đầu tiên và tổng trọng lượng của i vật đó không quá j.

const int N = 1e2 + 5;
const int M = 1e5 + 5;
ll n , w;
ll W[N] , V[N];
ll dp[N][M];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> w;
    FOR(i , 1 , n)
        cin >> W[i] >> V[i];
    FOR(i , 1 , n)
        FOR(j , 1 , w)
    {
            dp[i][j] = dp[i - 1][j];
            if(j >= W[i])
                dp[i][j] = max(dp[i][j] , dp[i - 1][j - W[i]] + V[i]);
    }
    cout << dp[n][w];
}


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

using namespace std;

int n,i,j,sum[100005],sum1[100005];
char s[100005],s1[100005];

int main(){
	scanf("%s%s", s, s1);
	
	int l = strlen(s);
	int l1 = strlen(s1);
	
	for(i = 1; i <= l; i++)
	sum[i] = (sum[i - 1] + s[i - 1] - 'A' + 1) % 3;
	for(i = 1; i <= l1; i++)
	sum1[i] = (sum1[i - 1] + s1[i - 1] - 'A' + 1) % 3;
	
	int q;
	scanf("%d", &q);
	
	for(i = 0; i < q; i++){
		int x,y,xx,yy;
		
		scanf("%d%d%d%d", &x, &y, &xx, &yy);
		
		int v = (sum[y] - sum[x - 1] + 3) % 3;
		int v1 = (sum1[yy] - sum1[xx - 1] + 3) % 3;
		
		if(v == v1)
		printf("YES\n");
		else
		printf("NO\n");
	}
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rapido ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define mod 1000000007

int find(string s,string t)
{
    int c=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=t[i])
        c++;
    }
    return c;
}
void solve()
{
    string s;string t;cin>>s>>t;
    int n=s.size();
    int m=t.size();
    int ans=m;
    for(int i=0;i<=n-m;i++)
    {
        string str=s.substr(i,m);
        ans=min(ans,find(str,t));
    }
    cout<<ans<<endl;
}
int32_t main()
{
    rapido;
    int t;
    //cin>>t;
    t=1;
       while(t--)
       solve();
}

Measured memory_bytes: 3660
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
#define SIZE 200010

using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
long long int MOD = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int N,K;
int G[2010][2010]={0};
int sumG[2010][2010]={0};
int calc(int x1,int y1,int x2,int y2){
	x1--;y1--;
	return sumG[x2][y2]+sumG[x1][y1]-sumG[x1][y2]-sumG[x2][y1];
}
int main(){
	cin>>N>>K;
	int x,y;
	char c;
		
	for(int i=0;i<N;i++){
		cin>>x>>y>>c;
		if(c=='W'){
			x+=K;
		}
		x=x%(2*K);
		y=y%(2*K);
		G[x][y]++;
	}
	for(int i=1;i<=2*K;i++){
		int wa=0;
		for(int j=1;j<=2*K;j++){
			wa+=G[i-1][j-1];
			sumG[i][j]=sumG[i-1][j]+wa;
			//cout<<sumG[i][j]<<" ";
		}
		//cout<<endl;
	}
	int ans=0;
	for(int i=1;i<=K;i++){
		for(int j=1;j<=K;j++){
			int hoge=calc(i,1,i+K-1,j-1)+calc(1,j,i-1,j+K-1)+calc(i+K,j,2*K,j+K-1)+calc(i,j+K,i+K-1,2*K);
			ans=max(max(ans,hoge),N-hoge);
			//cout<<hoge<<" ";
			//cout<<calc(i,1,i+K-1,j-1)<<calc(1,j,i-1,j+K-1)<<calc(i+K,j,2*K,j+K-1)<<calc(i,j+K,i+K-1,2*K)<<endl;
		}
		//cout<<endl;
	}
	cout<<ans<<endl;
}

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

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


signed main() {
	int n;
	cin >> n;
	vector<double>vec;
	rep(i, n) {
		int a;
		cin >> a;
		vec.push_back(a);
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	rep(i, n - 1) {
		double a = vec[vec.size() - 1], b = vec[vec.size() - 2];
		vec.pop_back(); vec.pop_back();
		vec.push_back((a + b) / 2);
		sort(vec.begin(), vec.end());
		reverse(vec.begin(), vec.end());
	}
	printf("%.12lf\n", vec[0]);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define fi first
#define se second
#define ep emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) 
#define rep2(i, n, m) for (ll i = n; i <= (ll)(m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (ll)(m); --i)

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

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

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

  int n; cin >> n;

  rep2(i, 1, n) {
    if (floor (i * 1.08) == n) {
      cout << i << endl;
      return (0);
    }
  }

  cout << ":(" << endl;

  return (0);
}


Measured memory_bytes: 3572
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
// ------ Classes ------ //
class Point {
public:
	long double px, py;
	Point() : px(0), py(0) {};
	Point(long double px_, long double py_) : px(px_), py(py_) {};
	friend bool operator==(const Point& p1, const Point& p2) { return p1.px == p2.px && p1.py == p2.py; }
	friend bool operator!=(const Point& p1, const Point& p2) { return p1.px != p2.px || p1.py != p2.py; }
	friend Point operator+(const Point& p1, const Point& p2) { return Point(p1.px + p2.px, p1.py + p2.py); }
	friend Point operator-(const Point& p1, const Point& p2) { return Point(p1.px - p2.px, p1.py - p2.py); }
	friend Point operator*(const Point& p1, long double d) { return Point(p1.px * d, p1.py + d); }
	friend Point operator*(long double d, const Point& p1) { return p1 * d; }
	friend Point operator/(const Point& p1, long double d) { return Point(p1.px / d, p1.py / d); }
	Point& operator+=(const Point& p1) { px += p1.px; py += p1.py; return *this; }
	Point& operator-=(const Point& p1) { px -= p1.px; py -= p1.py; return *this; }
	Point& operator*=(long double d) { px *= d; py *= d; return *this; }
	Point& operator/=(long double d) { px /= d; py /= d; return *this; }
};
class Segment {
public:
	Point p1, p2;
	Segment(Point p1_, Point p2_) : p1(p1_), p2(p2_) {};
	Segment(long double p1x, long double p1y, long double p2x, long double p2y) : p1(Point(p1x, p1y)), p2(Point(p2x, p2y)) {};
	friend bool operator==(const Segment& s1, const Segment& s2) { return (s1.p1 == s2.p1 && s1.p2 == s2.p2) || (s1.p1 == s2.p2 && s1.p2 == s2.p1); }
	friend bool operator!=(const Segment& s1, const Segment& s2) { return !(s1 == s2); }
};
class Line {
public:
	Point p1, p2;
	Line(Point p1_, Point p2_) : p1(p1_), p2(p2_) {};
	Line(long double p1x, long double p1y, long double p2x, long double p2y) : p1(Point(p1x, p1y)), p2(Point(p2x, p2y)) {};
	friend bool operator==(const Line& s1, const Line& s2) { return (s1.p1 == s2.p1 && s1.p2 == s2.p2) || (s1.p1 == s2.p2 && s1.p2 == s2.p1); }
	friend bool operator!=(const Line& s1, const Line& s2) { return !(s1 == s2); }
};
// ------ Functions ------ //
long double norm(const Point& a) { return a.px * a.px + a.py * a.py; }
long double abs(const Point& a) { return sqrtl(norm(a)); }
long double dot(const Point& a, const Point& b) { return a.px * b.px + a.py * b.py; }
long double crs(const Point& a, const Point& b) { return a.px * b.py - a.py * b.px; }
int ccw(Point p0, Point p1, Point p2) {
	Point a = p1 - p0, b = p2 - p0;
	if (crs(a, b) > 1e-10) return 1;
	if (crs(a, b) < -1e-10) return -1;
	if (dot(a, b) < -1e-10) return 2;
	if (norm(a) < norm(b)) return -2;
	return 0;
}
// ------ Main ------ //
Point p1, p2, p3, p4; int r1, r2, r3, r4;
int main() {
	while (~scanf("%Lf,%Lf,%Lf,%Lf,%Lf,%Lf,%Lf,%Lf", &p1.px, &p1.py, &p2.px, &p2.py, &p3.px, &p3.py, &p4.px, &p4.py)) {
		r1 = ccw(p1, p2, p3);
		r2 = ccw(p2, p3, p4);
		r3 = ccw(p3, p4, p1);
		r4 = ccw(p4, p1, p2);
		printf("%s\n", (r1 == r2 && r2 == r3 && r3 == r4 && abs(r1) == 1) ? "YES" : "NO");
	}
	return 0;
}

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

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

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

	int max = 0, cnt = 0;
	for (int i = 0; i < n-1; i ++) {
		if (hights[i] >= hights[i+1]) {
			// 移動できる
			cnt ++;
		} else {
			if (max < cnt) {
				max = cnt;
			}
			cnt = 0;
		}
	}
	if (max < cnt) {
		max = cnt;
	}
	cout << max << endl;
	return 0;
}


Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int p[n + 1];
    int Max = 0;
    int Sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        Max = Max < p[i] ? p[i] : Max;
        Sum += p[i];
    }
    for (int i = 1; i <= n; i++) {
        if (p[i] == Max) {
            Sum -= p[i];
            Sum += p[i] / 2;
            break;
        }
    }
    cout << Sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    int N, K;
    ll hk, c[100000];
    cin >> N >> K;
    int h[100000];
    for(int i=0;i<N;i++)
        cin >> h[i];
    for(int i=1;i<N;i++){
    	if(i==1){
    	    c[i] = abs(h[i] - h[0]);
        }else{
        	c[i] = LLONG_MAX;
        	for(int j=1;j<=K;j++){
                if(i-j >= 0){
        	        hk = c[i-j] + abs(h[i] - h[i-j]);
                    if(hk < c[i])
                        c[i] = hk;
                }
            }
        }    
    }
    
    cout << c[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1408
import java.io.*;

public class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
		String s,t;
		String[] u;
		double[] q;
		double l,p;
		double xa,ya,ra,xb,yb,rb;
		int n;
		int[] ans;
		while((s=reader.readLine())!=null){
			n=Integer.parseInt(s);
			ans=new int[n];
			for(int i=0;i<n;i++){
				t=reader.readLine();
				u=t.split(" ");
				q=new double[6];
				for(int k=0;k<6;k++){
					q[k]=Double.parseDouble(u[k]);
				}
				xa=q[0];
				ya=q[1];
				ra=q[2];
				xb=q[3];
				yb=q[4];
				rb=q[5];
				l=Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));
				if(ra<rb){p=rb-ra;}
				else{p=ra-rb;}
				if((ra+rb)<l){
					ans[i]=0;
				}else if(p<=l &&l<=(ra+rb)){
					ans[i]=1;
				}else if(ra>rb){
					ans[i]=2;
				}else{
					ans[i]=-2;
				}
				System.out.println(ans[i]);
			}
		}
	}
}

Measured memory_bytes: 16928
#include<iostream>
using namespace std;
int main(){
  int N,M;
  cin >> N >> M;
  int max_l=1;
  int min_r=N;
  int l,r;
  for(int i=0;i<M;i++){
    cin >> l >> r;
    max_l = max(max_l,l);
    min_r = min(min_r,r);
  }
  cout << max(0, min_r-max_l+1) << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll mininf = -922337203685477;
const ll nax = 0;

string s, t;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> s >> t;
	string str = "";
	for(ll i = 0; i < t.size() - 1; i++){
		str += t[i];
	}
	if(s == str){
		cout << "Yes" << '\n';
	}
	else{
		cout << "No" << '\n';
	}
}


Measured memory_bytes: 3656
n,tw = map(int, input().split())
wt = [];    val = []
for i in range(n):
    a,b = map(int, input().split())
    wt.append(a);   val.append(b)
dp = [[0 for i in range(tw+1)] for j in range(n+1)]
for i in range(n):
    for j in range(1,tw+1):
        if j < wt[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], val[i]+dp[i][j-wt[i]])
print(dp[n][tw])


Measured memory_bytes: 171528
strings = input().split(' ')
N = int(strings[0])
A = int(strings[1])
B = int(strings[2])

distance = B - A
moves = 0
if distance % 2 ==1:
    distance_B2W = N - B
    distance_A2W = A - 1
    moves = moves + min(distance_A2W,distance_B2W) + 1
    moves = moves + (distance - 1) // 2
    print(moves)
else:
    print(distance // 2)

    

Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll N,X,T;
    cin>>N>>X>>T;
    cout<<(ll)ceil((N*1.0/X*1.0))*T;
    return 0;
}


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

public class Main {

    public static void main(String[] args) {

        try (Scanner scan = new Scanner(System.in)) {
            // スキップ
            scan.nextLine();

            // 検索対象をmapに格納する
            Map<String, String> map = new HashMap<String, String>();
            for (String num : scan.nextLine().split(" ")) {
                map.put(num, "");
            }

            // スキップ
            scan.nextLine();

            // 検索対象が存在する場合はカウントする
            int count = 0;
            for (String num : scan.nextLine().split(" ")) {
                if (map.containsKey(num)) {
                    count += 1;
                }
            }

            System.out.println(count);
        }

    }

}



Measured memory_bytes: 73804
package main

import "fmt"

func main() {
	var h, w int
	fmt.Scan(&h, &w)
	if h == 1 || w == 1 {
		fmt.Println(1)
		return
	}
	if h*w%2 == 0 {
		fmt.Println(h * w / 2)
	} else {
		fmt.Println(h*w/2 + 1)
	}
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define sz(a) (int)((a).size())
#define fuck() cout<<"--------"<<endl
#define see(x) cout<<#x<<" = "<<x<<endl
const int hell=1000000007;
typedef pair<int,int> pii;
const int N=2e7;
bool dp[N];
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    dp[0]=1;
    int cost[6]={100,101,102,103,104,105};
    for(int i=0;i<N;i++){
        for(int j=0;j<6;j++){
            dp[i+cost[j]]|=dp[i];
        }
    }
    cout<<dp[n];
    cerr<<"Time elapsed : "<<clock()*1000.0/CLOCKS_PER_SEC<<"ms"<<'\n';
}

Measured memory_bytes: 19840
#include <cstdlib>
#include <iostream>

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

  int k, s, cnt = 0;
  std::cin >> k >> s;

  for (int i = 0; i <= k; i++) {
    for (int j = i; j <= k; j++) {
      for (int l = j; l <= k; l++) {
        if (i + j + l == s) {
          if (i == j && j == l) {
            cnt++;
          } else if (i == j || j == l || i == l) {
            cnt += 3;
          } else {
            cnt += 6;
          }
        }
      }
    }
  }

  std::cout << cnt << std::endl;
  return EXIT_SUCCESS;
}

Measured memory_bytes: 256
n,c,k=map(int,input().split())
arr=[int(input()) for _ in range(n)]
arr=sorted(arr)
pos=0
cnt=0
for i in range(n):
  if pos==i:
    for j in range(c):
      if i+j==n:
        break
      if arr[i+j]-arr[i]>k:
        pos=pos+j
        break
    else:
      pos=pos+c
    cnt+=1
  else:
    continue
print(cnt)

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

int main(){
  int n,k;
  int64_t a = 0;
  cin >> n >> k;
  int64_t h[n];
  for(int i=0; i<n; i++){
    cin >> h[i];
  }
  sort(h, h + n);
  for(int i=0; i<n-k; i++){
    a = a+h[i];
  }
  cout << a << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <numeric>
#include <string>
#include <bitset>
#include <functional>

using ld = long double;
using vld = std::vector<ld>;
using vvld = std::vector<vld>;
using vvvld = std::vector<vvld>;
using ll = long long;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
using pll = std::pair<ll, ll>;
using vpll = std::vector<pll>;
using str = std::string;
using vstr = std::vector<str>;

template<typename T> bool chmin(T a, T &b) { return a < b ? b = a, true : false; }
template<typename T> bool chmax(T a, T &b) { return a > b ? b = a, true : false; }

constexpr ld PI = 3.141592653589793L;
constexpr ld EPS = std::numeric_limits<ld>::epsilon();

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }
bool is_prime(ll n) {
    if (n == 1) return false;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
ll rpow(ll x, ll n) {
    if (n == 0) return 1;
    ll k = 1;
    for (; n > 1; n /= 2) {
        if (n & 1) k *= x;
        x *= x;
    }
    return k * x;
}
ll modpow(ll x, ll n, ll mod) {
    if (n == 0) return 1;
    ll k = 1;
    for (; n > 1; n /= 2) {
        if (n & 1) (k *= x) %= mod;
        (x *= x) %= mod;
    }
    return k * x % mod;
}
ll modcomb(ll n, ll r, ll mod) {
    if (r < 0 || n < r) return 0;
    chmin(n - r, r);
    ll mul = 1, div = 1;
    for (ll i = 0; i < r; i++) {
        (mul *= n - i) %= mod;
        (div *= i + 1) %= mod;
    }
    return mul * modpow(div, mod - 2, mod) % mod;
}

/*------------------------------------------------------------------------*/

constexpr ll MOD = 1e9 + 7;

void solve();

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15);

    solve();
}
void solve() {
    ll n;
    std::cin >> n;

    vll a(n);
    for (ll i = 0; i < n; i++)
        std::cin >> a[i];

    std::unordered_map<ll, ll> umap;
    for (ll i = 0; i < n; i++)
        umap[a[i]]++;

    if (n % 2 == 1 && umap[0] != 1) { std::cout << 0 << '\n'; return; }

    for (ll i = n - 1; i > 0; i -= 2)
        if (umap[i] != 2) { std::cout << 0 << '\n'; return; }

    std::cout << modpow(2, n / 2, MOD) << '\n';
}


Measured memory_bytes: 7360
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007

int a,b,c,n,k,x,y;

int main(){
  int ans=0;
  cin >> k >> x;
  int ans0=max(x-k+1,-1000000);
  int ans1=min(x+k-1,1000000);
  for(int i=ans0;i<=ans1;i++){
    cout<<i<<" ";
  }
  
  return 0;
}

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


int main(){
int n,x;
cin >> n>>x;
vector<int> l(n);
rep(i,n) cin >> l[i];
int count = 0;
vector<int> d(n+1);
d[0]= 0;
rep(i,n){
    d[i+1] = d[i]+l[i];    
}
rep(i,n+1){
if(x>=d[i]) count++;
}
cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n, m;
  cin >> n >> m;
  cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;
}

Measured memory_bytes: 256
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    S = input_raw[0]
    count = 0
    N = len(S)
    if len(S) % 2 == 0:
        for i  in range(0, N/2):
            if S[N/2] == S[N/2 - i - 1]  and S[N/2] == S[N/2 + i]:
                count += 2
            else:
                break

    else:
        count += 1
        for i in range(1, N/2 + 1):
            if S[N/2] == S[N/2 - i] and S[N/2] == S[N/2 + i]:
                count += 2
            else:
                break

    K = N -(N - count)/2

    print K

if __name__ == '__main__':
    main()


Measured memory_bytes: 4592
n,m,*t=map(int,open(0).read().split())
a=sorted(t[:n])[::-1]
m=0
for c,b in sorted(zip(t[n+1::2],t[n::2]))[::-1]:
 while a and b and c>a[-1]:m+=c;b-=1;a.pop()
print(m+sum(a))

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

int main() {
    int N, M = 0;
    string S;
    cin >> N >> S;
    for (int i = 0; i < N - 2; i++) {
        if(S[i]=='A' && S[i + 1]=='B' &&S[i + 2] == 'C') {
            M++;
        }
    }
    cout << M;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
  int n;
  while(cin>>n){
    int x, xx=0, yy=0, y, t, tt=0;
    bool l=1;
    for(int i=0; i<n; ++i){
      cin>>t>>x>>y;
      if(abs(x-xx)+abs(y-yy)>(t-tt)||(-abs(x-xx)-abs(y-yy)+(t-tt))%2){
//        cout<<abs(x-xx)+abs(y-yy)<<" "<<(t-tt)<<endl;
        l=0;
      }
      xx=x;yy=y;tt=t;
    }
    if(l)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
  return 0;
}




Measured memory_bytes: 384
//
//  main.cpp
//  ABC136D
#include <iostream>
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main(int argc, const char * argv[]) {
    string s;
    cin>>s;
    ll n=s.size();
    vector<int>ans(n);
    rep(i,2){
        int cnt=0;
        rep(j,n){
            if(s[j]=='R') cnt++;
            else {
                ans[j]+=cnt/2;
                ans[j-1]+=(cnt+1)/2;
                cnt=0;
            }
        }
    reverse(ans.begin(), ans.end());
    reverse(s.begin(), s.end());
    rep(i,n){
        if(s[i]=='L') s[i]='R';
        else s[i]='L';
    }
}
    rep(i,n-1) cout<<ans.at(i)<<" ";
    cout<<ans.at(n-1)<<endl;
    return 0;
}


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

public class Main {

    private static long solve(int N, int M, int[] Xs) {
        if (N >= M) {
            return 0;
        }

        Arrays.sort(Xs);

        int[] diffs = new int[M-1];
        for(int i = 1; i < M; i++) {
            diffs[i-1] = Xs[i] - Xs[i-1];
        }

        Arrays.sort(diffs);
        long ans = 0;
        for(int i = 0; i < M - 1 - (N - 1); i++) {
            ans += diffs[i];
        }

        return ans;
    }

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

        final int N = sc.nextInt();
        final int M = sc.nextInt();

        int[] Xs = new int[M];
        for(int i = 0; i < M; i++) {
            Xs[i] = sc.nextInt();
        }

        long ans = solve(N, M, Xs);
        System.out.println(ans);
    }
}


Measured memory_bytes: 49336
A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K = int(input())

print(A[K-1])


Measured memory_bytes: 9184
#include <bits/stdc++.h>
#include <vector>
 
using namespace std;
const double PI=3.14159265358979323846;
 
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {

	int k, a, b;
	cin >> k >> a >> b;

	bool is = false;
	for(int i = a; i <= b; i++) {
		if (!is && i  % k == 0)
			is = true;
	}

	string ans = "NG";
	if (is) ans = "OK";
	cout << ans << endl; 
}



Measured memory_bytes: 3628
<?php
fscanf(STDIN, "%d", $num);
$tmp = trim(fgets(STDIN));
$input = explode(' ', $tmp);
$sum = 0;
$flag = true;
$h = 0;
while ($flag) {
    $flag = false;
    for ($i = $num - 1; $i > $h; $i--) {
        $target = $input[$i];
        if ($input[$i - 1] > $target) {
            $input[$i] = $input[$i - 1];
            $input[$i - 1] = $target;
            $flag = true;
            $sum++;
        }
    }
    $h++;
}
for ($i = 0; $i < $num; $i++) {
    if ($i === $num - 1) {
        echo "$input[$i]\n";
    } else {
        echo $input[$i] . ' ';
    }
}
echo "$sum\n";



Measured memory_bytes: 9268
#include <iostream>
#include <math.h>

using namespace std;

int n;
bool* memo;

int getVal(char c) {
  switch (c) {
  case 'A':
    return 1;
  case 'C':
    return 2;
  case 'G':
    return 3;
  case 'T':
    return 4;
  default:
    return 0;
  }
}

int index(string s) {
  int l = s.size();
  int ans = 0;
  for (int i = 0; i < l; i++) {
    ans += getVal(s[i]) * (int)pow(5, i);
  }
  return ans;
}

void insert(string s) {
  int idx = index(s);
  memo[idx] = true;
}

bool find(string s) {
  int idx = index(s);
  return memo[idx];
}

int main() {
  memo = new bool[(1 << 26)];
  cin >> n;
  string cmd, s;
  for (int i = 0; i < n; i++) {
    cin >> cmd >> s;
    if (cmd == "insert") {
      insert(s);
    } else if (cmd == "find") {
      if (find(s)) {
        cout << "yes" << endl;
      } else {
        cout << "no" << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 12316
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int n;
int q;
int ans[N];
vector < pair < pair < int , int > , int > > event;

int main(){
    scanf("%d%d" , &n , &q);
    for(int i = 1; i <= n; i++){
        int s , t , x;
        scanf("%d%d%d" , &s , &t , &x);
        event.push_back({{s - x , 1} , x});
        event.push_back({{t - x , 0} , x});
    }
    for(int i = 1; i <= q; i++){
        int d;
        scanf("%d" , &d);
        event.push_back({{d , 2} , i});
    }
    multiset < int > xx;
    memset(ans , -1 , sizeof ans);
    sort(event.begin() , event.end());
    for(auto v : event){
        int a = v.first.first;
        int b = v.first.second;
        int c = v.second;
        if(b == 1){
            xx.insert(c);
        } else if(b == 0){
            xx.erase(xx.lower_bound(c));
        } else {
            if(xx.empty())
                continue;
            ans[c] = *xx.begin();
        }
    }

    for(int i = 1; i <= q; i++){
        printf("%d\n" , ans[i]);
    }
}


Measured memory_bytes: 19816
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define inf 1000000007
using namespace std;
int main(){
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	vector<char> t,d;
	for(int i=0;i<q;i++){
		char tt,td;
		cin>>tt>>td;
		t.pb(tt);d.pb(td);
	}
	int ans = n;
	int lef = -1, rig = n;
	while(rig-lef>1){
		int mid = (rig+lef)/2;
		bool fl = false;
		int pos = mid;
		for(int i=0;i<q;i++){
			if( 0<=pos && pos<n && t[i] == s[pos]){
				if(d[i]=='L')pos--;
				else pos++;
			}
			if( pos==-1 )fl = true;
		}
		if(fl){
			lef = mid;
		}
		else{
			rig = mid;
		}
	}
	ans -= rig;
	lef = -1, rig = n;
	while(rig-lef>1){
		int mid = (rig+lef)/2;
		bool fl = false;
		int pos = mid;
		for(int i=0;i<q;i++){
			if( 0<=pos && pos<n && t[i] == s[pos]){
				if(d[i]=='L')pos--;
				else pos++;
			}
			if( pos==n )fl = true;
		}
		if(fl){
			rig = mid;
		}
		else{
			lef = mid;
		}
	}
	ans -= (n-rig);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

template<typename T>
void sort_u(T& v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(),v.end()), v.end());
}

std::vector<int64_t> calc(int a, int b) {
  if(a == b) return std::vector<int64_t>(1,0);
  if(b >= (a+1)/2) return std::vector<int64_t>();
  std::vector<int64_t> res;
  for(int k = b+1; k <= a; ++k) {
    int na = a%k;
    if(na == b) res.push_back((int64_t)1<<k);
    if(b >= (na+1)/2) continue;
    auto tmp = calc(na, b);
    for(int64_t v: tmp) res.push_back(v+((int64_t)1<<k));
  }
  return res;
}

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::vector<int> a(N), b(N);
  std::vector<std::vector<int64_t>> v;
  for(int i = 0; i < N; ++i) std::cin >> a[i];
  for(int i = 0; i < N; ++i) std::cin >> b[i];
  for(int i = 0; i < N; ++i) if(a[i] != b[i]) {
    auto t = calc(a[i], b[i]);
    if(t.size() == 0) fin(-1);
    if(t.size() == 1 && t[0] == 0) continue;
    std::sort(t.begin(), t.end());
    v.push_back(t);
  }
  int64_t ans = 0;
  for(int k = 50; k > 0; --k) {
    int64_t s = (ans | ((int64_t)1<<k)-1);
    for(auto const& vv: v) {
      bool ok = false;
      for(int64_t x: vv) if((x&s)==x) { ok = true; break; }
      if(!ok) ans |= ((int64_t)1<<k);
    }
  }
  fin(ans);
  return 0;
}


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

int main() {
  int N, K, sum = 1;
  cin >> N >> K;
  rep(i, N){
  if(sum + K <= sum * 2){
    sum += K;
   }else{
    sum *= 2;
   }
  }
  cout << sum <<endl;
  return 0;
}


Measured memory_bytes: 3532
#include<bits/stdc++.h>
#define ll long long int
#define loop(i,a,b) for(i=a;i<b;i++)
#define INF 10000000000
#define pb push_back
#define lim 100001

using namespace std;
int main()
{ll n,i,j,ans=0;
	unordered_map<ll,ll> cnt,mp;
	vector<ll> v;
	cin>>n;

	loop(i,0,n)
	 {ll a;
	 	cin>>a;
	 	if(!cnt[a])
	 		v.pb(a);
	 	cnt[a]++;}

	 sort(v.begin(),v.end());

	 loop(i,0,v.size())
	 {
	 	if(mp[v[i]])
	 		continue;
	 		if(cnt[v[i]]==1)
	 	     	ans++;
	 	for(j=2*v[i];j<=1000000;j+=v[i])
	 		mp[j]=1;}

	 	cout<<ans<<endl;return 0;}

Measured memory_bytes: 52376
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

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

	string s;
    cin>>s;
    cout<<string(s.size(),'x')<<endl;
}


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

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

int n;
int a[100010];

int main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}

	sort(a, a + n);

	int t = a[n-1];

	int md = -1;
	int p = -1;

	rep(i, n-1) {
		int d = min(a[i], t-a[i]);
		if (md == -1 || d > md) {
			p = a[i];
			md = d;
		}
	}

	cout << t << " " << p << endl;	
	return 0;
}

Measured memory_bytes: 640