akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N;
  ll K;
  cin >> N >> K;
  ll A;
  vector<ll> B;
  vector<ll> C;
  ll z = 0;
  for (int i = 0; i < N; i++) {
    cin >> A;
    if (A == 0)
      z++;
    else if (A < 0)
      B.push_back(A);
    else
      C.push_back(A);
  }
  ll nb = B.size();
  ll nc = C.size();
  ll f0 = nb * nc;
  ll f1 = f0 + z * (nb + nc) + (z * (z - 1)) / 2;
  sort(B.begin(), B.end());
  if (K <= f0) {
    sort(C.begin(), C.end(), greater<ll>());
    ll l = -1e18 - 1ll;
    ll r = 0;
    while (r - l > 1) {
      ll m = (l + r) / 2;
      ll sum = 0;
      int j = 0;
      for (int i = nb - 1; i >= 0; i--) {
        while (j < nc && B[i] * C[j] <= m)
          j++;
        sum += j;
      }
      //cout << sum << " " << m << "\n";
      if (sum < K)
        l = m;
      else
        r = m;
    }
    cout << r << "\n";
  } else if (K <= f1) {
    cout << "0\n";
  } else {
    sort(C.begin(), C.end());
    ll l = 0;
    ll r = 1e18 + 1ll;
    while (r - l > 1) {
      ll m = (l + r) / 2;
      ll sum = f1;
      int j = nb - 1;
      for (int i = 0; i < nb - 1; i++) {
        while (j >= 0 && B[i] * B[j] <= m)
          j--;
        sum += min((int) nb - j - 1, (int) nb - i - 1);
      }

      j = 0;
      for (int i = nc - 1; i >= 1; i--) {
        while (j < nc && C[i] * C[j] <= m)
          j++;
        sum += min(i, j);
      }
      // cout << sum << " " << m << "\n";
      if (sum < K)
        l = m;
      else
        r = m;
    }
    cout << r << "\n";
  }
  return 0;
}


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

int main() {
    char c;
    cin >> c;
    if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o'){
        cout << "vowel" << endl;
    }
    else {
        cout << "consonant" << endl;
    }
}


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

long long n, ans;

int main() {
    cin >> n;
    long long sq = sqrt(n);
    for (long long i = 2; i <= sq; i++){
        if (n % i == 0){
            long long tmp = n;
            while (tmp % i == 0) tmp /= i;
            if (tmp % i == 1) ans++;
            long long j = n / i;
            if (j == i) continue;
            tmp = n;
            while (tmp % j == 0) tmp /= j;
            if (tmp % j == 1) ans++;
        }
    }
    sq = sqrt(n-1);
    for (int i = 2; i <= sq; i++){
        if ((n-1) % i == 0){
            ans++;
            long long j = (n-1) / i;
            if (j != i) ans++;
        }
    }
    if (n == 2) ans--;
    cout << ans+2 << "\n";
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int H, W, A, B;
    cin >> H >> W >> A >> B;

    for (int x = 0; x < H; ++x)
    {
        for (int y = 0; y < W; ++y)
        {
            const bool l = x < B;
            const bool u = y < A;
            cout << ((l ^ u) ? 0 : 1);
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include <climits>
#include<vector>
#include<list>
#include<numeric>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int N;
	cin >> N;
	bool yes = false;
	if (N % 4 == 0 || N % 7 == 0) yes = true;
	else {
		for (int i = N / 7;i > 0;i--) {
			if ((N - 7 * i) % 4 == 0) yes = true;
		}
	}
	if (yes) cout << "Yes\n";
	else cout << "No\n";

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
        int[] a=new int[4];
        int[] b=new int[4];
        int h = 0, v=0;
        for(int i=0; i<4; i++) 
        	a[i] = sc.nextInt();
        for(int i=0; i<4; i++) 
        	b[i] = sc.nextInt();
        for(int i=0; i<4; i++) {
        	for(int j=0; j<4; j++) {
        		if(i==j && a[i]==b[j])
        			h++;
        		else if(i!=j && a[i]==b[j])
        			v++;
        	}
        }
        System.out.println(h+" "+v);
        }
    }
}


Measured memory_bytes: 26264
#include<stdio.h>

 int main(){
  int a, b;
 
 scanf("%d %d", &a,&b);
 if(a < b){
 printf("a < b\n");
 } else if(a > b){
 printf("a > b\n");
 } else if(a == b){
 printf("a == b\n");
 }
 return 0;
}
 
 


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

struct edge{
  int to,cost;
};

typedef pair<int,int> pii;
#define MAX_V 100000
#define INF pow(10,9)

int V;
int E;
int r;
vector<edge> G[MAX_V];
int d[MAX_V];//???????????¢

void dijkstra(int s){

  priority_queue<pii,vector<pii>,greater<pii> > que;
  fill(d,d+V,INF);
  d[s] = 0;
  que.push(pii(0,s));

  while(!que.empty()){
    pii p = que.top();que.pop();
    int v = p.second;
    if(d[v] < p.first)continue;
    for(int i=0;i<G[v].size();i++){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
	d[e.to] = d[v] + e.cost;
	que.push(pii(d[e.to],e.to));
      }
    }
  }
}

int main(){
  int s,t,D;
  edge e;
  cin>>V>>E>>r;
  for(int i=0;i<E;i++){
    cin>>s>>t>>D;
    e.to = t;e.cost = D;
    G[s].push_back(e);
  }

  dijkstra(r);

  for(int i=0;i<V;i++){
    if(d[i]==pow(10,9))
      cout<<"INF"<<endl;
    else
      cout<<d[i]<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 12960
N = gets.chomp
K = gets.to_i

n = N[0].to_i
a = [1,n-1,0,0,1]
N[1..-1].each_char do |c|
  n = c.to_i
  a_ = [
    1,
    a[0]*9 + a[1],
    a[1]*9 + a[2],
    a[2]*9 + a[3],
    (n==0?a[4]:a[4]+1)
  ]
  a_[a[4]] += 1 if 0 < n && a[4] <= 3
  a_[a[4]+1] += [n-1,0].max if a[4]+1 <= 3
  a = a_
end

ret = a[K] + (a[4]==K ? 1:0)
p ret


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

int main(void) {
    int X,Y,Z,tmp,ans;
    cin >> X >> Y >> Z;
    ans = X / (Y + Z);
    if (X % (Y + Z) < Z) ans--;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
//113B
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
int main(void){
    int n=0, T=0, A=0, h=0, cnt=0;
    double ans =100000.0;
    cin >> n >> T >> A;
    rep(i, n){
        cin >> h;
        if(ans > abs(A-(T -h*0.006))){
            ans = abs(A-(T -h*0.006));
            cnt =i+1;
        }
    }
    cout << cnt << endl;
}

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

typedef long long ll;
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define endl '\n'
const int N = 2e5 + 10;
using namespace std;

int main() {
    IO;
    ll n, tmp;
    cin >> n;
    tmp = n;
    n = (n + 1000 - 1) / 1000;
    n *= 1000;
    cout << n - tmp;


}


Measured memory_bytes: 3580
// 2011/07/27 Tazoe

#include <iostream>
#include <climits>
using namespace std;

int main()
{
	while(true){
		int n;
		cin >> n;
		if(n==0)
			break;

		int wal[2][101];
		for(int i=0; i<2; i++){
			for(int j=0; j<n; j++)
				cin >> wal[i][j];
			wal[i][n] = 0;		// n+1KðÊÌÇÆ·é
		}

		int cnt[2];			// WvÌñ
		for(int i=0; i<2; i++){
			cnt[i] = 0;

			int memo[2] = {0};	// Ç±ÜÅoÁ½©

			int bld = i;		// r
			int flr = 0;		// K
			while(wal[bld][flr]==1&&wal[bld][flr+1]==1)	// Íµ²Ìê
				flr++;
			memo[bld] = flr;

			while(true){
				if(flr>=n-1)		// ÅãKÌê
					break;

				bld = (bld+1)%2;	// ÊÌrÖ
				flr = flr+2;		// 2ÂãÌKÖ

				while(wal[bld][flr]==1&&wal[bld][flr+1]==1)	// Íµ²Ìê
					flr++;

				while(wal[bld][flr]==2)		// ·×éÇÌê
					flr--;

				if(memo[bld]>=flr){		// [vÌê
					cnt[i] = INT_MAX;
					break;
				}
				else{
					memo[bld] = flr;
				}

				cnt[i]++;
			}
		}

		if(cnt[0]==INT_MAX&&cnt[1]==INT_MAX)
			cout << "NA" << endl;
		else if(cnt[0]<cnt[1])
			cout << cnt[0] << endl;
		else
			cout << cnt[1] << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int H, W, N;
int sr, sc;
string S, T;

int main() {
    //cout.precision(10);
    cin >> H >> W >> N;
    cin >> sr >> sc;
    cin >> S >> T;
    int down = H + 1;
    int up = 0;
    int left = 0;
    int right = W + 1;
    for(int i = N - 1; i >= 0; i--) {
        if(T[i] == 'U') down = min(down+1, H+1);
        if(T[i] == 'D') up = max(up-1, 0);
        if(T[i] == 'R') left = max(left-1, 0);
        if(T[i] == 'L') right = min(right+1, W+1);
        if(S[i] == 'U') up++;
        if(S[i] == 'D') down--;
        if(S[i] == 'R') right--;
        if(S[i] == 'L') left++;
        if(down - up <= 1 || right - left <= 1) {
            cout << "NO" << endl;
            return 0;
        }
        //cerr << up << " " << down << " " << left << " " << right << endl;
    }
    if(up < sr && down > sr && right > sc && left < sc) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define REPRl(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < (int)n; i++)
#define FORl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define ALL(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}

int main() {
  int a,b;cin>>a>>b;
  int sum=0;
  REP(i,2){
    if(a>b){
      sum+=a;
      a--;
    }else{
      sum+=b;
      b--;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
import sys


def _s(): return sys.stdin.readline().strip()


def main():
    s = _s()
    l = int(s[-1])
    if l in [2, 4, 5, 7, 9]:
        ans = "hon"
    elif l in [0, 1, 6, 8]:
        ans = "pon"
    else:
        ans = "bon"

    return ans


if __name__ == "__main__":
    print(main())


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

int main(){
  int N, A, B;
  cin >> N >> A >> B;

  long long ans = 0;
  for(int i = 1; i <= N; i++){
    int digit_sum = 0;
    int i_copy = i;
    while(i_copy > 0){
      digit_sum += i_copy % 10;
      i_copy /= 10;
    }
    //cout << i << ' ' << digit_sum << endl;
    if(digit_sum >= A && digit_sum <= B){
      ans += i;
    }
  }

  cout << ans << endl;
}



Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
typedef pair<P,int> PP;

void Main() {
  int n,s,t;
  cin >> n >> s >> t;
  PP a[n];
  rep(i,n) cin >> a[i].F.F >> a[i].F.S >> a[i].S;
  int dp[1000][1000];
  rep(i,1000)rep(j,1000) dp[i][j]=MAX;
  dp[0][0]=0;
  rep(i,n)rrep(j,1000)rrep(k,1000) {
    if(j+a[i].F.F<1000&&k+a[i].F.S<1000) dp[j+a[i].F.F][k+a[i].F.S]=min(dp[j+a[i].F.F][k+a[i].F.S],dp[j][k]+a[i].S);
  }
  int ans=MAX;
  REP(i,1,1000)REP(j,1,1000) {
    ll d=__gcd(i,j);
    ll x=i/d,y=j/d;
    if(x==s&&y==t) ans=min(ans,dp[i][j]);
  }
  if(ans==MAX) ans=-1;
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 4224
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			StringTokenizer tokenizer = new StringTokenizer(scanner.nextLine());
			int n = Integer.parseInt(tokenizer.nextToken());
			int s = tokenizer.countTokens();
			int[] num = new int[s];
			for (int i = 0; i < s; i++) {
				num[i] = Integer.parseInt(tokenizer.nextToken());
			}
			Arrays.sort(num);
			Deque<Integer> que = new ArrayDeque<Integer>();
			for (int t : num) {
				que.offer(t);
			}
			Deque<Integer> deque = new ArrayDeque<Integer>();
			int count = 0;
			while (!que.isEmpty()) {
				if (count % 4 == 0)
					deque.offer(que.pop());
				else if (count % 4 == 1)
					deque.offer(que.pollLast());
				else if (count % 4 == 2)
					deque.push(que.pollLast());
				else
					deque.push(que.pop());
				count++;

			}
			double sum = 0;
			sum += deque.getFirst();
			sum += deque.getLast();
			int a = deque.pop();
			while (!deque.isEmpty()) {
				int b = deque.pop();
				sum += Math.sqrt(a * b) * 2;
				a = b;
			}
			System.out.println(sum <= n ? "OK" : "NA");
		}
	}
}

Measured memory_bytes: 17184
N = int(input())
S = input()
lS = len(S)
l = 0
bw = [0, 0]
for i in range(lS):
    if (S[i] == "."):
        bw[1] += 1

ans = sum(bw)
for i in range(lS):
    if (S[i] == "#"):
        bw[0] += 1
    if (S[i] == "."):
        bw[1] -= 1

    if (ans > sum(bw)):
        ans = sum(bw)

print(ans)


Measured memory_bytes: 3500
#include <stdio.h>
#include <iostream>
using namespace std;

#define MAX 100005
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};


Node gNode[MAX];
int gDepth[MAX],gHeight[MAX];


int getSibling(int u){
   
    if(gNode[u].parent == NIL)return NIL;
   
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
 
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
   
    return NIL;
}

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "sibling = " << getSibling(node) << ", ";
    
    int deg = 0;
    if(gNode[node].left != NIL) deg++;
    if(gNode[node].right != NIL) deg++;
    cout << "degree = " << deg << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    cout << "height = " << gHeight[node] << ", ";
    
    if(gNode[node].parent == NIL){
        cout << "root\n";
    }else if(gNode[node].left == NIL && gNode[node].right == NIL){
        cout << "leaf\n";
    }else{
        cout << "internal node\n";
    }
}


void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}


int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;

    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
       
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

 
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    setDepth(root, 0);
    setHeight(root);
    
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}


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

vector<int> root;
vector<int> Rank;

//通常バージョン
int find(int x){
    if (root[x] == x) return x;
    root[x] = find(root[x]);
    return root[x];
}

bool check(int x, int y){
    return find(x) == find(y);
}

void Union(int x, int y){
    x = find(x); y = find(y);
    if (check(x, y)){
        return;
    }
    if (Rank[x] >= Rank[y]) root[y] = x;
    else root[x] = y;
    if (Rank[x] == Rank[y]) Rank[x]++;
}

int main(){
    int n;
    cin >> n;
    vector<int> set_root(n);
    for (int i = 0; i < n; i++) set_root[i] = i;
    root = set_root;
    vector<int> set_Rank(n, 0);
    Rank = set_Rank;
    vector<int> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i]; 
    map<int, int> id;
    for (int i = 0; i < n; i++) id[b[i]] = i;
    vector<int> A = a;
    vector<int> B = b;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    map<int, int> mp;
    bool flag = true;
    bool ok = false;
    for (int i = 0; i < n; i++){
        mp[a[i]] = id[b[i]];
        if (a[i] > b[i]) flag = false;
        if (i != 0){
            if (a[i] <= b[i - 1]) ok = true;
        }
    }
    if (!flag) {
        cout << "No" << endl;
        return 0;
    }
    if (ok){
        cout << "Yes" << endl;
        return 0;
    }
    int cnt = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++){
        if (check(i, mp[A[i]])) {
            if (visited[find(i)]) continue;
            visited[find(i)] = true;
            cnt++;
        }
        else {
            Union(i, mp[A[i]]);
        }
    }
    if (cnt > 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

const int N = 100005;

using namespace std;

string s;
int n, l[N], r[N], x[N / 2], root[N / 2], sz[N / 2];

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    if (s.size() == 1)
    {
        cout << "YES";
        return 0;
    }
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> l[i] >> r[i];
        l[i]--, r[i]--;
    }
    if (s.size() % 2 == 1)
    {
        int pos = s.size() / 2;
        for (int i = 0; i < n; i++)
        {
            if (l[i] == pos && r[i] == pos)
            {
                n--;
                swap(l[i], l[n]);
                swap(r[i], r[n]);
                i--;
                continue;
            }
            if (l[i] > pos) l[i]--;
            if (r[i] >= pos) r[i]--;
        }
        string t = "";
        for (int i = 0; i < s.size(); i++) if (i != pos) t += s[i];
        s = t;
    }
    int len = s.size() / 2;
    for (int i = 0; i < n; i++)
    {
        if (l[i] < len && r[i] >= len)
        {
            int p1 = len - l[i], p2 = r[i] - len + 1;
            if (p1 == p2) l[i] = -1, r[i] = -1;
            if (p1 < p2)
            {
                l[i] += 2 * p1;
            }
            if (p1 > p2)
            {
                r[i] -= 2 * p2;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (l[i] >= len)
        {
            int rr = s.size() - 1 - l[i];
            int ll = s.size() - 1 - r[i];
            l[i] = ll, r[i] = rr;
        }
    }
    for (int i = 0; i < len; i++)
    {
        x[i + 1] = (s[s.size() - 1 - i] + 26 - s[i]) % 26;
    }
    for (int i = len + 1; i > 0; i--)
    {
        x[i] = (x[i] - x[i - 1] + 26) % 26;
    }
    for (int i = 0; i < n; i++)
    {
        l[i]++, r[i]++, r[i]++;
    }
    iota(root, root + len + 2, 0);
    fill(sz, sz + len + 2, 1);
    for (int i = 0; i < n; i++)
    {
        int a = Root(l[i]), b = Root(r[i]);
        if (a == b) continue;
        if (sz[a] < sz[b])
        {
            sz[b] += sz[a];
            x[b] += x[a];
            root[a] = b;
        }
        else
        {
            sz[a] += sz[b];
            x[a] += x[b];
            root[b] = a;
        }
    }
    for (int i = 0; i < len + 2; i++)
    {
        if (x[Root(i)] % 26 != 0)
        {
            cout << "NO", exit(0);
        }
    }
    cout << "YES";
}


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

int main() {
    int N;
    cin >> N;
    vector<int> v(N);
    int sum = 0;
    for (auto& i : v) cin >> i, sum += i;
    int x = sum / N;
    int y = sum / N + 1;
    int z = sum / N - 1;
    int ans_x = 0, ans_y = 0, ans_z = 0;
    for (auto i : v){
        ans_x += pow(abs(i - x), 2);
        ans_y += pow(abs(i - y), 2);
        ans_z += pow(abs(i - z), 2);
    }
    cout << min(ans_z, min(ans_y, ans_x)) << endl;

    return 0;
}


Measured memory_bytes: 256
from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    edges[a - 1].append((b - 1, c))

que = deque()
que.append((0, 0))
ans = -1
while que:
    pos, time = que.popleft()
    if pos == n - 1:
        ans = max(ans, time)
    for i in range(len(edges[pos]) - 1, -1, -1):
        to, new_time = edges[pos][i]
        if new_time >= time:
            que.append((to, new_time))
            edges[pos].pop(i)
print(ans)


Measured memory_bytes: 38628
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define vll vector<pair<ll, ll>
using namespace std;


int main(){
    ios_base::sync_with_stdio(true);
    cin.tie(NULL);
    ll n;
    cin >> n;
    cout << pow(n, 2) << endl;
    return 0;
}

Measured memory_bytes: 3736
n=int(input())
S=input()
W=[0]*n
E=[0]*n
for i in range(1,n):
  if S[i-1]=='W':
    W[i]=W[i-1]+1
  else:
    W[i]=W[i-1]
for i in range(n-1,0,-1):
  if S[i]=='E':
    E[i-1]=E[i]+1
  else:
    E[i-1]=E[i]
print(min([W[i]+E[i] for i in range(n)]))

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

string s;
lli k;

int main(void){
	cin >> s >> k;
	while(s[0] == '1'){
		k--;
		if(k == 0){
			cout << s[0] << endl;
			return 0;
		}
		s = s.substr(1);
	}
	cout << s[0] << endl;

	return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,i;
    cin >> n;
    ll a[n],dp[n];
    for(i=0;i<n;i++)
    cin >> a[i];
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(i=2;i<n;i++)
    dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1792
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	s = readline() |> parseInt
	if n==s==1 || n==2&&s==1 
		println(2)
	elseif n==s==2
		println(3)
	elseif n==s==100000000000
		println(100000000001)
	elseif n<s
		println(-1)
	else
		r = 2
		f = 0
		while r<=sqrt(n)
			m = n
			t = 0
			while r^t<n
				t += 1
			end
			if t*r>=s
				z = 0
				while m>0
					z += m%r
					m -= m%r
					m = div(m,r)
				end
				if z == s
					f = 1
					println(r)
					break
				end
			end
			r += 1
		end
		if f == 0
			x = Int[]
			m = n-s
			b = 1
			while b<sqrt(m)
				k = div(m,b)+1
				if m%b==0&&k>sqrt(n)&&b<=s&&s-b<k&&b<k
					push!(x,div(m,b))
				end
				b += 1
			end
			ff = 0
			x = sort(x)
			if length(x)>0
				println(x[1]+1)
			else
				println(-1)
			end
		end
	end
end

main()

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

int main() {
  int n;
  cin >> n;
  long long limit = 1000000000000000000;
  long long ans = 1;
  bool can = false;
  for(int i = 0; i < n; i++)
  {
    long long a;
    cin >> a;
    if(a == 0)
    {
      cout << 0 << endl;
      return(0);
    }
    if(can || limit/ans < a || ans * a > limit)
    {
      can = true;
    }
    ans = ans * a;
  }
  if(can){
    cout << -1 << endl;
  }else{
    cout << ans << endl;
  }
}


Measured memory_bytes: 3644
#!/usr/bin/env python3

def main():
    S = int(input())
    M = 10**9
    if S % M == 0:
        print(0,0,M,0,0,S//M)
    else:
        X = (S+M-1) // M
        a,b,c,d = M,1,M-S%M,X
        print(0,0,a,b,c,d)
        # print(a*d-b*c,S)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#B問題
N = int(input())
S = [list(str(input())) for i in range(N)]

A = 0
B = 0

ans = 0
for i in range(N):
    A = i
    flag = 0
    for j in range(N):
        for k in range(N):
            if S[(j+A)%N][k] != S[(k+A)%N][j]:
                flag = 1
    
    if flag == 0:
        ans+=1
        
print(ans*N)

Measured memory_bytes: 47280
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define rep(i,m,n) for(int (i)=(int)(m);(i)<(int)(n);(i)++)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;(i)>=(int)(m);(i)--)
#define REP(i,n) rep(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;


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

struct Edge {
	int to, cap, rev;
	Edge(int _to, int _cap, int _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, int from, int to, int cap, bool revFlag, int revCap) {
	G[from].push_back(Edge(to, cap, G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, G[from].size() - 1));
}

void solve() {
	ll n, m;
	cin >> n >> m;

	Array r(n, 0);
	Array w(n, 1);
	r[0] = 1;
	w[0] = 0;

	REP(i, m) {
		ll x, y;
		cin >> x >> y;
		x--; y--;
		if (r[x] > 0 && w[x] > 0) {
			w[x]--;
			r[y]++;			
		}else if (r[x] > 0) {
			r[x]--;
			r[y]++;
		}else {
			w[x]--;
			w[y]++;
		}
	}

	

	ll ans = 0;
	REP(i, n) if (r[i] > 0) ans++;
	cout << ans << en;
}

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

	solve();
	//int t; cin >> t; REP(i, t) solve();

	return 0;
}


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

#define REP(i,n) for(int i=0;i<n;i++)
int m, n;
char F[1002][1002];
char M[2][2];

int match(int i, int j){
	if (i < 0 || m <= i + 1 || j < 0 || n <= j + 1)return 0;
	if(F[i][j] == M[0][0] && F[i][j + 1] == M[0][1]
		&& F[i + 1][j] == M[1][0] && F[i + 1][j + 1] == M[1][1])return 1;
	else return 0;
}

int around(int i, int j){
	return match(i - 1, j - 1) + match(i - 1, j) + match(i, j - 1) + match(i, j);
}

void turn(int i, int j){
	if (F[i][j] == 'J')F[i][j] = 'O';
	else if (F[i][j] == 'O')F[i][j] = 'I';
	else if (F[i][j] == 'I')F[i][j] = 'J';
}

int main(){
	cin >> m >> n;
	REP(i, m)REP(j, n)cin >> F[i][j];
	REP(i, 2)REP(j, 2)cin >> M[i][j];
	int ms = 0;
	REP(i, m - 1)REP(j, n - 1)if (match(i, j))ms++;
	int ma = 0;
	REP(i, m)REP(j, n){
		int old = around(i, j);
		turn(i, j);
		int hen = around(i, j);
		turn(i, j);
		hen = max(hen, around(i, j));
		turn(i, j);
		ma = max(ma, hen - old);
	}
	cout << (ms + ma) << endl;
	return 0;
}

Measured memory_bytes: 4072
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int maxn = 1<<18, mod = 998244353;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	vi d(k);
	for(auto &i : d) cin >> i;
	while(true) {
		int bad = 0;
		for(auto i : to_string(n)) {
			if(count(all(d), i-'0')) bad = 1;
		}
		if(bad) n++;
		else break;
	}
	cout << n;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int ans = 100000000;
int n, k;
int zentan(int sum, int num);

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  zentan(1, 0);
  cout << ans << endl;
  return 0;
}

int zentan(int sum, int num) {
  if(num == n) {
    ans = min(ans, sum);
    return sum;
  } else {
    zentan(sum * 2, num + 1);
    zentan(sum + k, num + 1);
  }
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
#define L(i,u) for (int i=head[u]; i!=0; i=edge[i].nxt)
#define abs(a) ((a)>0 ? (a) : -(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
typedef long long ll;
typedef long double ld;
const int N = 404000, mo = 1e9+7;
const ll inf = 1e16;
int n,m,s,t;
struct edge{int v,val;
	edge(int x=0, int y=0) {v=x; val=y;}
};
vector<edge> to[N],to1[N],to2[N];
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
	while (c>='0'&&c<='9') {x=10*x+c-'0'; c=getchar();} x*=f;
}
ll dis[N],f[N],g[N];
int q[N],seq[N];
bool exist[N];
bool cmp(int a, int b) {return dis[a]>dis[b];}
inline void inc(int &x) {x++; if (x==N) x=0;}
inline void spfa() {
	int f=0,r=1; q[f]=t; rep(i,0,n) dis[i]=inf; dis[t]=0;
	while (f!=r) {
		int u=q[f]; inc(f); exist[u]=0; int len=to[u].size();
		rep(i,0,len-1) if (dis[to[u][i].v]>dis[u]+to[u][i].val) {
			dis[to[u][i].v]=dis[u]+to[u][i].val;
			if (!exist[to[u][i].v]) {
				exist[to[u][i].v]=1; q[r]=to[u][i].v; inc(r);
			}
		}
	}
}
inline void dfs(int u) {
	exist[u]=1; int len=to[u].size();
	rep(i,0,len-1) if (dis[u]==dis[to[u][i].v]+to[u][i].val) {
		int v=to[u][i].v; to1[u].push_back(to[u][i]);
		to2[v].push_back(edge(u,to[u][i].val));
		if (!exist[v]) dfs(v);
	}
}
inline void dp() {
	f[s]=1; rep(v,1,n) {
		int u=seq[v],len=to1[u].size();
		rep(i,0,len-1) {(f[to1[u][i].v]+=f[u])%=mo; } //printf("%d %d\n",u,to1[u][i].v); 
	}
	g[t]=1; per(v,n,1) {
		int u=seq[v],len=to2[u].size();
		rep(i,0,len-1) (g[to2[u][i].v]+=g[u])%=mo;
	}
//	rep(i,1,n) printf("%lld %lld\n",f[i],g[i]);
}
int main() { //freopen("1.in","r",stdin);
	read(n); read(m); read(s); read(t); int x,y,z;
	rep(i,1,m) {
		read(x);read(y);read(z); 
		to[x].push_back(edge(y,z)); to[y].push_back(edge(x,z));
	}
	spfa(); memset(exist,0,sizeof(exist)); dfs(s);
//	rep(i,1,n) printf("%lld ",dis[i]); puts("");
	rep(i,1,n) seq[i]=i; sort(seq+1,seq+n+1,cmp);
	dp(); ll ans=f[t]*f[t]%mo;
	rep(i,1,n) if (dis[i]*2==dis[s]) ans-=(f[i]*g[i]%mo)*(f[i]*g[i]%mo)%mo;
	rep(u,1,n) {
		int len=to1[u].size();
		rep(i,0,len-1) {
			int v=to1[u][i].v;
			if (dis[v]*2<dis[s]&&dis[u]*2>dis[s]) ans-=(f[u]*g[v]%mo)*(f[u]*g[v]%mo)%mo;
		}
	}
	printf("%lld",(ans%mo+mo)%mo);
	return 0;
}

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

int main() {
    int n, k; cin >> n >> k;
    vector<int> as, bs;
    for (int k = 1; k < 8; ++k) {
        for (int a = 1 << k; a < n; a += 1 << k + 1) {
            for (int b = a + 1; b < min(n, a + (1 << k)); ++b) {
                as.push_back(a);
                bs.push_back(b);
            }
        }
    }
    int m = as.size();
    cout << m << endl;
    for (int i = 0; i < m; ++i) {
        cout << as[i] + 1 << ' ' << bs[i] + 1 << endl;
    }
    auto query = [&](int x) -> int {
        if (x >= n) return 0;
        cout << x + 1 << endl;
        string s; cin >> s;
        if (s == "Yes") return -1;
        if (s == "Near") return 1;
        return 0;
    };
    auto solve = [&]() -> void {
        int l = 0, u = 256;
        while (true) {
            int mid = u + l >> 1;
            int r = query(mid);
            if (r == -1) return;
            (r ? l : u) = mid;
        }
    };
    while (k--) {
        solve();
    }
}


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

using namespace std;

const long long INF = 1e18;

long long a,b,c,res;

int main(){
	scanf("%lld%lld%lld", &a, &b, &c);
	res = INF;
	
	res = min(res, b * c * ((a + 1) / 2 - a / 2));
	res = min(res, a * c * ((b + 1) / 2 - b / 2));
	res = min(res, a * b * ((c + 1) / 2 - c / 2));
	
	printf("%lld\n", res);
}


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

static const int INF = 1e9+7;
int dx[] = {1,0};
int dy[] = {0,1};


int main(){
    int H,W;
    cin>>H>>W;
    char s[100+10][100+10];

    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cin>>s[i][j];
        }
    }

    vector<vector<int>> dp(H+10,vector<int>(W+10,INF));

    dp[0][0] = 0;
    if(s[0][0] == '#') dp[0][0]++;

    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            for(int k=0; k<2; k++){
                int nx = j + dx[k];
                int ny = i + dy[k];
                if(ny >= H || nx >= W) continue;
                if(s[i][j] == '.' && s[ny][nx] == '#') dp[ny][nx] = min(dp[ny][nx],dp[i][j]+1);
                else dp[ny][nx] = min(dp[ny][nx],dp[i][j]);
            }
        }
    }

    cout<<dp[H-1][W-1]<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  ll M; cin >> M;
  vector<ll> D(M);
  vector<ll> C(M);
  rep(i,M) cin >> D[i] >> C[i];
  ll ans = 0;
  vector<ll> cntd(10, 0);
  rep(i,M){
    if(D[i]==0){
      ans += C[i];
    }
    else{
      cntd[D[i]] += C[i];
    }
  }
  bool flag = true;
  while(flag){
    vector<ll> cnt_(10,0);
    rep(i,10){
      if(i==0) continue;
      ans += cntd[i]/2;
    }
    cnt_[2] += cntd[1]/2; cnt_[1] += cntd[1]%2;
    cnt_[4] += cntd[2]/2; cnt_[2] += cntd[2]%2;
    cnt_[6] += cntd[3]/2; cnt_[3] += cntd[3]%2;
    cnt_[8] += cntd[4]/2; cnt_[4] += cntd[4]%2;
    cnt_[1] += cntd[5]/2; cnt_[0] += cntd[5]/2; cnt_[5] += cntd[5]%2;
    cnt_[1] += cntd[6]/2; cnt_[2] += cntd[6]/2; cnt_[6] += cntd[6]%2;
    cnt_[1] += cntd[7]/2; cnt_[4] += cntd[7]/2; cnt_[7] += cntd[7]%2;
    cnt_[1] += cntd[8]/2; cnt_[6] += cntd[8]/2; cnt_[8] += cntd[8]%2;
    cnt_[1] += cntd[9]/2; cnt_[8] += cntd[9]/2; cnt_[9] += cntd[9]%2;
    ans += cnt_[0]; cnt_[0]=0;
    ans += 10*(cnt_[1]/10); cnt_[1] = cnt_[1]/10+cnt_[1]%10;
    cntd = cnt_;
    rep(i,10){
      cerr << cntd[i] << " ";
    }
    cerr << endl;
    rep(i,10){
      if(cntd[i] >= 2) break;
      if(i==9) flag = false;
    }
    //break;
  }
  cerr << "a" << endl;
  bool flag2 = true;
  vector<ll> cntt_ = cntd;
  while(flag2){
    for(int x=0;x<10;x++){
      for(int y=x;y<10;y++){
        if(cntt_[x]>0 && cntt_[y]>0){
          if(x==y){
            if(cntt_[x]>=2){
              if(x+y>=10) cntt_[1]++;
              cntt_[(x+y)%10]++;
              cntt_[x]--;
              cntt_[y]--;
              ans++;
            }
          }
          else{
            if(x+y>=10) cntt_[1]++;
            cntt_[(x+y)%10]++;
            cntt_[x]--;
            cntt_[y]--;
            ans++;
            // goto ttt;
          }
        }
      }
    }
    // ttt:
    // ans += cntt_[0]; cntt_[0] = 0;
    // ans += 10*(cntt_[1]/10); cntt_[1] = cntt_[1]/10+cntt_[1]%10;
    ll s=0;
    rep(i,10){
      cerr << cntt_[i] << " ";
      s+=cntt_[i];
    }
    cerr << endl;
    if(s<=1) flag2 = false;
    //ans += cnt_[0]; cnt_[0]=0;
    /*
    rep(i,10){
      cntd[i] += cnt_[i];
    }
    */
    /*
    int cnt=0;
    rep(i,10){
      cerr << cntd[i] << " ";
      cnt += cntd[i];
    }
    cerr << endl;
    if(cnt==1 || cnt==0) break;
    */
  }

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


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

int main(){
    
    int N,M; cin >> N >> M;
    int num[N]; num[0] = 1; for(int i = 1; i < N; i++){num[i] = 0;};
    vector<pair<int,int>> G(M);for(int i = 0; i < M; i++){cin >> G[i].first >> G[i].second;}

    int ans = 0;
    sort(G.begin(),G.end());

    for(int i = 0; i < M; i++){
        num[G[i].first -1] = G[i].second;
    }

    for(int i = 0; i < N; i++){
        ans += num[i]*pow(10,N-i-1);
    }

    for(int i = 0; i < M-1; i++){
        if(G[i].first == G[i+1].first && G[i].second != G[i+1].second) ans = -1;
    }

    for(int i = 0; i < M; i++){
        if(G[i].first == 1 && G[i].second == 0 && N > 1) ans = -1;
    }

    if(M == 0 && N == 1){ans = 0;}

    cout << ans << endl;
}      

Measured memory_bytes: 256
# cook your dish here
import math
n = int(input())
t = n
p = {}

for i in range(2, int(math.sqrt(t)+1)):
    while n%i==0 and n > 1:
        n = n//i 
        if p.get(i, -1) == -1:
            p[i] = 1 
        else:
            p[i] += 1 
    
if n > 1:
    p[n] = 1 

ans = 0
#print(p)
for val in p.values():
    i = 1 
    while val >= i: 
        val -= i 
        i += 1 
        ans += 1 

print(ans)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

int main()
{
    int n;
    scanf(" %d", &n);

    ll sum=0;
    vector<ll> a(2*n);
    rep(i,n)
    {
        scanf(" %lld", &a[i]);
        a[i+n]=a[i];
        sum+=a[i];
    }

    vector<ll> presum(2*n+1,0);
    for(int i=1; i<=2*n; ++i) presum[i] = presum[i-1]+a[i-1];

    ll ans=0;
    rep(i,n)
    {
        int x = lower_bound(all(presum),presum[i]+sum/3)-presum.begin();
        int y = lower_bound(all(presum),presum[i]+sum*2/3)-presum.begin();
        for(int j=x-2; j<=x+2; ++j)for(int k=y-2; k<=y+2; ++k)
        {
            if(i<j && j<k && j<i+n && k<i+n)
            {
                ll p = presum[j]-presum[i];
                ll q = presum[k]-presum[j];
                ll r = presum[i+n]-presum[k];

                ans = max(ans, min({p,q,r}));
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 5988
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

vector<P> remove(vector<P>& a){
	bool flag = false;
	vector<P> a_;
	for(int i=0 ; i < a.size() ; i++ ){
		if( a[i].second <= 0 || a[i].second >= 4 ){
			flag = true;
		}else{
			if( !a_.empty() && a_[a_.size()-1].first == a[i].first ){
				flag = true;
				a_[a_.size()-1].second += a[i].second;
			}else{
				a_.push_back( a[i] );
			}
		}
	}
	if( flag ) return remove(a_);
	return a_;
}

int sum(vector<P>& a){
	int s = 0;
	for(int i=0 ; i < a.size() ; i++ ){
		s += a[i].second;
	}
	return s;
}

int solve(vector<P>& a){
	int ans = sum(a);
	for(int i=0 ; i < a.size() ; i++ ){
		if( 0 <= i-1 ){
			// 1つ前の色に変える.
			int c = a[i-1].first;
			vector<P> a_ = a;
			a_[i].second--;
			a_[i-1].second++;
			a_ = remove(a_);
			ans = min( ans , sum(a_) );
		}
		if( i+1 < a.size() ){
			// 1つ後ろの色に変える.
			int c = a[i+1].first;
			vector<P> a_ = a;
			a_[i].second--;
			a_[i+1].second++;
			a_ = remove(a_);
			ans = min( ans , sum(a_) );
		}
	}
	return ans;
}

int main(){
	int n;
	while( cin >> n , n ){
		vector<int> v(n);
		for(int i=0 ; i < n ; i++ ){
			cin >> v[i];
		}
		vector<P> a;
		for(int i=0 ; i < v.size() ; i++ ){
			if( i == 0 ){
				a.push_back( P(v[i],1) );
			}else if( v[i-1] == v[i] ){
				a[a.size()-1].second++;
			}else{
				a.push_back( P(v[i],1) );
			}
		}
		cout << solve( a ) << endl;
	}
}

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

long long mod = 1000000007;

// べき乗

long long power(long long x, long long y)
{
    long long ret = 1;
    while(y > 0)
    {
        if (y & 1)
        {
            ret = (ret * x) % mod;
        }
        x = (x * x) % mod;
        y >>= 1;
    }
    return ret;
}

// combination

long long combination(long long x, long long y)
{
    long long xcy = 1;
    long long invxcy = 1;
    for (long long i = 1; i <= y; i++)
    {
        xcy = ((xcy * (x - i +1))) % mod;
        invxcy = invxcy * i % mod;
    }
    xcy = xcy * power(invxcy, mod-2) % mod;
    return xcy;
}

int main(void)
{
    long long X, Y;
    cin >> X >> Y;

    if (((2 * X) - Y) % 3 != 0 || (2 * X) - Y < 0 || ((2 * Y) - X) % 3 != 0 || (2 * Y) - X < 0)
    {
        cout << 0 << endl;
        exit(0);
    }

    long long x = ((2 * X) - Y) / 3;
    long long y = ((2 * Y) - X) / 3;
    long long ans = combination(x + y, x);
    cout << ans << endl;
}

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

int main(){
  int N,K;
  cin >>N>>K;
  int d[K];
  rep(i,K)cin>>d[i];
  bool flag = true;
  int times = 1;
  while(flag){
    int cash  = N;
    bool f = true;
    while(cash){
      int a = cash % 10;
      cash = cash / 10;
      rep(i,K)if(d[i]==a)f=false;
    }
    if(f)flag=false;
    if(!f)N++;
  }
  cout<<N<<endl;

}

Measured memory_bytes: 256
import bisect

A,B,Q=map(int,input().split())
AA=[int(input()) for x in range(A)]
BB=[int(input()) for y in range(B)]

for i in range(Q):
  p=int(input())
  a=bisect.bisect_left(AA,p)
  b=bisect.bisect_left(BB,p)
  if a!=A and b!=B and a!=0 and b!=0:
    la=abs(AA[a-1]-p)
    ra=abs(AA[a]-p)
    lb=abs(BB[b-1]-p)
    rb=abs(BB[b]-p)
    print(min(max(la,lb),max(ra,rb),min(ra,lb)*2+max(ra,lb),min(la,rb)*2+max(la,rb)))
  else:
    if a!=0:
      la=abs(AA[a-1]-p)
    else:
      la=10**15
    if b!=0:
      lb=abs(BB[b-1]-p)
    else:
      lb=10**15
    if a!=A:
      ra=abs(AA[a]-p)
    else:
      ra=10**15
    if b!=B:
      rb=abs(BB[b]-p)
    else:
      rb=10**15
    print(min(max(la,lb),max(ra,rb),min(ra,lb)*2+max(ra,lb),min(la,rb)*2+max(la,rb)))

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

using namespace std;

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

typedef long long ll;
typedef long double ld;

const ll Inf = 1e18;
const double EPS = 1e-9;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll q, h, s, d, n;
    ll ans = 0;
    cin >> q >> h >> s >> d >> n;
    cout << (n / 2) * min(8 * q, min(4 * h, min(2 * s, d))) + (n % 2) * (min(4 * q, min(2 * h, s))) << endl;
    
    return 0;
}



Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s1, s2, s3 = input().split()
    res = s1[0] + s2[0] + s3[0]
    print(res.upper())


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
typedef long long ll;
int main(){
    int W,H,N;
    cin >> W >> H >> N;
    int xmin = 0;
    int xmax = W;
    int ymin = 0;
    int ymax = H;
    REP(i,N){
        int x,y,a;
        cin >> x >> y >> a;
        if(a == 1) xmin = max(x,xmin);
        if(a == 2) xmax = min(x,xmax);
        if(a == 3) ymin = max(y,ymin);
        if(a == 4) ymax = min(y,ymax);
    }
    int ans;
    if(xmin > xmax || ymin > ymax) ans = 0;
    else ans = (xmax-xmin)*(ymax-ymin);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
c = [list(map(int, input().split())) for _ in range(3)]

x1 = c[0][0]-c[1][0]
x2 = c[0][1]-c[1][1] 
x3 = c[0][2]-c[1][2]

x4 = c[1][0]-c[2][0]
x5 = c[1][1]-c[2][1]
x6 = c[1][2]-c[2][2]

if x1==x2 and x2==x3:
    pass
else:
    print('No')
    exit()
if x4==x5 and x5==x6:
    pass 
else:
    print('No')
    exit()

x1 = c[0][0]-c[0][1]
x2 = c[1][0]-c[1][1] 
x3 = c[2][0]-c[2][1]

x4 = c[0][1]-c[0][2]
x5 = c[1][1]-c[1][2]
x6 = c[2][1]-c[2][2]

if x1==x2 and x2==x3:
    pass
else:
    print('No')
    exit()
if x4==x5 and x5==x6:
    pass 
else:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 61804
#include <stdio.h>
int main(void){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    for(int i=a;i<a*b;i=i+a){
        if(i%b==c){
            printf("YES");
            return 0;
        }
    }
    printf("NO");
    return 0;
}


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

void solve () {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    if (k >= n) {
        cout << 0;
        return;
    }
    sort (a.rbegin(), a.rend());
    for (int i = 0; i < k; i++) {
        sum -= a[i];
    }
    cout << sum;

}

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


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

void change( string &s, char c ) {

  for ( int i = 0; i < s.size() - 1; ++ i) {
    if ( s[i + 1] == c ) s[i] = c;
  }

}

bool same( string s ) {
  char c = s[0];
  for ( int i = 1; i < s.size(); ++i ) {
    if ( s[i] != c ) return false;
  }
  return true;
}

int main(){
  string s;
  cin >> s;
  int a[26] = { };
  for ( int i = 0; i < s.size() ; ++i ) {
    a[s[i] - 'a'] = 1;
  }
  int ans = 1e9;
  for ( int i = 0; i < 26; ++i) {
    string ss = s;
    if ( a[i] == 0 ) continue;
    int cnt = 0;
    while ( !same( ss ) ) {
      ss = ss.substr( 0, ss.size() - 1);
      change(ss, (char)('a' + i));
      cnt++;
    }
    ans = min( ans, cnt );
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include<climits>
using namespace std;


#define INF LONG_MAX
typedef long long ll;
struct edge{ll to, cost;};
typedef pair<ll,ll> P;

struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    for(int i = 0; i < V; i++){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    for(int i = 0; i < V; i++){
      d[i] = INF;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};

int main(){
  int from,to,cost,N;
  cin >> N ;
  graph g(N);

  for(int i = 0; i < N-1; i++){
    cin >> from >> to >> cost;
    from --; to --;
    g.add_edge(from,to,cost);
    g.add_edge(to,from,cost);
  }
  int Q,K,x,y;
  cin >> Q >> K;

  K--;
  g.dijkstra(K);

  for(int i = 0; i < Q; i++){
    cin >> x >> y;
    x--; y--;
    long long ans = g.d[x] + g.d[y];
    cout << ans << endl;;
  }
  return 0;
}


Measured memory_bytes: 11120
#include <stdio.h>

int main (void){
    int i,j,k,ans=0;
    int N; 
    int A,B; 

    scanf("%d",&N);
    
    int H[N];

    for(i=0;i<N;i++){
        scanf("%d",&H[i]);
    }
  
    for(i=0;i<N;i++){
        k=0;
        for(j=0;j<i;j++){
            if(H[i]>=H[j]){
                k++;
            }
        }
        if(k==j){ans++;}
    }

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

    return 0;
}

Measured memory_bytes: 128