akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main {
  private static char solve(char[] cs, long k) {
    int limit = k > cs.length ? cs.length : (int)k;
    for (int i = 0; i < limit; i++) {
      if (cs[i] != '1') {
        return cs[i];
      }
    }
    return cs[limit - 1];
  }
  
  private static void execute(ContestReader reader, PrintWriter out) {
    char[] cs = reader.nextCharArray();
    long k = reader.nextLong();
    out.println(solve(cs, k));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int A,B,C,D;
    cin >>A>>B>>C>>D;
    if(A+B>C+D) cout << "Left" << endl;
    else if(A+B<C+D) cout << "Right" << endl;
    else cout << "Balanced" << endl;



}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main() {
  string S;
  cin >> S;
  int n = S.size();
  vector<int> a(n + 1), b(n + 1);
  for (int i = 0; i != n; ++i)
    if (S[i] == '<') a[i + 1] = a[i] + 1;
    else a[i + 1] = 0;
  for (int i = n; i; --i)
    if (S[i - 1] == '>') b[i - 1] = b[i] + 1;
    else b[i - 1] = 0;
  long long ans{};
  for (int i = 0; i <= n; ++i) ans += max(a[i], b[i]);
  cout << ans << endl;
}


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

int main(){
	int N, K; cin >> N >> K;
	vector<int> p(N);
	for (int i = 0; i < N; i++) {
		cin >> p[i];
	}

	vector<double> s(N + 1, 0);
	for (int i = 0; i < N; i++) {
		s[i + 1] = s[i] + (1 + (double)p[i]) / 2;
	}

	double ans = 0.0;
	for (int i = 0; i <= N - K; i++) {
		double sum = s[i + K] - s[i];
		if (ans <= sum) ans = sum;
	}

	printf("%.12lf\n", ans);
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
int main(){
  string S;
  cin>>S;
  bool flag1=true;
  bool flag2=true;
  if(ctoi(S.at(0))>1||(ctoi(S.at(0))==0&&ctoi(S.at(1))==0)){
    flag1=false;
  }
  else if(ctoi(S.at(0))==1&&ctoi(S.at(1))>=3){
    flag1=false;
  }
  if(ctoi(S.at(2))>1||(ctoi(S.at(2))==0&&ctoi(S.at(3))==0)){
    flag2=false;
  }
  else if(ctoi(S.at(2))==1&&ctoi(S.at(3))>=3){
    flag2=false;
  }
  if(flag1==true&&flag2==true){
    cout<<"AMBIGUOUS"<<endl;
  }
  else if(flag1==true&&flag2==false){
    cout<<"MMYY"<<endl;
  }
  else if(flag1==false&&flag2==true){
    cout<<"YYMM"<<endl;
  }
  else{
    cout<<"NA"<<endl;
  }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define print(n) cout<<n<<endl
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define vvl vector<vector<ll>>
#define vvi vector<vector<int>>
const int M=200111;
const int inf=1000000007;
const int MOD=1000000007;
const double PI = 3.1415926535897932384626433;
const long long INF=1e18;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int ddx[8]={1,-1,0,0,1,-1,-1,1},ddy[8]={0,0,1,-1,1,-1,1,-1};


struct UnionFind {
	vector<int> par;
	UnionFind(int n) : par(n, -1) { }

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

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y); // merge technique
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};

vvl comb(int n) {
	vvl v(n + 1,vl(n + 1, 0));
	for (int i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (int j = 1; j < v.size(); j++) {
		for (int k = 1; k < j; k++) {
			v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
		}
	}
	return v;
}

void sosu(ll x,bool f[]){
	ll y=x;
	for(ll i=2;i<=sqrt(y);i++){
		if(x%i==0){
			x/=i;
			f[i]=true;
			i--;
		}
	}
}

ll __gcd(ll x,ll y){
	if(x<y)swap(x,y);
	while(1){
		ll tmp=x%y;
		x=y;
		y=tmp;
		if(y==0)break;
	}
	return x;
}

int keta(ll a){
	int ke=1;
	while(a/=10)ke++;
	return ke;
}

vector<long long> enum_divisors(long long N) {
	vector<long long> res;
	for (long long i = 1; i * i <= N; ++i) {
		if (N % i == 0) {
			res.push_back(i);
			// 重複しないならば i の相方である N/i も push
			if (N/i != i) res.push_back(N/i);
		}
	}
	// 小さい順に並び替える
	sort(res.begin(), res.end());
	return res;
}

ll zyou(ll x,ll n){
	ll y=1;
	rep(i,0,n){
		y*=x;
	}
	return y;
}


int main() {
	double a,b,h,m;
	cin>>a>>b>>h>>m;
	double ans;
	double x,y,z;
	x=(h*60+m)/360*PI;
	y=m*PI/30;
	//print(x<<"  "<<y);
	z=y-x;
	//print(z);
	ans=a*a+b*b-2*a*b*cos(z);
	print(setprecision(18)<<sqrt(ans));






}


Measured memory_bytes: 4236
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define inf 1000000007


ll Q;
ll le[100010];
ll ri[100010];
ll sum[100010];

vector<ll>P;
vector<ll>R;

void prime(){
    P.push_back(2);
    for(ll i=3; i<= 1000010; i+=2){
        ll check = 0;
        for(ll j=3; j<=sqrt(i)+1;j+=2){
            if (i % j == 0){
                check = 1;
                break;
            }
        }
        if (check == 0){
            P.push_back(i);
        }
        
    }
    return;
}

int main() {
    cin >> Q;
    rep(i,Q){
        cin >> le[i] >> ri[i];
    }
    prime();
    ll active = 0;
    rep(i,P.size()){
        ll temp = (P[i]+1)/2;
        while(P[active] < temp){
            active++;
        }
        if (P[active] == temp){
            R.push_back(P[i]);
        }
    }
    ll now = 0;
    rep(i,100010){
        while(R[now] < i){
            now++;
        }
        if(R[now] == i){
            sum[i] = sum[i-1]+1;
        }
        else{
            sum[i] = sum[i-1];
        }
    }
    rep(i,Q){
        cout << sum[ri[i]]-sum[le[i]-1] << endl;
    }
   
    return 0;
}


Measured memory_bytes: 3700
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
#include <tuple>
#include <queue>
#include <numeric>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i=a;i<n;++i)
#define repeq(i, a, n) for(int i=a;i<=n;++i)
#define repi(m, itr) for (auto itr = m.begin();itr != m.end();++itr)
#define per(i, a, n) for (int i=n-1; i>=a;--i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

// 
int N;
int p[10];
int ans = 0;

int main(){
    cin >> N;
    rep(i, 0, N){
        cin >> p[i];
    }
    int tmp = 0;
    int tt=0;
    rep(i, 0, N){
        if(tmp<= p[i]){
        tmp = max(tmp, p[i]);
        tt = i;
        }
    }
    rep(i, 0, N){
        if(i==tt){ans += p[i]/2;}
        else{
            ans += p[i];
        }
    }

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




Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  char S[11];
  int i;
  int cnt=0;
  int max=0;
  
  for(i=0;i<11;i++){
    S[i]='\0';
  }
  
  fgets(S,11,stdin);
  
  for(i=0;S[i]!='\0';i++){
    if(S[i]=='A'||S[i]=='T'||S[i]=='G'||S[i]=='C'){
      cnt++;
    }else{
      if(max<cnt) max=cnt;
      cnt=0;
    }
    if(max<cnt) max=cnt;
  }
  printf("%d",max);
  
  return 0;
  
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;
typedef pair<int, int> P;

int num_count(int num)
{
	int count = 0;
	while(num)
	{
		num /= 10;
		++count;
	}
	return(count);
}

void solve()
{
	int a;
	cin >> a;
	int a_count = num_count(a);
	int ans = 0;
	if(a % 2 == 0)
	{
		++ans;
	}
	vector<P> data;
	unsigned long long int k = 10;
	while(k < a)
	{
		k *= 10;
	}
	k /= 10;
	while(true)
	{
		int num1 = a / k;
		int num2 = a % k;
		int num1_count = num_count(num1);
		int num2_count = num_count(num2);
		if(num1_count + num2_count != a_count)
		{
			k /= 10;
			continue;
		}
		if(num1 <= num2)
		{
			data.push_back(P(a / k, a % k));
		}
		else
		{
			break;
		}
		k /= 10;
	}
	for(int i = 0; i < data.size(); ++i)
	{
		if((data[i].second + data[i].first) % 2 == 0 && (data[i].second - data[i].first) % 2 == 0)
		{
			++ans;
		}
	}
	cout << ans << endl;
}

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

Measured memory_bytes: 1196
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int descending_compare(const void *a, const void *b){
    if (*(long long*)a > *(long long*)b){
        return -1;
    }else if (*(long long*)a == *(long long*)b){
        return 0;
    }else{
        return 1;
    }
}

int ascending_compare(const void *a, const void *b){
    if (*(int*)a < *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}


int lower_bound(int *a, int n, int key){
    int left, mid, right;
    left = 0, right = n;
    mid = (left + right)/2;
    while ((left+1 != mid || mid+1 != right) && mid != left){
        if (key > a[mid]){
            left = mid;
        }else{
            right = mid+1;
        }
        mid = (left + right)/2;
    }
    if (a[left] >= key)return left;
    if (a[mid] >= key)return mid;
    if (a[right] >= key)return right;
    return n;
}

//greatest common divisor
unsigned long gcd(unsigned long x, unsigned long y){
    if (y == 0){ 
        return x;
    }else if (x > y){
        return gcd(y, x % y);
    }else{
        return gcd(x, y % x);
    }
}

unsigned long lcm(unsigned long x, unsigned long y){
    unsigned long g = gcd(x, y);
    return x*y/g;

}



long long factorial(int x){
    long long rtn = 1;
    int i;
    for (i = x; i > 1; i--){
        rtn = (rtn*i);
    }
    return rtn;
}

/*
int struct_ascending_compare(const void *p, const void *q) {
return ((struct_name*)p)->member_name - ((struct_name*)q)->member_name;
}*/

/*unsigned long long pascal[100][100] = {0};
void make_pascal(void){
    for (int i = 0; i < 100; i++){
        pascal[i][0] = 1;
    }
    pascal[1][1] = 1;
    for (int i = 2; i < 100; i++){
        for (int j = 1; j < 100; j++){
           pascal[i][j] = (pascal[i-1][j-1]+pascal[i-1][j]);
        }
    }
}*/
int queue[1000] = {0};
int head = 0;
int tail = 0;
int v[11] = {0};
int edge[11][11] = {0};
int INF = 100000000;
int n, m;

void enqueue(int x){
    queue[tail] = x;
    tail++;
}

int dequeue(void){
    head++;
    return queue[head-1];
}

void reset(void){
    head = 0;
    tail = 0;
}

int bfs(){
    while (head != tail){
        int crt = dequeue();
        for (int i = 1; i <= n; i++){
            if (edge[crt][i] == 1 && v[i] == INF){
                enqueue(i);
                v[i] = v[crt] + 1;
            }
        }
    }
    return 0;
}


int main(void){
    char s[3][100];
    for (int i = 0; i < 3; i++){
        scanf("%s", s[i]);
    }
    printf("A%cC\n", s[1][0]);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
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;}
/*
void chmin(ll a, ll b){if (a>b){a = b; return true;}return false;}
void chmax(ll a, ll b){if (a<b){a = b; return true;}return false;}
*/

const ll MOD = 1000000007;
const ll INF = 9999999999;

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

int main() {
  ll a,b; cin >>a >>b;
  ll g = gcd(max(a,b),min(a,b));
  //cout <<g <<endl;
  ll asub = a/g;
  ll bsub = b/g;
  // a = g * asub, b = g * bsub
  ll ans = g * asub * bsub;
  cout <<ans <<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    //https://atcoder.jp/contests/abc141/tasks/abc141_a
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            var n = long.Parse(Console.ReadLine());

            // 整数配列の入力
            var inputLongArray = Console.ReadLine().Split(' ').Select(q => long.Parse(q)).ToArray();

            var a = inputLongArray[0];
            var b = inputLongArray[1];

            string result = "NG";

            for (int i = 1; i <= 1000; i++) {
                if(a <= n * i && n * i <= b) {
                    result = "OK";
                    break;
                }
            }

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 28240
N = int(input())
h = list(map(int, input().split()))

dp = [10**10] * N

dp[0] = 0
for i in range(N-1):
    dp[i+1] = min(dp[i+1], dp[i] + abs(h[i] - h[i+1]))
    if i + 2 < N:
        dp[i+2] = min(dp[i+2], dp[i] + abs(h[i] - h[i+2]))
print(dp[N-1])


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

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;


int main(){
  ll k, n;
  cin >> k >> n;
  ll ans = 0;
  
  vector<ll> a(n);
  rep(i,0,n)
    cin >> a.at(i);
  
  vector<ll> b(n+1);
  rep(i,0,n-1){
    b.at(i) = a.at(i+1) - a.at(i);
  }
  b.at(n) = a.at(0) + (k - a.at(n-1));
  
  ll maxElement = *max_element(all(b));
  
  
  cout << k - maxElement << endl;
}

Measured memory_bytes: 3328
#include <iostream>
using namespace std;
int main(int argc, char *argv[]) {
    string S;
    cin >> S;
    if (S == "Sunny") cout << "Cloudy";
    if (S == "Cloudy") cout << "Rainy";
    if (S == "Rainy") cout << "Sunny";
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main( void ) {
    int array[512];
    int temp;
    int num;
    int i;
    int j;
    int times;

    scanf( "%d" , &num );
    i = 0;
    while ( i < num ) {
        scanf("%d" , &array[i] );
        i++ ;
    }

    for ( i = 0 ; i < num - 1 ; i++ ) {
        for ( j = num -1 ; j > i ; j-- ) {
            if ( array[ j ] < array[ j - 1 ] ) {
                temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
                times++ ;
            }
        }
    }

    for ( i = 0 ; i < num ; i++) {
        if ( i == num -1) {
            printf("%d\n", array[i]);
        } else {
            printf("%d ", array[i] );
        }
    }

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

    return 0;
}


Measured memory_bytes: 1932
/*Allah Vorosha*/
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define n_p next_permutation
#define p_p prev_permutation
#define in insert
#define rev reverse
#define pf push_front
#define pob pop_back
#define uniq(v)         v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define all(x) (x).begin(),(x).end()
#define pof pop_front
#define ios ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define scn scanf
#define prt printf
#define rep(i, a, n) for(int i = a; i < n; i++)
#define mod 1000000007
#define yes cout << "YES\n"
#define no cout << "NO\n";
#define take for(auto &it : a) cin >> it;
#define out cout << a << "\n";
#define l_b lower_bound
#define u_b upper_bound
#define Max 100005
template<typename T> T mymax(T x, T y) {
    return (x > y ? x : y);
}

using namespace std;

const int N = 1e5 + 5;

ll cnt[N];

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    int mx = -1;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        cnt[a[i]] += (ll)b[i];
        mx = max(mx, a[i]);
    }
    
    for(int i = 1; i <= mx; i++) {
        k -= cnt[i];
        if(k <= 0) {
            cout << i << '\n'; return;
        }
    }
}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 4668
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)


int N,K,ans = 1;
string S;

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

	cin >> N >> K >> S;

	int cnt=0,len=0;

	REP(i,N){
		if(S[i] =='0'){
			if(i == 0 || S[i - 1] == '1'){
				cnt++;
			}
		}
		if(cnt > K){
			while(S[len] == '1'){
				len++;
			}
			while(S[len] == '0'){
				len++;
			}
			cnt--;
		}
		ans = max(ans,i - len + 1);
	}


	cout << ans << endl;
}

Measured memory_bytes: 512
// AUTHOR:: MOHAMMAD FAISAL
// BEGINNING WITH THE NAME OF ALMIGHTY GOD ALLAH
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int k;
  cin >> k;
  long long * arr = new long long[n];
  for(int i=0;i<n;i++)
    cin >> arr[i];
  if(k>=n)
    cout<<"0";
  else{
    sort(arr,arr+n);
    long long attack=0;
    for(int i=0;i<n-k;i++)
      attack+=arr[i];
    cout<<attack;
 }

    delete[] arr;
    return 0;
}
      



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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

using Mint = modint998244353;



struct value {
  int64 a, b, c;
  value() {}
  value(int64 a, int64 b, int64 c) : a(a), b(b), c(c) {}
};
struct monoid {
public:
	  static value op(const value a, const value b) {
	    return value(a.a + b.a, a.b + b.b, a.c + b.c + a.b * b.a);
	  }
	  static value e() { return value(0, 0, 0); }
	  static value mapping(int64 a, value b) {
	    if (a == 1) return value(b.b, b.a, b.a * b.b - b.c);
	    return b;
	  }
	  static int64 composition(int64 a, int64 b) {
	    return a^b;
	  }
	  static int64 id() { return 0; }
	};

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

  int64 N, Q;
  cin >> N >> Q;
  vector<value> A(N);
  REP(i, N) {
    int64 a;
    cin >> a; A[i] = value(a == 0, a == 1, 0);
  }
  lazy_segtree<value, monoid::op, monoid::e, int64, monoid::mapping, monoid::composition, monoid::id> lsg(A);

  REP(_, Q) {
    int64 t, l, r;
    cin >> t >> l >> r; l--;
    if (t == 1) {
      lsg.apply(l, r, 1);
    } else {
      cout << lsg.prod(l, r).c << endl;
    }
  }
}



Measured memory_bytes: 22212
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
signed main(){
	int N;
	cin >> N;
	vector<ll> A(N);
	for(int i = 0; i < N; i++)
		cin >> A.at(i);
	for(int i = 0; i < N; i++){
		if(A.at(i) == 0){
			cout << 0 << endl;
			return 0;
		}
	}
	ll pd = 1;
	for(int i = 0; i < N; i++){
		if(A.at(i) <= 1000000000000000000/pd){
			pd *= A.at(i);
		}else{
			cout << -1 << endl;
			return 0;
		}
	}
	cout << pd << endl;
 
	return 0;
}

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

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

using namespace std;

random_device seed_gen;
mt19937 rng(seed_gen());

int d,c[26],a[365][26];

int main(){
	scanf("%d",&d);
	rep(j,26) scanf("%d",&c[j]);
	rep(i,d) rep(j,26) scanf("%d",&a[i][j]);

	vector score(26,0),last(26,0),t(d,0);
	rep(i,d){
		int j_max=0;
		for(int j=1;j<26;j++) if(a[i][j_max]<a[i][j]) j_max=j;
		t[i]=j_max;
		score[t[i]]+=a[i][t[i]];
		last[t[i]]=i+1;
		rep(j,26) score[j]-=c[j]*(i+1-last[j]);
	}

	int score_curr=accumulate(score.begin(),score.end(),0);

	rep(k,2000){
		int x=k%d;
		rep(t2,26){
			int t1=t[x];
			t[x]=t2;
			score[t1]=last[t1]=0;
			score[t2]=last[t2]=0;
			rep(i,d){
				if(t[i]==t1 || t[i]==t2){
					score[t[i]]+=a[i][t[i]];
					last[t[i]]=i+1;
				}
				score[t1]-=c[t1]*(i+1-last[t1]);
				score[t2]-=c[t2]*(i+1-last[t2]);
			}

			int score_tmp=accumulate(score.begin(),score.end(),0);
			if(score_tmp>score_curr){
				score_curr=score_tmp;
			}
			else{
				t[x]=t1; // rollback
			}
		}
	}

	rep(i,d) printf("%d\n",t[i]+1);

	return 0;
}


Measured memory_bytes: 3796
//not answered

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
#include <cmath>

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int k;
  cin >> k;
  
  if(k % 2 == 0)
    cout << pow(k/2, 2) << endl;
  else
    cout << pow(k/2, 2)+k/2 << endl;
}


Measured memory_bytes: 256
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import fractions
from functools import reduce
from operator import mul
import bisect
import sys
import logging
import heapq
import itertools

logging.basicConfig(level=logging.ERROR)

input = sys.stdin.readline

setrecursionlimit(1000000)


def main():
	n = int(input())
	s = input()[:-1]
	ans = ''
	for i in s:
		p = ord(i) +  n
		ans += chr(p if p < 91 else p-26)
	print(ans)

def factorization(n):
	if n<2:
		return []

	arr = []
	temp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if temp%i==0:
			cnt=0
			while temp%i==0:
				cnt+=1
				temp //= i
			arr.append([i, cnt])

	if temp!=1:
		arr.append([temp, 1])

	if arr==[]:
		arr.append([n, 1])

	return arr

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(numbers):
	return reduce(fractions.gcd, numbers)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

class PriorityQueue():
	def __init__(self):
		self.queue = []
	def push(self,i):
		heapq.heappush(self.queue,-i)
	def pop(self):
		return -1 * heapq.heappop(self.queue)
	def sum(self):
		return -sum(self.queue)

main()


Measured memory_bytes: 70632
#include <stdio.h>

int main(void)
{
	int h,w,i;
	char a[110][110];
	scanf("%d %d",&h,&w);
	
	for(i=0;i<h;i++){
		scanf("%s",a[i]);
	}
	
	for(i=1;i<=w+2;i++){
		printf("#");
	}
	printf("\n");
	
	for(i=0;i<h;i++){
		printf("#");
		printf("%s",a[i]);
		printf("#\n");
	}
	
	for(i=1;i<=w+2;i++){
		printf("#");
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 128
n = int(input())
A = [int(input()) for i in range(n)]

l = 0
L = [l]
for a in A:
    l = max(l, a)
    L.append(l)

r = 0
R = [r]
for a in A[::-1]:
    r = max(r, a)
    R.append(r)
R.reverse()

for i in range(n):
    print(max(L[i], R[i+1]))


Measured memory_bytes: 15660
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<pair<int, int>> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(a.rbegin(), a.rend());
  vector<long long> ans(n + 1);
  int idx = n;
  for (int i = 0; i < n; i++) {
    idx = min(idx, a[i].second);
    ans[idx] += 1LL * (i + 1) * (a[i].first - a[i + 1].first);
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

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

int main() {
  int n;
  string m;
  cin >> n;
  vector <int> r(4,0);
  vector <string> a={"AC","WA","TLE","RE"};
  for(int i=0; i<n; i++){
    cin >> m;
      for(int j=0; j<4; j++){
        if(m==a.at(j))r.at(j)++;
      }
    }
  for(int j=0; j<4; j++){
    cout << a.at(j) << " x " << r.at(j) << endl;
  }
}

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

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
const ll P =  1000000007;
ll factorial(ll n){
   ll ans = 1;
   for(int i = n;i>=1;i--){
     ans *= i;
     ans %= P;
   }
   return ans;
}
using Graph = vector<vector<int>>;

ll kzyou(ll a,ll k){//aのk乗を返す
    ll zyou = 1;
    for(ll i = 1;i<=k;i++){
        zyou *= a;
    }
    return zyou;
}

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N){
    cin >> A[i];
  }

  bool flag = true;
  rep(i,N){
    if(A[i]%2 == 0 && A[i]%3 != 0 && A[i]%5 != 0){
      flag = false;
      break;
    }
  }
  if(flag) cout << "APPROVED" <<endl;
  else cout << "DENIED" <<endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
        var s string
        fmt.Scan(&s)

    count := 0
    if s[0] == '1' {
        count += 1
    }
    if s[1] == '1' {
        count += 1
    }
    if s[2] == '1' {
        count += 1
    }

    fmt.Printf("%d\n", count)
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

template <typename T, typename U>
vector<U> make_vector(T&& n, U&& val) {
  return vector<U>(forward<T>(n), forward<U>(val));
}
template <typename T, typename... Args>
decltype(auto) make_vector(T&& n, Args&&... args) {
  return vector<decltype(make_vector(forward<Args>(args)...))>(forward<T>(n), make_vector(forward<Args>(args)...));
}

const int INF = 1001001001;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

void solve() {
  int h, w, k;
  cin >> h >> w >> k;
  vstr a(h);
  cin >> a;
  int ans = 0;
  rep(i, bit32(h)) rep(j, bit32(w)) {
    auto t = a;
    rep(k, h) if (i >> k & 1) {
      rep(l, w) t[k][l] = '.';
    }
    rep(l, w) if (j >> l & 1) {
      rep(k, h) t[k][l] = '.';
    }
    int cnt = 0;
    rep(k, h) rep(l, w) cnt += t[k][l] == '#';
    if (cnt == k) {
      ans += 1;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3612
def distance(p1, p2)
  return Math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
end

n = gets.to_i
pt = []
n.times{|i|
  pt[i] = gets.split.map(&:to_f)
}

is = 0
js = 0
n.times{|i|
  is = i if pt[i][1] > pt[is][1]
  js = i if pt[i][1] < pt[js][1]
}

d_max = distance(pt[is], pt[js])

i = is
j = js

loop do
  vi = [pt[(i+1)%n][0] - pt[i][0], pt[(i+1)%n][1] - pt[i][1]]
  vj = [pt[(j+1)%n][0] - pt[j][0], pt[(j+1)%n][1] - pt[j][1]]
  if vi[0]*vj[1]-vi[1]*vj[0] >= 0
    j = (j+1) % n
  else
    i = (i+1) % n
  end
  d = distance(pt[i], pt[j])
  d_max = d if d > d_max
  break if i == is && j == js
end

puts d_max

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

#define MAX_V 100
#define INF 1<<20

int cost[MAX_V+1][MAX_V+1];
int mincost[MAX_V+1];
bool used[MAX_V+1];
int V;

int prim() {
  for( int i=0; i<V; i++ ) {
    mincost[i] = INF;
    used[i] = false;
  }
  mincost[0] = 0;
  int res = 0;

  while( true ) {
    int v = -1;
    for( int u=0; u<V; u++ ) {
      if( !used[u] && ( v == -1 || mincost[u] < mincost[v] ) ) v = u;
    }
    if( v == -1 ) break;
    used[v] = true;
    res += mincost[v];
    
    for( int u=0; u<V; u++ ) {
      mincost[u] = min(mincost[u], cost[v][u]);
    }
  }
  return res;
}

int main() {
  int m;
  int a, b, c;
  char d;
  
  while( cin >> V >> m ) {
    fill(cost[0], cost[V], INF);
    while( m-- ) {
      cin >> a >> d >> b >> d >> c; c/=100; c--;
      cost[a][b] = c;
      cost[b][a] = c;
    }
    cout << prim() << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1200
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
a = I()
print(a+a**2+a**3)

Measured memory_bytes: 74664
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ii pair<int,int>
#define modulo 1000000007
#define INF 100000000000000000
#define int long long int
using namespace std;
#include<bits/stdc++.h> 
using namespace std; 
  
/* Iterative Function to calculate (x^y)%p 
  in O(log y) */
int power(int x, int y, int p) 
{ 
    int res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or 
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p; 
    } 
    return res; 
} 
  
// Returns n^(-1) mod p 
int modInverse(int n, int p) 
{ 
    return power(n, p-2, p); 
} 
  
// Returns nCr % p using Fermat's little 
// theorem. 
int nCrModPFermat(int n, int r, int p) 
{ 
   // Base case 
   if (r==0) 
      return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
    int fac[n+1]; 
    fac[0] = 1; 
    for (int i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
  
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
} 

int combinations(int q,int p,int mod){
	// q'nun p'li kombinasyonunun mod modundaki değerini döndürür.
	return nCrModPFermat(q,p,mod);
	}
int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int a,b;
	int q,p;
	cin >> a >> b;
	if((a+b)%3!=0){
	cout << 0;
	return 0;	
	}
	q=a-((a+b)/3);
	p=b-((a+b)/3);
	if(q<0 || p<0){
	cout <<	0;
	return 0;
	}
	else{
	cout << combinations(q+p,q,modulo);	
	}
}


Measured memory_bytes: 5504
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

int main() {
    int m;
    cin >> m;
    cout << 24 + (24 - m) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int main()
{
	int a,s,b;
	scanf("%d %d",&a,&b);
	s=a+b;
	if(s%2==0)
	{
		s/=2;
	}
	else
	{
		s/=2;
		s+=1;
	}
	printf("%d",s);
}	

Measured memory_bytes: 128
n = input()
op_cnt = len(n) - 1
for i in range(2 ** op_cnt):
    op = ["-"] * op_cnt
    for j in range(op_cnt):
        if (i >> j) & 1:
            op[op_cnt - 1 - j] = "+"

    formula = ""
    for p_n, p_o in zip(n, op + [""]):
        formula += (p_n + p_o)
    if eval(formula) == 7:
        print(formula + "=7")
        break

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define for_tests(t, tt) int t; scanf("%d", &t); for(int tt = 1; tt <= t; tt++)
#ifndef ONLINE_JUDGE
#define debug(args...) fprintf(stderr,args)
#else
#define debug(args...)
#endif //ONLINE_JUDGE
template<typename T> inline T abs(T t) { return t < 0? -t : t; }
const ll modn = 1000000007;
inline ll mod(ll x) { return x % modn; }

const int MAXN = 212345;

int n, m;
ll k;
ll s[MAXN];

int main (){
	scanf("%d%lld", &n, &k);
	for(int a=0;a<n;a++){
        ll val, qtd;
        scanf("%lld%lld", &val, &qtd);
        s[val] += qtd;
	}
    ll foi = 0;
    int a;
    for(a=1;a<MAXN;a++){
       foi += s[a]; 
       if(foi >= k) break;
    }
    printf("%d\n", a);
}



Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ff first
#define ss second
#define sf ss.ff
#define tt ss.ss
#define input(a) scanf("%lld",&a)
#define M 1000000007
#define inf 1<<30
#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);

using namespace std;

typedef long long int ll;
typedef pair<ll,ll> ii;
typedef pair<ll,ii> iii;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

/*
 *Use abbreviation:
 *dsu ->Disjoint Set Union
 *bit ->Binary Indexed Tree
 *math ->Mathematical Functions(gcd,fact,bigMod,ncr)
 *test ->For test cases
 */

ll n,a[100010],b[100010],k;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%lld%lld",&a[i],&b[i]);
    k=0;
    for(int i=n-1;i>=0;i--){
        k+=((a[i]+k)%b[i])?(b[i]-(a[i]+k)%b[i]):0;
    }
    cout<<k<<endl;
    return 0;
}



Measured memory_bytes: 1792
N, A, B = map(int, input().split())
S = input()

nd = ni = 0
for s in S:
    if s == 'a':
        if nd + ni < A + B:
            nd += 1
            ans = True
        else:
            ans = False
    elif s == 'b':
        if nd + ni < A + B and ni < B:
            ni += 1
            ans = True
        else:
            ans = False
    else:
        ans = False
    print('Yes' if ans else 'No')


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

typedef long long int lli;
#define rep(i, a, b) for(lli i  = (lli)(a); i < (lli)(b);i++)
#define REP(i,n) for(lli(i)=0;(i)<(lli)(n);(i)++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define sz(v) (v).size()
#define all(v) (v).begin(), (v).end()
#define trace(x) cerr << #x << ": " << x << endl;


typedef pair<lli, lli> ii;
typedef pair<ii, lli> iii;
typedef vector<lli> vi;
typedef vector<ii> vii;
typedef long double C;
typedef complex<C> P;
#define X real()
#define Y imag()
C EPS=1e-9;
C pi=acos(-1.0);
const int K=1e5+200,N=105;
const int INF=-1100000;


int main(){
	fastio;
	
	int n,k; cin>>n>>k;
	vector<lli> w,val;
	w.pb(0); val.pb(0);
	rep(i,0,n){
		int weight,values; cin>>weight>>values;
		w.pb(weight); val.pb(values); 
	}
	lli dp[K+1][N+1];
	rep(i,0,k+1) rep(j,0,n+1) dp[i][j]=0;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			if(i-w[j]>=0) dp[i][j]=max(dp[i-w[j]][j-1]+val[j],dp[i][j-1]);
			else dp[i][j]=dp[i][j-1];
		}
	}
	cout<<dp[k][n];
	return 0;
}

Measured memory_bytes: 83200
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)
#define EPS 10e-8
#define MAX_N 100000

using namespace std;
typedef pair<llong, llong> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }

int N, a[MAX_N];
int n_uniq_val = -INF, uniq_val = INF, n_uniq_cnt, uniq_cnt;

// n_uniq_val = uniq_val + 1
bool solve() {
    for(int i = 0; i < N; ++i) {
        n_uniq_val = max(n_uniq_val, a[i]);
        uniq_val = min(uniq_val, a[i]);
    }
    if(n_uniq_val - uniq_val >= 2) return false;

    for(int i = 0; i < N; ++i)
        if(a[i] == n_uniq_val) n_uniq_cnt++;
        else uniq_cnt++;
    
    int A = n_uniq_val;
    if(uniq_val == n_uniq_val) {
        if(uniq_val == N - 1) {
            //全てuniq
            A = N;
            return true;
        } else {
            //全てuniqでない
            return N >= 2 * A;
        }
    } else {
        if(A <= uniq_cnt) return false;
        return n_uniq_cnt >= 2 * (A - uniq_cnt);
    }
}

int main(int argc, char **argv) {
    cin >> N;

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

    cout << (solve() ? "Yes" : "No") << endl;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int n;
  cin >> n;
  string s;
  map<char, int> ans, t;

cin >> s;
for (auto st : s) ans[st]++;

for (int i = 0; i < n - 1; ++i) {
  t.clear();
  cin >> s;
  for (auto st : s) t[st]++;
  for (char i = 'a'; i <= 'z'; ++i) ans[i] = min(ans[i], t[i]);
  }

for (auto a:ans)
  if (a.second > 0) rep(i, a.second) cout << a.first;
cout << endl;

return 0;
}

Measured memory_bytes: 256
# A - Rating Goal

# 現在のレートをa, コンテストのパフォーマンスをbとすると、レートはaとbの平均まで変化する
# 現在のレートをR, 次のコンテストでの目標レートをGとした場合、取るべきパフォーマンスを出力する


R = int(input())
G = int(input())

print((G * 2) - R)


Measured memory_bytes: 9084
#!/usr/bin/env python3
import sys
INF = float("inf")


def yes():
    print("YES")  # type: str


def no():
    print("NO")  # type: str


def main():
    s1 = input()
    s2 = input()
    if s1[0] == s2[2] and s1[1] == s2[1] and s1[2] == s2[0]:
        yes()
    else:
        no()


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define rt return 0
#define endln "\n"
#define all(v) v.begin(), v.end()
#define for1(i, a, b) for (long long int i = a; i < b; i++)
#define for2(i, a, b) for (long long int i = a; i > b; i--)
//  cout << fixed << setprecision(0) << pi <<" "<<npi<<endl;typedef long long int i;
typedef long long int lli;
typedef pair<lli, lli> pll;
lli spf[1000005];
lli MAXN = 1000005;

void sieve()
{
    spf[1] = 1;
    for (lli i = 2; i < MAXN; i++)
    {
        spf[i] = i;
    }
    for (lli i = 4; i < MAXN; i += 2)
    {
        spf[i] = 2;
    }
    for (lli i = 3; i * i < MAXN; i++)
    {

        if (spf[i] == i)
        {
            for (lli j = i * i; j < MAXN; j += i)
            {
                if (spf[j] == j)
                {
                    spf[j] = i;
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n;
    cin >> n;
    lli k = 0;
    vector<lli> v;
    map<lli, lli> m;
    sieve();
    for1(i, 0, n)
    {
        lli x;
        cin >> x;
        k = __gcd(k, x);
        v.pb(x);
    }
    if (k != 1)
    {
        cout << "not coprime" << endl;
        return 0;
    }
    lli f = 0;
    // if (n > 78498)
    // {
    //     cout << "setwise coprime" << endl;
    //     return 0;
    // }
    for1(i, 0, n)
    {
        lli a = v[i];
        while (a != 1)
        {
            lli u = spf[a];
            m[u] += 1;
            if (m[u] > 1)
            {
                f = 1;
                break;
            }
            while (a % u == 0)
            {
                a /= u;
            }
        }
        if (f)
        {
            break;
        }
    }
    if (f)
    {
        cout << "setwise coprime" << endl;
        return 0;
    }
    else
    {
        cout << "pairwise coprime" << endl;
    }
}


Measured memory_bytes: 19364
#!/usr/bin/env python3
n,x = map(int,input().split())
a = list(map(int,input().split()))
def gcd(a,b):
    if b > a: a,b = b,a
    while b > 0:
        #print(a,b)
        a,b = b,a%b
    return a
cur_gcd = abs(x-a[0])
a.sort()
for i in range(n-1):
    cur_gcd = gcd(cur_gcd,abs(x-a[i+1]))
    #print(cur_gcd)
print(cur_gcd)



Measured memory_bytes: 62576
from sys import stdin
nii=lambda: map(int, stdin.readline().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            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

    def size(self, x):
        return -self.parents[self.find(x)]

n,m,k=map(int,input().split())

tree_f=[[] for i in range(n+1)]
tree_g=[[] for i in range(n+1)]

uf=UnionFind(n+1)

for i in range(m):
  a,b=nii()
  tree_f[a].append(b)
  tree_f[b].append(a)
  uf.union(a,b)

for i in range(k):
  a,b=nii()
  if uf.find(a)==uf.find(b):
    tree_g[a].append(b)
    tree_g[b].append(a)

ans=[uf.size(i)-len(tree_f[i])-len(tree_g[i])-1 for i in range(1,n+1)]
print(*ans)

Measured memory_bytes: 46844
from collections import deque
S = input()
Q = int(input())
R = 1
Top = deque()
Top.append(S)
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      Top.append(c)
    else:
      Top.appendleft(c)
S = ''.join(Top)
S = S if R==1 else S[::-1]
print(S)

Measured memory_bytes: 6900
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int[] d=new int[n];
    for(int i=0;i<n;i++){
      d[i]=sc.nextInt();
    }
    int sum=0;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        sum+=d[i]*d[j];
      }
    }
  System.out.println(sum);
  }
}

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

int main(){
  int N;
  cin >> N;
  vector<int> p(N);
  for(int i = 0; i < N; i++) cin >> p.at(i);
  vector<int> pp(N);
  pp = p;
  sort(pp.begin(), pp.end());
  int count = 0;
  for(int i = 0; i < N; i++){
    if(pp.at(i) != p.at(i)) count++;
  }
  if(count == 0 || count == 2) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
n = int(input())
a_list = list(map(int, input().split()))

ai = max(a_list)
a_list.remove(ai)
sorted([a - (ai / 2) for a in a_list])[0]

tmp = ai
cand = ai
for x in [a - (ai / 2) for a in a_list]:
    if abs(x) < tmp:
        tmp = abs(x)
        cand = int(x + (ai / 2))

print(ai, cand)

Measured memory_bytes: 14428