akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <queue>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
class Graph{
private:
  int n;// 頂点数
  int m;// 辺の数
  vector<vector<int>> edge;// 辺

  vector<int> in; //入次数
  vector<int> depth; // トポロジカルソートしたときの深さ
  
public:
  // 頂点数_nのグラフを作成
  Graph(int _n){ n = _n; edge.resize(n);  }
  // 辺コストありのグラフ作成、_n頂点、_m辺、a[i]->b[i]の辺がある。
  Graph(int _n,int _m,vector<int> a,vector<int> b){
    n = _n;m = _m;edge.resize(n);
    rep(i,m){
      add_edge(a[i], b[i]);
      //      add_edge(b[i], a[i]); //無向辺
    }
  }  

  // 辺の追加 コストなし
  void add_edge(int from,int to){ edge[from].push_back(to);}

  // トポロジカルソート
  int t_sort() { 
    in.resize(n,0);
    depth.resize(n);    
    rep(v,n) for(int w : edge[v]) in[w]++; // 全ての頂点の入次数をカウント
    
    queue<int> q;
    rep(i,n) if(in[i] == 0) { // 入次数が0の頂点はスタート地点になる
      q.push(i);
      depth[i] = 0;
    }

    int cnt = 0;
    int res = 0;
    while(!q.empty()) { 
      int v = q.front(); q.pop();
      cnt++;
      for(int w : edge[v]) {
	in[w]--; // 入次数が0の頂点から伸びた先の頂点の入次数を1減らす
	if(in[w] == 0) {
	  q.push(w);
	  depth[w] = depth[v] + 1;
	  chmax(res, depth[w]);
	}
      }
    }
    
    if(cnt == n) return res;
    else return -1;
  }

  int GetDepth(int v) { return depth[v]; }
  
};

int main()
{
  int n;cin >> n;
  vector<vector<int>> a(n, vector<int>(n-1));
  rep(i,n) {
    rep(j,n-1) {
      cin >> a[i][j]; a[i][j]--;
    }
  }

  int cnt = 0;
  map<pair<int,int>,int> mp;
  rep(i,n) {
    rep(j,n) {
      if(i >= j) continue;
      else mp[{i, j}] = cnt++;
    }
  }
  
  vector<int> b, c;
  rep(i,n) {
    rep(j,n-2) {
      if(i < a[i][j]) b.push_back(mp[{i, a[i][j]}]);
      else b.push_back(mp[{a[i][j], i}]);
      if(i < a[i][j+1]) c.push_back(mp[{i, a[i][j+1]}]);
      else c.push_back(mp[{a[i][j+1], i}]);      
    }
  }

  Graph gp(cnt, b.size(), b, c);
  int res = gp.t_sort();
  if(res >= 0) {
    cout << res+1 << "\n";
  }
  else {
    cout << -1 << "\n";
  }
  
  return 0;
}


Measured memory_bytes: 78348
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

int main() {
	int N;
	cin >> N;
	vector<int>A(N);
	rep(i, N) {
		cin >> A[i];
	}
	int cnt = 0;
	rep(i, N) {
		if (A[i] % 2) {
			cnt++;
		}
	}
	if (cnt % 2) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a,q;
    int b;
    for(int i=0;i<4;i++){
        cin >> b;
        a.push_back(b);
    }
    for(int i=0;i<2;i++){
        cin >> b;
        q.push_back(b);
    }
    sort(a.begin(),a.end(),greater<int>());
    sort(q.begin(),q.end(),greater<int>());
    int ans=0;
    for(int i=0;i<3;i++){
        ans+=a[i];
    }
    ans+=q[0];
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3236
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s=sc.next();
        String st="";
        if ( s.charAt(s.length()-1)=='s' ){
            System.out.println(s+"es");
        }else System.out.println(s+"s");
    }
}


Measured memory_bytes: 38460
# 2019-11-22 19:46:21(JST)
import sys


def main():
    n, a, b, c, d = [int(x) for x in sys.stdin.readline().split()]
    s = '#' + sys.stdin.readline().rstrip()

    if '##' in s[a+1:c-1] or '##' in s[b+1:d-1]:
        ans = 'No'
    else:
        if c < d:
            ans = 'Yes'
        else:
            for i in range(b, d+1):
                if s[i-1] == s[i] == s[i+1] == '.':
                    ans = 'Yes'
                    break
            else:
                ans = 'No'
        
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
 
int main() {
    int n;
    while (scanf("%d", &n), n) {
        string s[1005];
        vector<int>cnt[1005];
        int d[1005]{};
        rep(i, n) {
            cin >> s[i];
            int j = (int)s[i].rfind(".");
            cnt[j+1].push_back(i);
            d[i] = j + 1;
            if (j >= 0)s[i][j] = '+';
        }
        for (int i = 1; i < n; i++) {
			for(int j=1;j<cnt[i].size();j++){
				bool flag=true;
				for(int k=cnt[i][j-1]+1;k<cnt[i][j];k++){
					if(d[k]<i){
						flag=false;
						break;
					}
				}
				if(flag){
					for(int k=cnt[i][j-1]+1;k<cnt[i][j];k++)s[k][i-1]='|';
				}
			}
        }
        rep(i, n) {
            replace(s[i].begin(), s[i].end(), '.', ' ');
            cout << s[i] << endl;
        }
    }
}

Measured memory_bytes: 3828
def main():
    s=input()
    t=input()
    n=len(s)
    zumi=[]
    for i in range(n):
        ss= s[i]
        st= t[i]
        if ss != st:
            if st in zumi or ss in zumi:
                return "No"
            zumi.append(st)
            s=s.translate(str.maketrans({ss:st,st:ss}))
    return "Yes"

print(main())

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

template<class M, class N>
constexpr common_type_t<M, N> gcd(M a, N b){
	if(a < b){
		common_type_t<M, N> tmp = a;
		a = b;
		b = tmp;
	}
	if(b==0) return a;
	else return gcd(b, a%b);
}

template<class M, class N>
constexpr common_type_t<M, N> lcm(M a, N b){
	if(a==0 || b==0) return 0;
	return a*b / gcd(a, b);
}

int main() {
	long long n;
	cin >> n;
	cout << lcm(2, n) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
const int INF = 2e9;
const ll INFLL = 4e18;
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 1e6+100;
const int mod = 1e9+7;
struct range{
	int l,r,ind;
};
bool cmp(range a,range b){
	return(a.r<b.r);
}
int prev_ind[upperlimit];
int pos[upperlimit];
int a[upperlimit];
int segtree[4*upperlimit];
range qry[upperlimit];
int ans[upperlimit];
void update(int node,int i,int j,int ind,int val){
	if(! ind) return;
	if(i==j){
		segtree[node]+=val;
		return;
	}
	int mid=(i+j)>>1;
	if(ind<=mid) update(2*node,i,mid,ind,val);
	else update(2*node+1,mid+1,j,ind,val);
	segtree[node]=segtree[2*node]+segtree[2*node+1];
}
int query(int node,int i,int j,int l,int r){
	if((i>r)||(l>j)||(i>j)||(l>r)) return 0;
	if((i>=l)&&(j<=r)) return segtree[node];
	int mid=(i+j)>>1;
	return(query(2*node,i,mid,l,r)+query(2*node+1,mid+1,j,l,r));
}
int main() {
	int n,q;
	sd(n);sd(q);
	for(int i = 1; i <= n; i++){
		sd(a[i]);
		prev_ind[i]=pos[a[i]];
		pos[a[i]]=i;
	}
	for(int i = 1; i <= q; i++){
		qry[i].ind=i;
		sd(qry[i].l);sd(qry[i].r);
	}
	sort(qry+1,qry+q+1,cmp);
	int p1=1;
	for(int i = 1; i <= n; i++){
		update(1,1,n,i,1);
		update(1,1,n,prev_ind[i],-1);
		while((p1<=q)&&(qry[p1].r==i)){
			ans[qry[p1].ind]=query(1,1,n,qry[p1].l,qry[p1].r);
			p1++;
		}
	}
	for(int i = 1; i <= q; i++) pdn(ans[i]);
	return 0;
}

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

struct Node{
  Node (int z) : //constracter
    key(z),
    parent(nullptr),
    right(nullptr),
    left(nullptr)
  {}
  int key;
  Node *parent;
  Node *right, *left;
  //right == nullptr && left == nullptr
};

Node *root;

void insert(Node *z){
  Node *y=nullptr;
  Node *x=root;

  while(x!=nullptr){
    y = x;
    x = (z->key < x->key) ? x->left : x->right;
  }
  if(y == nullptr) root = z;
  else (z->key < y->key ? y->left : y->right) = z;
}

bool find(Node *node, int f){
  if(node == nullptr) return false;
  if(f == node->key) return true;
  else if(f < node->key) return find(node->left, f);
  else return find(node->right, f);
}

void inorder(Node *node){
  if(node->left != nullptr) inorder(node->left);
  std::cout << " " << node->key;
  if(node->right != nullptr) inorder(node->right);
}

void preorder(Node *node){
  std::cout << " " << node->key;
  if(node->left != nullptr) preorder(node->left);
  if(node->right != nullptr) preorder(node->right);
}

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

  int v, f;
  std::string s;
  for(int i=0; i<n; i++){
    std::cin >> s;
    if(s == "insert"){
      std::cin >> v;
      insert(new Node(v));
    }
    else if(s == "find"){
      std::cin >> f;
      if(find(root, f)) std::cout << "yes" << std::endl;
      else  std::cout << "no" << std::endl;
    }
    else{
      inorder(root);
      std::cout << std::endl;
      preorder(root);
      std::cout << std::endl;
    }
  }
  return 0;
}



Measured memory_bytes: 21892
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
 
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
 
int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    for(int i = 0; i <= 1e5; i++) {
        if(i * 8 / 100 != A) continue;
        if(i * 10 / 100 != B) continue;
        cout << i << endl;
        return 0;
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    if a[i] > x:
        ans += a[i] - x
        a[i] = x

for i in range(1, n):
    if a[i] + a[i-1] > x:
        ans += (a[i] + a[i-1]) - x
        a[i] = x - a[i-1]
print(ans)


Measured memory_bytes: 14588
N=int(input())

A=list(map(int,input().split()))
B=[]
for i in range(N):
    B.append(A[i]-i)
    
B.sort()

if N==0:
    print(1)
elif N%2==1:
    ANS=0
    for j in range(N):
        ANS+=abs(B[j]-B[N//2])
    print(ANS)
else:
    S=0
    for j in range(N):
        S+=abs(B[j]-B[N//2-1])
    L=0
    for k in range(N):
        L+=abs(B[j]-B[N//2])
    print(min(S,L))

Measured memory_bytes: 26180
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 10000000000000009
//#define INF 9223372036854775807
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define ORREP(i,n) for(int i=(n);i>=1;--i)
#define ZREP(i,n) for(int i=1;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define rollcall cout<<"I'm Sucu."<<endl;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define out(s,t,u) s?cout << t << endl:cout << u << endl
#define int ll
#define Endl endl


signed main(){
    int N,K,Ans=0;
    cin >> N >> K;
    int sum=N/K;
    Ans+=sum*sum*sum;
    sum=0;
    if(K%2==0){
        OREP(i,N){
            if(i%K==K/2)sum++;
        }
    }
    Ans+=sum*sum*sum;
    cout << Ans << endl;
    return 0;
}   


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

int selectionSort(int A[],int N){
	
	int count=0;
	for(int i=0; i<N-1; i++){
		
		int minj=i;
		for(int j=i; j<N; j++){
			
			if(A[j]<A[minj]){
				
				minj=j;
				
				
			}
			
		}
		swap(A[i],A[minj]);
			if(i!=minj){
			    
			    count++;
			    
			}
		
	}
	
	return count;
	
}

int main(){
	
	int N,count;
	cin >>N;
	int A[N];
	for(int i=0; i<N; i++){
		
		cin >>A[i];
		
	}
	
	count=selectionSort(A,N);
	
	for(int i=0; i<N; i++){
		
		if(i){
			
			cout <<" ";
			
		}
		cout <<A[i];
		
	}
	cout <<endl;
	cout <<count <<endl;
	
}


Measured memory_bytes: 3104
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7

ans = 0
for i in range(N):
  ans += A[i]

dig = 0
for i in range(N):
  dig += (A[i] ** 2 % MOD)
  
ans = (ans**2 - dig) % MOD

if ans % 2 == 0:
  print(ans // 2)
else:
  print((ans + MOD) //2)

Measured memory_bytes: 31608
#coding:utf-8

N = int(input())

ron = 10 ** 9 + 7

a = (10 ** N) % ron

b = (9 ** N) % ron

c = (9 ** N) % ron 

bandc = (8 ** N) % ron

ans = (a - b - c + bandc) % ron

print("{}".format(ans))

Measured memory_bytes: 10364
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n,num,Num[100],m; 
int judge(int x){
	int cnt = 0 ,numm[10];
	while(x > 0){
		numm[cnt++] = x % 10;
		x = x / 10;
	}
	int ret = 1;
	for(int i = 0  ; i < cnt ; i++){
		if(Num[numm[i]] == 1){
			ret = 0;
			break;
		}
	}
	return ret;
}



int main(){
	scanf("%d %d",&n,&num);
	for(int i = 0 ; i < num ; i++){
		scanf("%d",&m);
		Num[m] = 1;
	}
	while(judge(n) == 0){
		n++;
	}
	printf("%d\n",n);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>;
//**関数リスト**//
int ctoi(char c) {
	switch (c) {
	case '0': return 0;
	case '1': return 1;
	case '2': return 2;
	case '3': return 3;
	case '4': return 4;
	case '5': return 5;
	case '6': return 6;
	case '7': return 7;
	case '8': return 8;
	case '9': return 9;
	default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.second < secondElof.second;
}
ll nod(ll F) {
	ll keta = 1;
	while (F / 10 > 0) {
		keta++; F /= 10;
	}
	return keta;
}
ll gcd(ll x, ll y) {
	ll r;
	if (x < y) {
		swap(x, y);
	}
	while (y > 0) {
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
ll isPrime(ll x) {
	ll i;
	if (x < 2) {
		return 0;
	}
	else if (x == 2) {
		return 1;
	}
	else if (x % 2 == 0) {
		return 0;
	}
	else {
		for (i = 3; i * i <= x; i += 2) {
			if (x % 1 == 0) {
				return 0;
			}
		}
		return 1;
	}
}
void eratos(vl isPrime) {
	//(注)isPrimeのサイズはN+1にする！実際にはmain内に配置して使用
	ll i, j;
	for (i = 0; i < isPrime.size(); i++) {
		isPrime[i] = 1;
	}
	isPrime[0] = 0; isPrime[1] = 0;
	for (i = 2; i * i <= isPrime.size() - 1; i++) {
		if (isPrime[i] == 1) {
			j = i * 2;
			while (j <= isPrime.size() - 1) {
				isPrime[j] = 0;
				j = j + i;
			}
		}
	}
}
ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll alphabet(char C) {
	ll b = 0; ll key = 0;
	if (C == 'a') { return b; }b++;
	if (C == 'b') { return b; }b++;
	if (C == 'c') { return b; }b++;
	if (C == 'd') { return b; }b++;
	if (C == 'e') { return b; }b++;
	if (C == 'f') { return b; }b++;
	if (C == 'g') { return b; }b++;
	if (C == 'h') { return b; }b++;
	if (C == 'i') { return b; }b++;
	if (C == 'j') { return b; }b++;
	if (C == 'k') { return b; }b++;
	if (C == 'l') { return b; }b++;
	if (C == 'm') { return b; }b++;
	if (C == 'n') { return b; }b++;
	if (C == 'o') { return b; }b++;
	if (C == 'p') { return b; }b++;
	if (C == 'q') { return b; }b++;
	if (C == 'r') { return b; }b++;
	if (C == 's') { return b; }b++;
	if (C == 't') { return b; }b++;
	if (C == 'u') { return b; }b++;
	if (C == 'v') { return b; }b++;
	if (C == 'w') { return b; }b++;
	if (C == 'x') { return b; }b++;
	if (C == 'y') { return b; }b++;
	if (C == 'z') { return b; }
	return -1;
}
void bitSearch(ll n) {
	//実際にはコピーして中身を改変して使う
	ll i;
	for (i = 0; i < pow(2, n); i++) {
		ll p = i;
		for(i = 0; i < n; i++) {
			cout << p % 2; p /= 2;
		}
		cout << endl;
	}
}
void bfs(ll now) {
	//中身は毎回書き換えて使用
	queue<ll> Q;
	Q.push(now);
	ll u;
	while (!Q.empty()) {
		u = Q.front();
		Q.pop();
		//ll v=;
		//Q.push(v);
	}
}
//**定義場所**//
ll i, j, k, l, m, n, N, M, K, H, W;
ll MOD = 1000000007; ll ans = 0;
//***********//
int main() {
	cin >> N;
	cout << pow(N, 3);
}

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


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  int x[105];
  cin>>n;
  int mini=1<<30;
  rep(i,n)cin>>x[i];
  for(int i=1;i<=100;i++){
    int tmp=0;
    rep(j,n)tmp+=(x[j]-i)*(x[j]-i);
    if(tmp<mini)mini=tmp;
  }
  cout<<mini<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a,b,ans;
    char op;
    
    while(1)
    {
        scanf("%d %c %d\n",&a,&op,&b);
    
        if(op == '?')
        
        {
            break;
        }
            if(op == '+')
    {
        ans = a + b;
        printf("%d\n",ans);
    }else if(op == '-')
    {
        ans = a - b; 
        printf("%d\n",ans);
    }else if(op == '*'){
        ans = a * b;
        printf("%d\n",ans);
    }else if(op == '/'){
        ans = a/b;
        printf("%d\n",ans);
    }else {
        return 0;
    }
    
    }
    

    return 0;

}


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

using namespace std;

int main()
{
  int n, m; cin >> n >> m;
  vector <set <int>> a(n);

  for (int i = 0; i < m; ++i)
{
  int c, d; cin >> c >> d;
  a[c - 1].insert(d);
}

  for (auto elem : a[0])
  if (a[elem - 1].count(n))
  {
    cout << "POSSIBLE" << endl;
    return 0;
  }

  cout << "IMPOSSIBLE" << endl;

  return 0;
}

Measured memory_bytes: 18944
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;
int n;
string s;
int a[1000006];
int main()
{
	cin>>s;
	if(s.size()<=3)cout<<"No"<<endl;
	else
	{
		if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I')
		{
			cout<<"Yes"<<endl;
		}
		else cout<<"No"<<endl;
	}
	return 0;
}

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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
 
	//cin.tie(0); ios_base::sync_with_stdio(false);
	const int MX=200001;
	int n, ch;
	cin >>n >>ch;
	vector<vector<pii>> dt(ch);
	//VI s(n), t(n), c(n);
	
	rep(i, n){
		int s,t,c;
		cin >>s >> t >>c;
		dt[c-1].push_back(pii(2*s-1, 2*t));
	}
	rep(i,ch) sort(all(dt[i]));
	vector<int> usd(MX+20);

	rep(i,ch){
		int fr=0, to=0;
		rep(j, sz(dt[i])){
			if(dt[i][j].first > to || to==0){
				if(to >0){
					usd[fr] +=1;
					usd[to] -=1;
					//dbg(i,fr,to);
				}
				tie(fr,to) = dt[i][j];
			}
			if(dt[i][j].first <= to){
				to = max(to, dt[i][j].second);
			}
		}
		usd[fr] +=1;
		usd[to] -=1;
		//dbg(i,fr,to);
	}
	rep(i, MX) usd[i+1] += usd[i];
	//rep(i,100) printf("%d, ",usd[i]); puts("");
	cout << *max_element(all(usd)) <<"\n";
	
	return 0;
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>

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

  int retval = 0;
  rep(i,N){
    if (i==p[i]){
      retval++;
      if (i-1<N && i+1==p[i+1]) i++;
    }
  }
  cout << retval << endl;



  // cout << fixed << setprecision(10);
  
  return 0;
}



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

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

// calculate ap + bq = gcd(a, b)
// return d = gcd(a, b)
ll extGcd(ll a, ll b, ll& p, ll& q) {
    if(b == 0) {
        p = 1;
        q = 0;
        return a;
    }
    ll d = extGcd(b, a % b, q, p);
    q -= a / b * p;
    return d;
}

// let return val be (r, m),
// x == r (mod. m)
// (r, m) == (0, -1) if not exist
pair<ll, ll> ChineseRem(ll b1, ll m1, ll b2, ll m2) {
    ll p, q;
    ll d = extGcd(m1, m2, p, q); // p is inv of m1/d (mod. m2/d)
    if((b2 - b1) % d != 0) return {0, -1};
    ll m = m1 * (m2 / d); // lcm of (m1, m2)
    ll tmp = (b2 - b1) / d * p % (m2 / d);
    ll r = ((b1 + m1 * tmp) % m + m) % m;
    return {r, m};
}

int main() {
    ll n;
    cin >> n;
    ll m = 2 * n;
    vector<ll> ps;
    for (ll x = 2; x * x <= m; ++x) {
        if(m % x) continue;
        ps.push_back(x);
        m /= x;
        while(m % x == 0) {
            ps.back() *= x;
            m /= x;
        }
    }
    if(m != 1) ps.push_back(m);

    ll ans = 2 * n - 1;
    int sz = ps.size();
    for (int bit = 0; bit < (1 << sz); ++bit) {
        ll a = 1, b = 1;
        for (int i = 0; i < sz; ++i) {
            if(bit >> i & 1) {
                a *= ps[i];
            } else {
                b *= ps[i];
            }
        }
        assert(gcd(a, b) == 1);
        ll p, q;
        extGcd(a, -b, p, q);
        ll l = lcm(a, b);
        while(a * p <= 1) {
            p += l;
        }
        ans = min(ans, p * a);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3640
"
ABC162C
https://atcoder.jp/contests/abc162/tasks/abc162_c
"

K = gets.to_i
ans = 0
1.upto(K) do |a|
  1.upto(K) do |b|
    1.upto(K) do |c|
      ans = ans + a.gcd(b.gcd(c))
    end
  end
end
puts ans

Measured memory_bytes: 14408
N = int(input())

name = ""

def num2char(n) :
  if n == 0:
    n = 26
  return chr(n+96)

while(N > 26) :
  m = N%26
  name = num2char(m) + name
  N = int(N/26)
  if m == 0 :
    N -= 1
  
name = num2char(N) + name
print(name)


Measured memory_bytes: 9104
#include <iostream>

using namespace std ;

int main ()
{
 int a ,b;
 cin >> a>>b;


 if (1<=a&&a<=9 && 1<=b&&b<=9)
 {
    cout <<(a*b) ;

 }

else
{
    cout << -1 << endl ;
}



    return 0 ;
}


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

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  
  vector<int> west(N + 1);
  vector<int> east(N + 1);
  for (int i = 0; i <= N; i++) {
    if (i == 0) west.at(i) = 0;
    else if (S.at(i - 1) == 'W') west.at(i) = west.at(i - 1) + 1;
    else west.at(i) = west.at(i - 1);
  }
  for (int i = 0; i <= N; i++) {
    east.at(i) = i - west.at(i);
  }
  
  int min_count = N;
  for (int a = 0; a <= N; a++) {
    int count_l, count_r;
    count_l = west.at(a) - west.at(0);
    count_r = east.at(N) - east.at(a);
    int count = count_l + count_r;
    if (count < min_count) min_count = count;
  }
  
  cout << min_count << endl;
}

Measured memory_bytes: 3076
#include <iostream>
#include <vector>
using namespace std;
long long ryuka(int x);
	vector<long long> row(88);
int main() {
 int N;
 long long M;
 cin>>N;

M=ryuka(N);

cout<<M<<endl;

}

long long ryuka(int x){
	long long y;
	row.at(0)=2;
	row.at(1)=1;
	if(x==0)return 2;
	if(x==1)return 1;
row.at(x)=ryuka(x-1)+row.at(x-2);
y=row.at(x);
return y;
}

Measured memory_bytes: 256
using System;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Linq;

class Program
{
	static void Main(string[] args)
	{
		long[] intArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
		int H = (int)intArray[0];
		int W = (int)intArray[1];
		int[,] ans = new int[H, W];

		for (int i = 0; i < H; i++)
		{
			char[] tmp = Console.ReadLine().ToCharArray();
			for (int j = 0; j < W; j++)
			{
				if (tmp[j] == '#')
				{
					ans[i, j] = 9;

					for (int hh = i - 1; hh <= i + 1; hh++)
					{
						if (hh < 0 || H <= hh)
							continue;
						for (int ww = j - 1; ww <= j + 1; ww++)
						{
							if (ww < 0 || W <= ww)
								continue;
							if (H == hh && W == ww)
								continue;
							ans[hh, ww]++;
						}
					}
				}
			}
		}

		string a = "";
		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (ans[i, j] < 9)
					a += ans[i, j].ToString();
				else
					a += "#";
			}
			if(i != H - 1)
				a += "\n";
		}

		Console.WriteLine(a);
	}

	/// <summary>
	/// アナグラム
	/// </summary>
	/// <param name="word1"></param>
	/// <param name="word2"></param>
	/// <returns></returns>
	static bool IsAnagramOf(string word1, string word2)
	{
		return word1.OrderBy(x => x).SequenceEqual(word2.OrderBy(x => x));
	}
	/// <summary>
	/// 最小公倍数
	/// </summary>
	/// <param name="a"></param>
	/// <param name="b"></param>
	/// <returns></returns>
	public static long Lcm(long a, long b)
	{
		return a * b / Gcd(a, b);
	}

	/// <summary>
	/// 最大公約数
	/// </summary>
	/// <param name="a"></param>
	/// <param name="b"></param>
	/// <returns></returns>
	public static long Gcd(long a, long b)
	{
		if (a < b)
			// 引数を入替えて自分を呼び出す
			return Gcd(b, a);
		while (b != 0)
		{
			var remainder = a % b;
			a = b;
			b = remainder;
		}
		return a;
	}
}




//string s = Console.ReadLine();
//int[] intArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
//int H = intArray[0];
//int W = intArray[1];
//int N = int.Parse(Console.ReadLine());
//List<int> A = new List<int>(Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray());
//Boolean ok = false;

//Console.WriteLine(ans);
//Console.WriteLine("Yes");
//Console.WriteLine("No");
//Console.ReadKey();
//Console.WriteLine(cnt);

//string[] strArray = Console.ReadLine().Split(' ').ToArray();
//string S = strArray[0];
//string T = strArray[1];


Measured memory_bytes: 34380
#include<stdio.h>

int main(){
	char a[100],i,j,b[100],c;
	for(j=0;j<1000;j++){
		gets(a);
		c=1;
		b[0]=')';
		if(a[0]=='.'){
			return 0;
		}
		for(i=0;i<100;i++){
			if((a[i]=='(')||(a[i]=='[')){
				b[c]=a[i];
				c++;
			}
			if(a[i]==')'){
				if(b[c-1]=='('){
					c--;
				}
				else{
					printf("no\n");
					c--;
					break;
				}
			}
			if(a[i]==']'){
				if(b[c-1]=='['){
					c--;
				}
				else{
					printf("no\n");
					c--;
					break;
				}
			}
			if(a[i]=='.'){
				if(c==1){
				printf("yes\n");
					break;
				}else{
					printf("no\n");
					break;
				}
				
				
	}}
	}
return 0
;}

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

#define ll long long
#define pb push_back
#define f first
#define s second
//#define mp make_pair
#define gg return 0;
#define pii pair < int, int>

using namespace std;

const int maxn = 132675;
const int INF = (int)1e9;

ll a,b[maxn],c,d,cnt,e[(int)2e3 + 1][(int)2e3 + 1],cost[maxn],tout[maxn],mn = INF,mx = -INF,l,r;

ll x[maxn],y[maxn],x2[maxn],y2[maxn];

bool m;

vector <int> v;

void forn( int s, int f, int inter){
	for(int i = s; i <= f; i += inter){
		b[i] = i;
	}
}

string s;

ll pref;

//vector <int> g[maxn],d[maxn];

ll lvlc,lvl[maxn];
/*
void dfs(int v){
	lvlc++;
	lvl[v] = lvlc;
	d[lvl[v]].pb(v);
	u[v] = 1;
	for(int i = 0; i < g[v].size(); ++i){
		int to = g[v][i];
		if(!u[to]){
			dfs(to);
		}
	}
	lvlc--;
}*/

map <char, int> mp;

char ch;

int main()
{
	cin >> s;
	for(int i = 0; i < s.size(); ++i){
		mp[s[i]]++;
	}
	for(int i = 0; i < s.size(); ++i){
		if(mp[s[i]] % 2 == 1){
			cout << "No" << "\n";
			gg
		}
	}
	cout << "Yes" << '\n';
	gg;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    long long N, H, W;
    cin >> N >> H >> W;

    long long cnt = 0;

    for (int i = 0; i < N; i++){
        long long A, B;
        cin >> A >> B;

        if (A >= H && B >= W){
            cnt++;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<queue>
#include<list>
#include<stdio.h>
#include<stdlib.h>
#include<map>
#include<cstdio>
#include <iomanip>

#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

using namespace std;
typedef long long ll;
using P = pair<ll, ll>;

int main() {

	const int inf = 100000000;

	int n, m;
	cin >> n >> m;

	int a[1000], b[1000], c[1000], dist[100][100];

	//入力を受け取る
	//0-オリジンのため-1
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--, b[i]--;
	}

	//距離用の配列の初期化
	//自己辺は無いのでi=jは0
	//それ以外は未到達にしておく。
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) {
				dist[i][j] = 0;
			}
			else {
				dist[i][j] = inf;
			}
		}
	}	

	//隣接している頂点i-jに辺を張る
	//今記録されている値よりも、直接いったほうが近ければ辺を貼りなおす。
	for (int i = 0; i < m; i++) {
		dist[a[i]][b[i]] = c[i];
		dist[b[i]][a[i]] = c[i];
	}

	//WFで任意の2点間の最短距離を格納していく。
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	int ans = m;
	//辺を一つ一つみていって、最短距離＋直接つないだ距離＝最短距離になっているか
	//調べる

	//Eij:a[i]-b[i]という辺を固定して、頂点について全探索。
	//Eijが最短距離に含まれていれば結果をへらす(ほしい出力は最短距離に含まれて"いない"辺の数のため)


	for (int i = 0; i < m; i++) {
		bool shortest = false;
		//終点jに対して
		for (int j = 0; j < n; j++)if (dist[j][a[i]] + c[i] == dist[j][b[i]])shortest = true;
		if (shortest == true) {
			ans--;
		}
	}

	cout << ans << endl;

	return 0;
}


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

using namespace std;
typedef long long ll;

int main()
{
    ll N, K;
    cin >> N >> K;

    vector<ll> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];

    ll X = 0;
    for (int i = 40; i >= 0; i--)
    {
        ll bit = 1LL << i;
        if (bit > K)
            continue;

        int count = 0;
        for (int j = 0; j < N; j++)
            if ((A[j] & bit) > 0)
                count++;
        if (count < N - count and X + bit <= K)
            X += bit;
    }

    ll ans = 0;
    for (int i = 0; i < N; i++)
        ans += X ^ A[i];

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    s[3] = '8';
    cout << s << endl;
}


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

long long A, B, N;

long long dif(long long x) {
    long long a = A * x;
    a /= B;
    long long b = x / B;
    b *= A;
    return a - b;
}

long long bi(long long mi, long long ma, long long target) {
    if (ma - mi == 1 || ma - mi == 0) {
        return dif(ma);
    }
    
    long long mid = (ma + mi) / 2;
    long long midValue = dif(mid);
    if (midValue >= target) {
        return bi(mi, mid, target);
    } else {
        return bi(mid, ma, target);
    }
}

int main() {
    cin >> A >> B >> N;
    long long valueN = dif(N);
    long long x = N / B;
    x *= B;
    x -= 1;
    if (x < 0) { x = 0; }
    long long valueLastEdge = dif(x);
    long long target = max(valueN, valueLastEdge);
    cout << bi(0, min(N, B - 1), target);
}

Measured memory_bytes: 3632
def check3(m):
    m = str(m)
    if '3' in m:
        return True
    else:
        return False

n = int(input())

i = 1


while i <= n:
    x = i
    if x%3 == 0 or x%10 == 3:
        print(" %d" % i, end = '')
        i += 1
    else:
        isThree = check3(x)
        if isThree:
            print(" %d" % i, end = '')
        i += 1
print("")

Measured memory_bytes: 8012
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x;scanf("%d",&x);return x;
}
char ch[2001020];
int ans = 0;
int main()
{
	int n,x,t;
	cin>>n>>x>>t;
	cout << ((n-1)/x+1)*t<<endl;
	return 0;
}

Measured memory_bytes: 3632
function Main(input) {
    input = input.split(" ");
    one = false;
    nana = false;
    nine = false;
    four = false;
    for(i = 0; i < 4; i++){
        if(Number(input[i]) === 1) one=true;
        if(parseInt(input[i]) == 7) nana = true;
        if(parseInt(input[i]) == 4) four = true;
        if(Number(input[i]) == 9) nine = true;
    }
  if(one && nana && nine && four){
    console.log('YES')
  }else{
    console.log('NO')
  }
    
}


Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
import bisect

N=int(input())
L=list(map(int,input().split()))

L.sort()
#print(L)

ans=0
for i in range(N-1,-1,-1):
  for j in range(i-1,-1,-1):
    if L[i]>=2*L[j]:
      break
    #print(L[i],L[j],bisect.bisect(L,L[i]-L[j]),j-bisect.bisect(L,L[i]-L[j]))
    ans+=j-bisect.bisect(L,L[i]-L[j])
print(ans)

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


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = []
for a, b in LIR(n):
    L += [(a, b)]


L.sort()
ret = 0
i = 0
for a, b in L:
    ret += b
    ans = a
    if ret >= k:
        break


print(ans)

Measured memory_bytes: 65628
import core.bitop;
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
  string s = readln.chomp;
  string t = readln.chomp;
  string ans = '~'.repeat.take(s.length).array;
  foreach (i; 0 .. s.length - t.length + 1)
  {
    bool ok = true;
    foreach (j, c; t)
    {
      ok &= s[i + j] == '?' || s[i + j] == c;
    }
    if (ok)
    {
      char[] sub = s.map!(a => cast(char)(a == '?' ? 'a' : a)).array;
      foreach (j, c; t)
      {
        sub[i + j] = c;
      }
      ans = min(ans, sub.idup);
    }
  }
  if (ans.front == '~')
  {
    "UNRESTORABLE".writeln;
    return;
  }
  ans.writeln;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i< (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
//long long ccw(const Point& A, const Point& B, const Point& C) {
//	return 1LL * (B.x - A.x)*(C.y - A.y) - 1LL * (B.y - A.y)*(C.x - A.x);
//}

int main() { // E,F , virtual
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string s; cin >> s;
	int x = (s[0] - '0') * 10 + (s[1] - '0');
	int y = (s[2] - '0') * 10 + (s[3] - '0');
	if (x <= 12 && y <= 12 && x > 0  && y > 0) {
		cout << "AMBIGUOUS" << '\n';
	}
	else if (x <= 12&& x > 0) {
		cout << "MMYY" << '\n';
	}
	else if (y <= 12 && y > 0) {
		cout << "YYMM" << '\n';
	}
	else {
		cout << "NA" << '\n';
	}




}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll ans;
	ans=a*c;
	ans=max(ans,a*d);
	ans=max(ans,b*c);
	ans=max(ans,b*d);
	cout<<ans;
}

Measured memory_bytes: 3608
#include<stdio.h>
#include<string.h>

int main() 
{
	char str[100], str1[100] = {0};
	int cnt = 0, i, len, j;

	while (scanf("%s", str) != EOF) {
		len = strlen(str);
		for (i = 0, j = len - 1; j >= 0; i++, j--)
		{
			str1[i] = str[j];
		}
		str1[len] = '\0';
		if (strcmp(str, str1) == 0)
		{
			++cnt;
		}
	}
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 548
#include <bits/stdc++.h>
const int N = 5e5 + 1;
int n, d[ N ], f[ N ], s[ N ];
int main( )
{
 std::cin >> n >> d[ 0 ];
 for( int i = 1; i <= n; ++i )
 {
  std::cin >> s[ i ];
  d[ i ] = d[ i - 1 ];
  if( d[ i ] >= s[ i ] )
   d[ i ] -= s[ i ];
  else if( s[ i ] < 2 * d[ i ] )
   d[ i ] = s[ i ] - d[ i ];
 }
 f[ n + 1 ] = 1;
 for( int i = n; i; --i )
  if( f[ i + 1 ] <= s[ i ] / 2 )
   f[ i ] = f[ i + 1 ];
  else
   f[ i ] = f[ i + 1 ] + s[ i ];
 int m;
 std::cin >> m;
 while( m-- )
 {
  int x;
  std::cin >> x;
  if( d[ x - 1 ] >= f[ x + 1 ] )
   std::cout << "YES\n";
  else
   std::cout << "NO\n"; 
 }
 return 0;
}

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


#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int x, y;
	string s;
	cin >>s >>x >>y;
	
	VI vx, vy;
	s +='E';
	int sm =0, cr =0, n =sz(s);
	rep(i, n){
		if(s[i]=='F') sm++;
		else{
			(cr? vy: vx).push_back(sm);
			cr ^=1; sm =0;
		}
	}
	
	auto ckd=[&](const VI& v, int tgt, int xfg=1)->bool{
		vector<bool> ck(n*2+6);
		ck[n+3] = 1;
		int fsw =0;
		for(auto z: v){
			vector<bool> nck(n*2+6);
			rep(i, n*2+6) if(ck[i]){
				if(xfg && fsw++==0) nck[i+z] = 1;
				else nck[i+z] = nck[i-z] = 1;
			}
			swap(ck, nck);
		}
		return ck[n+3+tgt];
	};
	bool xx = ckd(vx, x, 1);
	bool yy = ckd(vy, y, 0);
	puts((xx && yy)? "Yes": "No");
	return 0;
}


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

#define ff first
#define ss second
#define mp make_pair

using namespace std;

typedef long long ll;

int a[1005];
int v[1005], n, m;
bool mark[1005][4098];
int dp[1005][4098];

int f(int c, int mask) {
	if(mask == (1<<n)-1) return 0;
	if(c == m) return 1e9;
	if(mark[c][mask]) return dp[c][mask];
	mark[c][mask] = 1;

	int ret = min(a[c] + f(c+1, mask | v[c]), f(c+1, mask));

	return dp[c][mask] = ret;
}

int main() {
    int qtt,aux;

    scanf("%d%d",&n, &m);

    for(int i = 0; i < m; i++) {
    	scanf("%d%d", &a[i], &qtt);
    	int mask = 0;
    	while(qtt--) {
    		scanf("%d", &aux);
    		mask |= (1<<(aux-1));
    	}
    	v[i] = mask;
    }

    int ans = f(0,0);

    if(ans >= 1e9) ans = -1;

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

    return 0;
}


Measured memory_bytes: 20352
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <math.h>
#include <string>
#include <math.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> Q;

const ll mod = 1000000007;
const ll INF = 1000000000000;



ll N, M, ans;
vector<ll> vec[100010];
priority_queue<ll> que;

int main()
{
	cin >> N >> M;
	

	for (int i = 0; i < N; i++)
	{
		ll a, b;
		cin >> a >> b;
		vec[a].push_back(b);
	}

	for (int i = 1; i <= M; i++)
	{
		for (int j = 0; j < vec[i].size(); j++)
		{
			que.push(vec[i][j]);
		}
		if (que.size())
		{
			ans += que.top();
			que.pop();
		}
	}


	cout << ans << endl;

	int www;
	cin >> www;
}

Measured memory_bytes: 5632
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

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

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
string S;

int main(){
    cin >> S;
    int count =0;
    if(S.length()%2==0){
        for(int i=0;i<S.length()/2;i++){
            if(S[i]!=S[S.length()-i-1])count++;
        }
    }else{
        for(int i=0;i<S.length()/2;i++){
            if(S[i]!=S[S.length()-1-i])count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

bool cmp(pii a,pii b){
	return a.second<b.second;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;cin >> n >> m;
	vector<pii> a(m);
	rep(i,m) cin >> a.at(i).first >> a.at(i).second;
	sort(a.begin(),a.end(),cmp);
	int ans=0,end=a.at(0).second;
	rep(i,m){
		if(a.at(i).first<end) end=min(end,a.at(i).second);
		else{
			ans++;
			end=a.at(i).second;
		}
	}
	cout << ans+1 << endl;
}

Measured memory_bytes: 1024
n, *a = map(int, open(0).read().split())
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    cnt = 0
    for j in range(n):
        cnt += a[j] >> i & 1
    ans = (ans + (1 << i) * cnt * (n - cnt) % mod) % mod
print(ans)


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

//C++14 (GCC 5.4.1)

#define LLINF (1LL<<60)
typedef long long ll;
#define mod 1000000007

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)

template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<typename T> inline T divrup(T a, T b) { if (a % b) return a/b+1; else return a/b;}

#define dbg_v1(i,V) do{cout<<"-v1----\n";rep(i,V.size())cout<<" "<<i<<"\t:"<<V[i]<<endl;cout<<endl;}while(0)
#define dbg_v2(i,k,V) do{cout<<"-v2----\n";rep(i,V.size()){rep(k,V[0].size())cout<<" "<<V[i][k];cout<<endl;}}while(0)

int main() {
    ios::sync_with_stdio(false);//stdoutとcoutの同期解除
    cin.tie(nullptr);//cinとcoutの同期解除
    
    int A,B;
    cin >>A>>B;

    int kuchi=1,ans=0;
    while(kuchi<B){
        kuchi+=A-1;
        ans++;
    }

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

Measured memory_bytes: 256
/*jai_ganeshdeva*/

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pu push  //  adds the value to the last of the queue 
#define lld long long int
#define ins insert /// used in set to insert the values 
#define adv advance  /// used to increment the iterator
#define mp make_pair
#define fi first
#define se second
#define all(c) c.begin(),c.end()
#define PI 3.1415926
#define INF (lld)1e18
#define vl  vector<long long int >
#define vpl vector< pair<lld ,lld> >
#define vvl vector<vector<lld> > 
#define pll pair <lld,lld>
long long int modp(lld a,lld p,lld n)
{
   lld d[100];
    lld i,j,k,l;
    if(n==0) return 1;
    for(i=0;n>=1;i++)
    {
        d[i]=n%2;
        n/=2;
    }
    l=i;
    long long int e=1;
    if(d[0]==1) e*=(a%p);
    for(i=1;i<l;i++)
    {
        a*=a;
        a=a%p;
        if(d[i]==1) 
        {
            e*=a;
            e=e%p;
        }
    }
    return e%p;
}
lld modInverse(lld n, lld p) 
{ 
    return modp(n, p, p-2); 
}

//lld fac[100001]; 
/*
void solve2()
{
   lld p=1000000007;
    fac[0] = 1; 
    for (lld i=1 ; i<=100000; i++) 
        fac[i] = fac[i-1]*i%p; 
}    

long long int nCrModPFermat(lld n, lld r,lld p) 
{ 
   // Base case 
   if (r==0) 
      return 1; 
     
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
}


long long int gcd(lld b,lld a)
{
    if(a<b) return gcd(a,b);
    if(a%b==0) return b;
    return gcd(a%b , b);
}
*/
lld p1=1000000007,p2=998244353;
lld l,r,mid,ans;
lld n,m,i,j,k;
lld x,y,n1,a,b,n2,h,z,c;
queue<lld> q;
lld d,p=1000000000;
//vector< vector <lld > > v(100001);
/*
void bfs(lld x , vector<lld>& d)
{
    d[x]=0;
    q.pu(x);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        l=v[x].size();
        for(i=0;i<l;i++)
        {
            y=v[x][i];
            if(d[y]==INF) 
            {
                d[y] = d[x]+1;
                q.pu(y);
            }       
        }
    }

}
/*

lld DFS(lld a ,lld x)
{
    visited[a] =true;
    sub_size[a]=1;
 //   if(a==x) 
   //     cont[a] =true;
    lld l= v[a].size();
    for(lld i=0;i<l;i++)
    {
        if(visited[v[a][i]] == false)
        {
            sub_size[a]+= DFS(v[a][i],b);
//            if(cont[v[a][i]] ==true ) cont[a]=true;
        }
    }
    return sub_size[a];

}
*/

void solve()
{
    lld a,b,n;
    cin>>a>>b>>n;
    if(n>=b-1)
    {
        ans=a-(a/b)-(a%b?1:0);
        cout<<ans;
    }
    else
    {
        x=a/b;
        y=n/b;
        ans=x*y+(x)*(n%b)+(y)*(a%b)+(((a%b)*(n%b))/b);
        cout<<ans;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t=1;
    
 //   cin>>t;
 //   solve2();
    for(int i=0;i<t;i++)
    {
   //     cout<<"Case #"<<i+1<<": ";
        solve();
        cout<<"\n";
    }

    return 0;
}

Measured memory_bytes: 3648