akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int main()
{
int n,i;
int a,b,c;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d %d",&a,&b,&c);
if((a*a) == (b*b+c*c) || (b*b) == (c*c+a*a) || (c*c) == (a*a+b*b))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}

Measured memory_bytes: 580
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long 
#define mp make_pair
#define pb push_back
# define pi 3.14159265358979323846
#define reus ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int32_t main()
{
	reus;
	int n;
	cin>>n;
	string s;
	while(n>0)
	{
		int x=n%26;
		if(x==0)
		{
			s+='z';
			n/=26;
			n--;
		}
		else
		{
			s+=(char(96+x));
			n/=26;
		}
	}
	reverse(s.begin(),s.end());
		cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 3632
n, m = map(int, input().split())
a = []
for _ in range(n):
    a.append(input())

b = []
for _ in range(m):
    b.append(input())

for sy in range(n):
    for sx in range(n):
        # start point
        if sy + m - 1 >= n or sx + m - 1 >= n:
            break

        ok = True
        for y in range(m):
            for x in range(m):
                if a[sy + y][sx + x] != b[y][x]:
                    ok = False
        if ok:
            print('Yes')
            exit()
print('No')


Measured memory_bytes: 40048
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val aa = readLine()!!.split(" ").map{it.toInt()}
    val nums = mutableMapOf<Int, Int>()

    aa.forEach {
        nums[it] = (nums[it] ?: 0) + 1
    }

    var max = 0
    nums.keys.forEach {
        val sum = (nums[it-1] ?: 0) + nums[it]!! + (nums[it+1] ?: 0)
        if (sum > max) max = sum
    }

    println(max)
}

Measured memory_bytes: 56500
n,x=map(int,input().split())
a=list(map(int,input().split()))
A=0
for i in range(len(a)):
  A += a[i]
if A < x:
  print(n-1)
else:
  b=sorted(a)
  c=0
  ans=0
  for _ in range(len(a)):
    c += b[_]
    if c <= x:
      ans += 1
    else:
      break
  print(ans)


Measured memory_bytes: 3060
#include<iomanip>
#include <string>
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
#include<math.h>
#include <ctype.h>
#include <algorithm> // sort
#include <map> // pair
using namespace std;
#define nin(n) int n; cin >> n;
#define kin(k) int k; cin >> k;
const int INF = 1001001001;
int main(){
  int n;cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  vector<int> c(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  for(int i=0;i<n;i++){
    cin >> b.at(i);
  }
  for(int i=0;i<n-1;i++){
    cin >> c.at(i);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    ans+=b.at(i);
  }
  for(int i=0;i<n-1;i++){
    if((a.at(i+1)-a.at(i))==1){ 
      ans+=c.at(a.at(i)-1);
    }
  }
  cout << ans;
}
  

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

using namespace std;

long long N, K;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> N >> K;
	long long md = (N % K);
	long long dif = K - md;
	cout << min(md, dif);
	
	return 0;
}



Measured memory_bytes: 256
A,B,C,D = map(int,input().split())

def gcd(x,y):
    if(x == 0):
        return y
    if(y == 0):
        return x
    if(x >= y):
        return gcd(y,x%y)
    if(x < y):
        return gcd(y%x,x)

l = (C * D) // gcd(C,D)

p = B//C - (A-1)//C
q = B//D - (A-1)//D
r = B//l - (A-1)//l
s = p + q - r
print(B-A+1-s)

Measured memory_bytes: 9208
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl
#define show2(a, n, m) rep(i, n) { rep(j, m) {cout << a[i][j] << ' ';} cout << endl;} 
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef long double ld;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MAX = 100000;
const int N = 100010;

const int MOD = 2019;
struct mint {
	ll x;
	mint(ll x=0):x((x%MOD+MOD)%MOD){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {if ((x+=a.x)>=MOD) x-=MOD; return *this;}
	mint& operator-=(const mint a) {if ((x+=MOD-a.x)>=MOD) x-=MOD; return *this;}
	mint& operator*=(const mint a) {(x*=a.x)%=MOD; return *this;}
	mint operator+(const mint a) const {mint res(*this); return res+=a;}
	mint operator-(const mint a) const {mint res(*this); return res-=a;}
	mint operator*(const mint a) const {mint res(*this); return res*=a;}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
 		return a;
	}

	// for prime mod
	mint inv() const { return pow(MOD-2);}
	mint& operator/=(const mint a) { return (*this) *= a.inv();}
	mint operator/(const mint a) const {mint res(*this); return res/=a;}
};

int main() {
//	cout << fixed << setprecision(15);
	string s;
	cin >> s;
	map<ll, int> mp;
	ll ans = 0;
	mint base = 1;
	mint comp = 0;
	mp[comp.x]++;
	rep(i, s.size()) {
		mint x = (s[i] - '0');
		comp -= x * base;
		base *= mint(202);
		ans += mp[comp.x];
		mp[comp.x]++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3784
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n;
    cin >> n;
    map<int, int> cnt;
    rep(i,n){
        int a;
        cin >> a;
        cnt[a-1]++;
        cnt[a]++;
        cnt[a+1]++;
    }
    int ans = 0;
    for(auto p : cnt){
        chmax(ans, p.second);
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
void SRAND(){auto duration = std::chrono::system_clock::now().time_since_epoch();auto millis = std::chrono::duration_cast<std::chrono::milliseconds>(duration).count();srand(millis);}

ll n,x,c;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	REP1(i,n){
		cin>>x;
		c+=(x!=i);
	}
	cout<<(c<=2?"YES":"NO");
	return 0;
}



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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 2e5+5;

int N, A[mxN];

void die() { cout << -1 << '\n'; exit(0); }

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> N;
    FOR(i,1,N){
		cin >> A[i];
	}
	
	if (A[1] > 0) die();
	FOR(i,1,N-1){
		if (A[i+1]-A[i] > 1) die();
	}
	
	ll ans = 0;
	FOR(i,2,N){
		if (A[i]-A[i-1] == 1) ++ans;
		else ans += A[i];
	}
	
	cout << ans << '\n';
}


Measured memory_bytes: 4456
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		int[][] even = new int[100001][2]; //[Number of occurances, which number is analyzed]
		//Needed due to sorting mixing indices up
		int[][] odd = new int[100001][2];
		int ans = 0;
		for (int i = 0; i < N; i++) {
			int x = input.nextInt();
			if (i%2==0) {
				even[x][0]++;
				even[x][1]=x;
			} 
			else {
				odd[x][0]++;
				odd[x][1]=x;
			} 
		}
		Arrays.sort(even,(a,b)->Integer.compare(a[0], b[0]));
		Arrays.sort(odd,(a,b)->Integer.compare(a[0], b[0]));
		if (even[100000][1]!=odd[100000][1]) {
			ans+=N/2-even[100000][0];
			ans+=N/2-odd[100000][0];
		}else {
			int sub = Math.max(even[100000][0]+odd[99999][0], odd[100000][0]+even[99999][0]);
			ans+=N-sub;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 68340
#include <iostream>

using namespace std;

int main(){
  long p = 1;
  int N;
  cin >> N;
  
  for(int i = 1; i <= N; i++){
    p *= i;
    p %= 1000000007; //(int)(1e9 + 7);
  }

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


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;

int main(void){

	int x,i,s=0;
	for(i=1;i<=5;i++){
		cin >> x;
		if(x>=40) s+=x;
		else s+=40;
	}

	cout << s/5 << endl;

	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,sum=0;
    cin>>n;
    a=n;
    for(int i=n;i>=1;i--)
    {
        sum=sum+n%10;
        n=n/10;

    }
    if(a%sum==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}


Measured memory_bytes: 256
N, M, C =map(int, input().split())
B = list(map(int, input().split()))
ans = 0
for n in range(N):
    count = C
    A = list(map(int, input().split()))
    for m in range(M):
        count += A[m] * B[m]
    if count > 0:
        ans += 1
print(ans)    
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int x,A,B;
    cin >>x>>A>>B;

    int a=A-x,b=B-x;
    if(a<0)a*=-1;
    if(b<0)b*=-1;

    if(a<b)cout<<"A"<<endl;
    else cout<<"B"<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
    
#define int long long int
#define vi vector<int>
#define vvi vector<vi>
#define read(a)  for(int i = 0; i < n; i++) cin >> a[i];
#define print(a)  for(int i = 0; i < n; i++) cout << a[i] << " ";
#define pb push_back
#define pql priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define pqlv priority_queue<vi>
#define pqsv priority_queue<vi, vvi, greater<vi>>
#define endl '\n'
#define N 10000002
#define MOD 1000000007

signed main() {
    int n;
    cin >> n;
    vi a(n);
    map<int, int> mp;
    int sum = 0;
    int xr = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        xr ^= a[i];
    }
    for(int i = 0; i < n; i++) {
        cout << (a[i] ^ xr) << " ";
    }
}

Measured memory_bytes: 4832
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<20)
#define LLINF (1LL<<60)
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
    int n, num[200005]={};
    cin >> n;
    rep(i,n-1){
        int t;
        cin >> t;
        num[t]++;
    }
    for (int i = 1; i <= n;i++){
        cout << num[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 4400
INF = 1000000000
n, m, x = gets.split.map(&:to_i)
a = []
c = []
n.times do |i|
  tmp = []
  a[i] = []
  tmp = gets.split.map(&:to_i)
  c[i] = tmp[0]
  a[i] = tmp.slice(1,m)
end

ans = INF
(1<<n).times do |i|
  cost = 0
  prog = []
  prog = prog.fill(0,0..m-1)
  n.times do |j|
    # j番目の参考書を買う
    if i[j] == 1
      cost += c[j]
      a[j].each_with_index do |v, k|
        prog[k] += v
      end
    end
  end
  
  if prog.all?{ |v| v >= x }
    ans = [ans, cost].min
  end
end

if ans == INF
  ans = -1
end

puts ans


Measured memory_bytes: 14288
import re
N = int(input())
S = input()
ans = 0
tmp = [[m.start() for m in re.finditer(str(i), S)] for i in range(10)]
for i in range(10):
  if len(tmp[i]) == 0:
    continue
  for j in range(10):
    if len(tmp[j]) == 0:
      continue
    for k in range(10):
      if len(tmp[k]) == 0:
        continue
      l = tmp[i][0]
      flag = True
      for m in tmp[j]:
        if m > l:
          flag = False
          break
      if flag:
        continue
      for n in tmp[k]:
        if n > m:
          ans += 1
          break
print(ans)

Measured memory_bytes: 4552
#include<stdio.h>

int main(void){
	int X,Y, N;
	int A[1000];
	int i=0;
	//while((scanf("%d",&X))!='\n'){
	//	N=X; //????´???°
	//}
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%d",&A[i]);
	}
	int change=0; //???????????°
	for(int i=0; i< N-1; i++){
		for(int j=N-1; j>i; j--){
			if(A[j-1] > A[j]){
				int stock = A[j];
				A[j] = A[j-1];
				A[j-1] = stock;
				change++;
			}
		}
	}

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

Measured memory_bytes: 1832
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;

int main(){
  	ll N;
    cin >> N;
    cout << N*(N-1)/2 <<endl;

    
  	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
struct UnionFind {
	vector<int> par, s;
	UnionFind(int N) : par(N), s(N, 1) { rep(i, 0, N)par[i] = i; }
	int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
	void unite(int x, int y) { x = root(x), y = root(y); if (x == y)return; if (s[x] < s[y])swap(x, y); s[x] += s[y]; par[y] = x; }
	bool same(int x, int y) { return root(x) == root(y); }
	int size(int x) { return s[root(x)]; }
	map<int, int> cnt() { map<int, int> cnt; rep2(v, par)cnt[root(v)]++; return cnt; }
};
int main()
{
	ll n, m;
	cin >> n >> m;
	vector<int> a(m), b(m);
	rep(i, 0, m)cin >> a[i] >> b[i], a[i]--, b[i]--;
	UnionFind tree(n);
	vector<ll> A;
	reverse(all(a));
	reverse(all(b));
	ll k = n * (n - 1) / 2;
	rep(i, 0, m) {
		A.push_back(k);
		if (!tree.same(a[i], b[i])) {
			k -= (ll)tree.size(a[i]) * (ll)tree.size(b[i]);
			tree.unite(a[i], b[i]);
		}
	}
	reverse(all(A));
	rep2(v, A)printf("%lld\n", v);
	return 0;
}


Measured memory_bytes: 5776
# B
def palindrome(string): return True if string==string[::-1] else False

S = input()
ans = 0
if len(S) % 2 == 0:
    for i in range(len(S) // 2):
        if S[i] == S[-i-1]:
            pass
        else:
            ans += 1
else:
    for i in range(len(S) // 2):
        if S[i] == S[-i-1]:
            pass
        else:
            ans += 1
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <algorithm>

#define endl "\n"

using namespace std;

template<typename T>
void printArray(T a) {
    for(auto i : a)
        cout << i << " ";

    cout << endl;
}

template<typename T>
void print2DArray(T a) {
    for(auto i : a) {
        for(auto j : i)
            cout << j << " ";

        cout << endl;
    }
    cout << endl;
}

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

    int m = 1;
    int d = 1;

    cin >> m >> d;
    
    if (d < 22) {
        cout << 0 << endl;
        return 0;
    }

    unsigned long long acc = 0;

    for (int i = 22; i <= d; i++) {
        int d_1 = i % 10;
        int d_10 = (i / 10) % 10;

        if (d_1 < 2 || d_10 < 2) {
            continue;
        }

        if (d_1 * d_10 <= m) {
            /* cout << d_1 * d_10 << "-" << i << endl; */
            acc++;
        }
    }

    cout << acc << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long N;
    cin >> N;
    long long A, B;
    cin >> A >> B;
    if(N % (A + B) == 0) cout << N / (A + B) * A << endl;
    else if(N % (A + B) >= A) cout << N / (A + B) * A + A << endl;
    else if(N % (A + B) < A) cout << N / (A + B) * A + N % (A + B) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define inf 10000000
using namespace std;
typedef long long int ll;

int main(){

    int A,B,C,ans;

    cin >> A >> B >> C;

    for(ans=0 ; ((A+B)>0)&&(C>0) ; ){
        C--;
        ans++;
        if(A>0){
            A--;
        }else if(B>0){
            B--;
            ans++;
        }
    }

    if((C>0)&&((A+B) == 0)){
        C--;
        ans++;
    }

    if((C == 0)&&((A+B)>0)){
        ans += B;
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
"use strict";
    
const main = arg => {
	const packs = arg.split("\n")[0].split(" ").map(n=>parseInt(n)).sort((a,b)=>b-a);
	console.log(packs[0] === packs[1] + packs[2] ? "Yes" : "No");
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

int n,m;
vector<int> par(200000);

int root(int x){
    if(par[x] == x)return x;
    return par[x] = root(par[x]);
}

void unite(int x,int y){
    x = root(x),y = root(y);
    if(x == y)return;
    par[x] = y;
}

int main(void){
    cin >> n >> m;
    
    int p[n],x[m],y[m];
    for(int i = 0;i < n;i++){
        cin >> p[i];p[i]--;
        par[i] = i;
    }
    
    for(int i = 0;i < m;i++){
        cin >> x[i] >> y[i];
        unite(x[i]-1,y[i]-1);
    }
    
    int alina = 0;
    for(int i = 0;i < n;i++){
        if(root(i) == root(p[i]))alina++;
    }
    cout << alina << endl;
}

Measured memory_bytes: 5020
(defn shift-only [n a]
  (loop [counter 0 arr a]
    (if (not-every? even? arr)
        counter
        (recur (+ counter 1) (map #(/ % 2) arr)))))

(defn create-data [s]
  (map #(bigint %) (.split s " ")))

(println (shift-only (Long/parseLong (read-line)) (create-data (read-line))))

Measured memory_bytes: 68744
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return S().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1) if i else self.sum(j - 1)


n = I()
s = list(S())
q = I()
D = defaultdict(lambda:BIT(n))
for j in range(n):
    D[s[j]].add(j, 1)

for _ in range(q):
    qi, i, c = LS()
    if qi == "1":
        i = int(i) - 1
        D[s[i]].add(i, -1)
        D[c].add(i, 1)
        s[i] = c
    else:
        l, r = int(i) - 1, int(c)
        ret = 0
        for k in range(97, 123):
            if D[chr(k)].interval_sum(l, r):
                ret += 1
        print(ret)






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

int main(){
    int N;
    cin >> N;
    vector<int> W(N);
    int sum = 0;
    for(int i = 0;i < N;i++){
        cin >> W[i];
        sum += W[i];
    }
    int ans = sum;
    int sub_sum = 0;
    for(int i = 0;i<N-1;i++){
        sub_sum += W[i];
        ans = min(ans,abs(sum-2*sub_sum));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
def main():
    A = [[int(i) for i in input().split()] for j in range(3)]
    seen = [[False]*3 for j in range(3)]
    N = int(input())
    for i in range(N):
        b = int(input())
        for j in range(3):
            for k in range(3):
                if A[j][k] == b:
                    seen[j][k] = True
    flag = False
    for i in range(3):
        if all(seen[i]):
            flag = True
    for i in range(3):
        if all([seen[0][i], seen[1][i], seen[2][i]]):
            flag = True
    if all([seen[0][0], seen[1][1], seen[2][2]]) or \
            all([seen[0][2], seen[1][1], seen[2][0]]):
        flag = True
    if flag:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
const MOD: u64 = 1_000_000_007;

fn main() {
    let mut input = Input::new();

    let n: u64 = input.parse();
    let k: u64 = input.parse();

    let mut ans: u64 = 1;
    for i in k..=n {
        let u = (n + (n - i + 1)) * i / 2;
        let l = (i - 1) * i / 2;
        ans += u - l + 1;
        ans %= MOD;
    }

    println!("{}", ans);
}

struct Input(Vec<String>);

#[allow(dead_code)]
impl Input {
    fn new() -> Self {
        Self(Vec::new())
    }
    fn read(&self) -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).expect("read() failed.");
        s
    }
    fn fill(&mut self) {
        let s = self.read();
        self.0 = s.split_whitespace().map(String::from).rev().collect();
    }
    fn parse<T: std::str::FromStr>(&mut self) -> T {
        if self.0.len() == 0 {
            self.fill();
        }
        self.0.pop().unwrap().parse().ok().unwrap()
    }
}


Measured memory_bytes: 2136
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string St[] = { "0", "Sunny", "Cloudy", "Rainy", "Sunny"};
    string s;
    cin >> s;
    for(int i = 1; i <= 10; i++)
    {
        string tem = St[i];
        if(s.compare(tem) == 0)
        {
            cout << St[i+1] << endl;
            break;
        }
    }
    return 0;
}


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

int a, b;

int main() {
	cin >> a >> b;
	if (a <= 0 && b >= 0) {puts("Zero"); return 0;}
	if (((b - a + 1) %2 == 1) && b < 0){puts("Negative"); return 0;}
	puts("Positive");
	return 0; 
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
using namespace std;
int h,n,f[20005],a[1005],b[1005];
int main(){
	cin>>h>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=a[i];j<=20000;j++)f[j]=min(f[j],f[j-a[i]]+b[i]);
	}
	int ans=0x3f3f3f3f;
	for(int i=h;i<=20000;i++)ans=min(ans,f[i]);
	cout<<ans;
}


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

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

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 endl "\n"
#define int long long


const int N= 6115;
int t,n;







int32_t main()
{
	IOS;
	cin>>n;
	int ans= (n/500) * 1000;
	n%=500;
	ans+= (n/5)*5;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
def resolve():
    H, W, M = map(int, input().split())
    pos = []
    for _ in range(M):
        pos.append(list(map(int, input().split())))

    h_totals = [0] * (H+1)
    w_totals = [0] * (W+1)
    overlap = [set() for _ in range(H+1)]

    for ph, pw in pos:
        h_totals[ph] += 1
        w_totals[pw] += 1
        overlap[ph].add(pw)

    max_h = -1
    max_w = -1
    h_list = []
    w_list = []
    for i in range(1, H+1):
        if h_totals[i] > max_h:
            max_h = h_totals[i]
            h_list = [i]
        elif h_totals[i] == max_h:
            h_list.append(i)
    for j in range(1, W+1):
        if w_totals[j] > max_w:
            max_w = w_totals[j]
            w_list = [j]
        elif w_totals[j] == max_w:
            w_list.append(j)

    for i in h_list:
        for j in w_list:
            if j not in overlap[i]:
                print(max_h + max_w)
                return
    print(max_h + max_w - 1)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 229708
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if 0 > x]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
	
N, M = MAP()
AB = [LIST() for _ in range(M)]

tree = UnionFind(N)
for A, B in AB:
	tree.union(A-1, B-1)

ans = 0
for i in tree.roots():
	ans = max(ans, tree.size(i))

print(ans)

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


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

    vector<int> x(n), y(n);
    for(int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];

    vector<int> p(n);
    for(int i = 0; i < n; ++i)
        p[i] = i;

    double len = 0;
    int cnt = 0;
    do {
        for(int i = 0; i < n - 1; ++i)
        {
            double dx = x[p[i]] - x[p[i + 1]];
            double dy = y[p[i]] - y[p[i + 1]];
            len += sqrt(dx * dx + dy * dy);;
        }
        cnt++;
    } while(next_permutation(p.begin(), p.end()));

    double res = len / cnt;
    cout << setprecision(10) << fixed << res << "\n"; 
    return 0;
}

Measured memory_bytes: 3820
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define mp make_pair
#define ss second
#define ff first

vector<int> coi;

int dp[100007];

int solve(int n)
{
	if(n==0)
	return 0;
	
	if(dp[n]!=-1)
		return dp[n];

	int temp=INT_MAX;
	for(int i=0;i<coi.size();i++)
	{
		if(coi[i]<=n)
		{
			temp=min(temp,1+solve(n-coi[i]));
		}
	}
	dp[n]=temp;
	return temp;
}

int main() 
{
	memset(dp,-1,sizeof(dp[0])*100007);
	coi.pb(1);
	int p6=6;
	int p9=9;
	while(p6<=100000)
	{
		coi.pb(p6);
		p6*=6;
	}
	while(p9<=100000)
	{
		coi.pb(p9);
		p9*=9;
	}

	int n;
	cin>>n;
	cout<<solve(n)<<endl;

	return 0;
}






Measured memory_bytes: 3712
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)){
			
			System.out.println(sc.next().matches(".*C.*F.*") ? "Yes" : "No");
		}
	}
}

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

typedef long long ll;

int n;

int main(){

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

    cin>>n;
    vector<ll> d(n);
    vector<int> w(n,1);
    map<ll,int> mp;
    for(int i=0;i<n;i++){
        cin>>d[i];
        mp[d[i]]=i;
    }
    vector<pair<int,int> > res;
    for(int tm=1;tm<n;tm++){
        map<ll,int>::reverse_iterator it=mp.rbegin();
        int i=it->second;
        ll wt=d[i]-n+w[i]+w[i];
        if(mp.find(wt)==mp.end()||mp[wt]==i){
            cout<<-1<<endl;
            return 0;
        }
        int j=mp[wt];
        res.emplace_back(i,j);
        w[j]+=w[i];
        mp.erase(--mp.end());
    }
    vector<ll> rd(n,-1);
    rd[0]=0;
    vector<vector<int> > g(n);
    for(pair<int,int> p : res){
        g[p.first].push_back(p.second);
        g[p.second].push_back(p.first);
    }
    vector<int> q(1,0);
    for(int b=0;b<q.size();b++){
        for(int j:g[q[b]]){
            if(rd[j]==-1){
                q.push_back(j);
                rd[j]=rd[q[b]]+1;
            }
        }
    }
    if(accumulate(rd.begin(),rd.end(),0ll)!=d[0]){
        cout<<-1<<endl;
        return 0;
    }
    for(pair<int,int> p : res){
        cout<<p.first+1<<' '<<p.second+1<<endl;
    }

    return 0;
}

Measured memory_bytes: 10488
#include <stdio.h>
int main() {
  int k, a, b, count = 0;
  scanf("%d %d %d", &k, &a, &b);
  for (int i = a; i <= b; i++) {
    if (i % k == 0) {
      printf("OK");
      count = i;
      break;
    }
  }
  if (count == 0) {
    printf("NG");
  }
  return 0;
}

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

int main() {
	// your code goes here
	int h,r;
	cin>> h>> r;
	if(h<-1*r)cout<< -1<<endl;
	else if(h>-1*r)cout<< 1<< endl;
	else cout<< 0<<endl;
	
	return 0;
}


Measured memory_bytes: 3092
using System;
using System.Collections;
using System.IO;
using System.Linq;

namespace CompetitiveProgramming
{

  class Solve
  {

    const int INF = (int)(1e9) + 10;

    string ArrangeName(string str)
    {
      string ret = str[0] + "";

      bool isMother = false;
      if (str[0] == 'a' || str[0] == 'i' || str[0] == 'u' || str[0] == 'e' || str[0] == 'o')
      {
        isMother = true;
      }

      for (int i = 1; i < str.Length; i++)
      {
        if (isMother)
        {
          ret += str[i];
        }
        if (str[i] == 'a' || str[i] == 'i' || str[i] == 'u' || str[i] == 'e' || str[i] == 'o')
        {
          isMother = true;
        }
        else
        {
          isMother = false;
        }
      }

      return ret;
    }
    private void main()
    {
      while (true)
      {
        int N = int.Parse(Console.ReadLine());
        if (N == 0)
        {
          break;
        }
        string[] s = new string[N];
        int sizeMax = 0;
        for (int i = 0; i < N; i++)
        {
          s[i] = ArrangeName(Console.ReadLine());
          sizeMax = Math.Max(sizeMax, s[i].Length);
        }


        Hashtable ht = new Hashtable();
        bool isDifferentAll = false;
        for (int i = 0; i < sizeMax; i++)
        {
          bool isDifferent = true;
          foreach (var e in s)
          {

            string str = e.Substring(0, Math.Min(e.Length, i + 1));
            if (ht[str] != null)
            {
              ht.Clear();
              isDifferent = false;
              break;
            }
            ht[str] = true;
          }
          if (isDifferent)
          {
            isDifferentAll = true;
            Console.WriteLine(i + 1);
            break;
          }
        }

        if (!isDifferentAll)
        {
          Console.WriteLine(-1);
        }

      }
    }


    public Solve()
    {
      Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
      main();
      Console.Out.Flush();
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      new Solve();
    }
  }
}

Measured memory_bytes: 9456
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;

char st[5010];
int f[5010][5010];

int main()
{
    int n;scanf("%d",&n);
    scanf("%s",st+1);
    int ans=0;
    for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++)
    {
        if (st[i]==st[j]) f[i][j]=f[i-1][j-1]+1;
        else f[i][j]=0;
        //printf("%d %d %d\n",i,j,f[i][j]);
        if (f[i][j]>j-i) f[i][j]=j-i;
        if (f[i][j]>ans) ans=f[i][j];
    }
    printf("%d\n",ans);

}


Measured memory_bytes: 96896
n = int(input())
import numpy as np
li = np.array([ int(it) for it in input().split()])
cs = np.cumsum(li)
import collections
cd = collections.Counter(cs)
sm = 0
for k,v in cd.items():
  p = v - 1 + (1 if k==0 else 0)
  sm += (p*(p+1))//2
print (sm)

Measured memory_bytes: 39352
import copy
import heapq
import math
import fractions

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printmultiplerow(a):
    for i in a:
        print(i)
def printrow(a):
    for i in range(len(a)-1):
        print(a[i],end = " ")
    print(a[-1])

n = ip()
a = [0]
a.extend(iprow())
a.append(0)
sub = []
jsub = []
n+=2
for i in range(n-1):
    sub.append(abs(a[i+1]-a[i]))
for i in range(n-2):
    jsub.append(abs(a[i+2]-a[i]))
s = sum(sub)
s-=sub[0]
for i in range(n-2):
    s-=sub[i+1]
    print(s+jsub[i])
    s+=sub[i]

Measured memory_bytes: 18248
#include <iostream>
using namespace std;
int main(void){
  int x,y;
  while (1){
    cin >> x >> y;
    if (x==0&&y==0) break;
    if (x<y) cout << x << ' ' << y << endl;
    else cout << y << ' ' << x << endl;
  }
  return 0;
}


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

string calc(string &s, string formula, int sum, int i) {
  // ベースケース
  if (i == (int) s.size()) {
    if (sum == 7) {
      return formula + '=' + to_string(sum);
    } else {
      return "";
    }
  }
  // 再帰ステップ
  stringstream ss;
  int num;
  ss << s[i];
  ss >> num;

  string calculated;
  // 加算
  calculated = calc(s, formula + '+' + s[i], sum + num, i + 1);
  if (calculated == "") {
    // だめなら減算
    calculated = calc(s, formula + '-' + s[i], sum - num, i + 1);
  }

  return calculated;
}

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

  string formula;
  formula.push_back(s[0]);

  stringstream ss;
  int sum;
  ss << s[0];
  ss >> sum;

  formula = calc(s, formula, sum, 1);

  cout << formula << endl;
  return 0;
}

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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, m, n) for (ll i = (m); i < (n); i++)
#define FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    vector<ll> d(n);
    vector<ll> chk(101, 0);
    REP(i, n)
    {
        cin >> d[i];
        chk[d[i]] = 1;
    }
    cout << accumulate(ALL(chk), 0) << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())

graph = [[] for _ in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    graph[u-1].append([v-1,w])
    graph[v-1].append([u-1,w])

from collections import deque
q = deque()
q.append(0)    
seen = [-1]*n
seen[0] = 0  #Node0 White    

while q:
    node = q.pop()
    for pair,length in graph[node]:
        if seen[pair]==-1:
            q.append(pair)
            if length%2 == 0:
                if seen[node] == 0:
                    seen[pair] = 0
                if seen[node] == 1:
                    seen[pair] = 1
            else:
                if seen[node] == 0:
                    seen[pair] = 1
                if seen[node] == 1:
                    seen[pair] = 0                         
for i in range(n):
    print(seen[i])

Measured memory_bytes: 84896
#include <bits/stdc++.h>
using namespace std;
#define sci1(a) scanf("%d",&a)
#define sci2(a,b) scanf("%d %d",&a,&b)
#define sci3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define scs(s) scanf("%s",s)
#ifndef GET_MACRO

#define GET_MACRO(__1,__2,__3,NAME,...) NAME

#endif // GET_MACRO

#define sci(...) GET_MACRO(__VA_ARGS__,sci3,sci2,sci1)(__VA_ARGS__)
#define ll long long
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define LSB(i) ((i)&(-i))
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define infl 0x7fffffffffffffff
#define infi  0x7fffffff
#define fill_(a,b) fill(a.begin(),a.end(),b)
template <class T>T n_inverse_mod_m(T n,T m){
    T rn_1,rn,sn_1,sn,tn_1,tn,tr,ts,tt,q;
    rn_1=n;sn_1=1;tn_1=0;
    rn=m;sn=0;tn=1;
    while(1){
        tr=rn_1%rn;
        q=(rn_1-tr)/rn;
        ts=sn_1-(q*sn);
        tt=tn_1-(q*tn);
        if(tr==0){
            return (sn+m)%m;
        }
        sn_1=sn;sn=ts;
        tn_1=tn;tn=tt;
        rn_1=rn;rn=tr;
    }
}
ll mod=1000000007ll;
ll fact(int n){
    ll rval=1;
    for(int i=1;i<=n;i++){
        rval=(rval*(ll)i)%mod;
    }
    return rval;
}
int main(){
    int x,y;
    int l,u;
    sci(x,y);
    l=2*x-y;
    u=2*y-x;
    if(l%3){
        printf("0\n");
        return 0;
    }
    if(u%3){
        printf("0\n");
        return 0;
    }
    if(l<0||u<0){
        printf("0\n");
        return 0;
    }
    l/=3;
    u/=3;
    ll t1=fact(l+u);
    ll t2=fact(l);
    ll t3=fact(u);
    t1=(t1*n_inverse_mod_m(t2,mod))%mod;
    t1=(t1*n_inverse_mod_m(t3,mod))%mod;
    cout<<t1<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
template <class T> void chmax(T& x, T y) { if (x < y) x = y; }
string S;
int dp[300][300][151];
int recur(int i, int j, int k) {
    if (dp[i][j][k] != -1) {
        return dp[i][j][k];
    } else if (i > j) {
        return dp[i][j][k] = 0;
    } else if (i == j) {
        return dp[i][j][k] = 1;
    } else if (S[i] == S[j]) {
        return dp[i][j][k] = recur(i + 1, j - 1, k) + 2;
    } else {
        int ret = 0;
        chmax(ret, recur(i + 1, j, k));
        chmax(ret, recur(i, j - 1, k));
        if (k > 0) chmax(ret, recur(i + 1, j - 1, k - 1) + 2);
        return dp[i][j][k] = ret;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> S;
    int K; cin >> K;
    K = min(K, (int)S.size() / 2);
    for (int i = 0; i < S.size(); i++) {
        for (int j = 0; j < S.size(); j++) {
            for (int k = 0; k <= K; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
    cout << recur(0, S.size() - 1, K) << endl;
    return 0;
}


Measured memory_bytes: 53376
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 25;
int A[MAXN][MAXN], B[MAXN];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, M, C; cin >> N >> M >> C;
    for (int i=0; i<M; i++) cin >> B[i];
    int ans = 0;
    for (int i=0; i<N; i++){
        int cur = 0;
        for (int j=0; j<M; j++){
            cin >> A[i][j];
            cur += A[i][j] * B[j];
        }
        if (cur + C > 0) ans++;
    }
    cout << ans;
}


Measured memory_bytes: 256
import std.stdio,std.array,std.string,std.algorithm,std.conv;

immutable STR_LENGTH = 20;

int main(string[] argv)
{
    char[] buf;
	stdin.readln(buf);
	char[] c;

	for(int i = 0;i < STR_LENGTH;i++){
		if(buf.length > i){
			c ~= buf[i];
		}
	}
	reverse(c);
	writeln(c);

    return 0;
}

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

#define EPS (1e-7)
#define INF (1<<25)
#define PI (acos(-1))

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

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

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; }

using ll = long long;

int main() {
  int n; cin >> n;
  vector<int> t(n); REP(i,n) cin >> t[i];
  vector<double> v(n); REP(i,n) cin >> v[i];
  int T = 0; REP(i,n) T += 2*t[i];
  vector<double> a(T+1); REP(x,T+1) a[x] = min(x, T-x)/2.0;
  REP(x, T) {
    int l = 0, r = 0;
    REP(i,n) {
      r += 2*t[i];
      if (x <= l) chmin(a[x], v[i]-(x-l)/2.0);
      else if (x <= r) chmin(a[x], v[i]);
      else chmin(a[x], v[i]+(x-r)/2.0);
      l = r;
    }
  }
  double ans = 0;
  REP(x,T) ans += 0.25*(a[x]+a[x+1]);
  cout << setprecision(17) << ans << endl;
  return 0;
}


Measured memory_bytes: 512
import sys
n,m,x,y=map(int,input().split())
lx=list(map(int,input().split()))
ly=list(map(int,input().split()))
lx.sort()
ly.sort()
if lx[n-1]>=ly[0] or ly[0]<=x or ly[0]>y:
    print('War')
    sys.exit()
else:print('No War')

Measured memory_bytes: 3060
import sys
def I(): return int(sys.stdin.readline().rstrip())
def S(): return sys.stdin.readline().rstrip()

N = I()
s = [''.join(sorted(S())) for i in range(N)]

from collections import Counter

c = Counter(s)
ans = 0
for i in c.keys():
    ans += c[i]*(c[i]-1)//2

print(ans)


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

#define ED return 0;
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) int(pow(x,y))
const long long mod = 1000000007;

int main() {
    string s;
    cin >> s;
    int i = 0;
    bool backIsDream = false;
    bool backIsErase = false;
    while(true){
        if(i == s.size()){
            cout << "YES" << endl;
            ED
        }
        if(s.substr(i,5) == "dream" || s.substr(i,5) == "erase"){
            if(s.substr(i,5) == "dream"){
                backIsDream = true;
                backIsErase = false;
                i += 5;
                continue;
            }
            else{
                backIsDream = false;
                backIsErase = true;
                i += 5;
                continue;
            }
        }
        if(backIsDream && s.substr(i,2) == "er"){
            backIsDream = false;
            i += 2;
            continue;
        }
        if(backIsErase && s.at(i) == 'r'){
            backIsErase = false;
            i++;
            continue;
        }
        cout << "NO" << endl;
        ED
    }
}


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

using namespace std;

double p[42], q[42];

int main() {
  for (int i = 0; i < 6; i++) {
    int foo;
    scanf("%d", &foo);
    p[i] = 0.01 * foo;
  }
  for (int i = 0; i < 6; i++) {
    int foo;
    scanf("%d", &foo);
    q[i] = 0.01 * foo;
  }
  vector <double> pts;
  pts.push_back(0.0);
  pts.push_back(1.0);
  for (int i = 0; i < 6; i++) {
    if (p[i] + q[i] > 1e-14) {
      pts.push_back(q[i] / (p[i] + q[i]));
    }
  }
  double ans = 42.0;
  for (int id = 0; id < (int) pts.size(); id++) {
    double pA = pts[id];
    double total = 0.0;
    for (int i = 0; i < 6; i++) {
      total += max(pA * p[i], (1.0 - pA) * q[i]);
    }
    ans = min(ans, total);
  }
  printf("%.15f\n", ans);
  return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define INF (int)1e9
#define MIN(a,b) (((a)<(b)) ? (a):(b))

int root[102][102];

void init() {
	FOR(i,0,102){
		FOR(j,0,102){
			if(i == j) root[i][j] = 0;
			else root[i][j] = INF;
		}
	}
}

int main(){
	int n,m,a[1002],b[1002],c[1002];

//	memset(root,INF,sizeof(root));
//	FOR(i,0,102) root[i][i] = 0;

	init();

	scanf("%d %d",&n,&m);
	FOR(i,0,m){
		scanf("%d %d %d",&a[i],&b[i],&c[i]);
		root[a[i]][b[i]] = c[i];	//MIN(root[a[i]][b[i]],c[i]);
		root[b[i]][a[i]] = c[i];	//MIN(root[b[i]][a[i]],c[i]);
	}

	FOR(k,1,n+1)	//中継点
		FOR(i,1,n+1)	//始点
			FOR(j,1,n+1)	//終点
				root[i][j] = MIN(root[i][j],root[i][k]+root[k][j]);

	int ans = m;

	FOR(k,0,m)	//判定する辺
			FOR(i,1,n+1)	//始点
				if(root[i][a[k]] + c[k] == root[i][b[k]]){	//最短経路に使用済み
					ans--;
					break;
				}

	printf("%d\n",ans);
}

Measured memory_bytes: 256
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

s=input()
n=len(s)
left=s[:(n-1)//2]
right=s[(n+3)//2-1:]
# print(left)
# print(left[::-1])
if s==s[::-1] and left==left[::-1] and right==right[::-1]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 64748