akhauriyash/Code-Regression huggingface dataset:
N = int(input())
P = list(map(int, input().split()))

class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + 1
    s.T[k - 1] = max(s.T[k - 1], v)
    k += k & -k
    while k <= s.N:
      s.T[k - 1] = max(s.T[k - 1], v)
      k += k & -k
  def getV(s, x):
    if x <= 0:
      return 0
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans = max(ans, s.T[x - 1])
      x -= x & -x
    return ans

class segMin:
  inf = N + 1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    if l > r:
      return s.inf
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = BIT(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  #print(ans)
  t = D[i]
  ma = TMa.getV(t)
  ma2 = TMa.getV(ma)

  mi = TMi.getV(t, N + 1)
  mi2 = TMi.getV(mi + 1, N + 1)
  #print(ma2, ma, t, mi, mi2, ans)
  TMa.update(t, t)
  TMi.update(t, t)
  ans += (mi - t) * (ma - ma2) * i
  ans += (mi2 - mi) * (t - ma) * i

print(ans)


Measured memory_bytes: 119944
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); i++)
#define repi(i,a,b) for (int i=a;i<(b);i++)
using namespace std;
typedef long long ll;
  
  int main(void){
    cin.tie(0); //cin高速化
    ios::sync_with_stdio(false); //cin高速化
	
    int a,b,k;
    cin >> a >> b >> k;
    vector<int> list(k*2);
    if(k>=b-a+1){
      repi(i,a,b+1){
        cout<<i<<endl;
      }
      return 0;
    }
    repi(i,a,a+k){
      list.push_back(i);
    }
    for(int i=b;i>b-k;i--){
      list.push_back(i);
    }
    sort(list.begin(),list.end());
    auto itr = unique(list.begin(),list.end());
    list.erase(itr,list.end());
    list.erase(list.begin() + 0);
    rep(i,list.size()){
    cout << list[i] << endl;
    }
    return 0;

  }    

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using lint = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main()
{
    int N;
    scanf("%d", &N);
    printf("%d\n", N*(N+1) / 2);

    return 0;
}


Measured memory_bytes: 256
mod=10**9+7
n,a,b=map(int,input().split())
pows=[2]
for _ in range(40):
  pows.append((pows[-1]**2)%mod)
ans=1
flag=format(n,'b')
if len(flag)<31:
  flag=(31-len(flag))*'0'+flag
flag=flag[::-1]
for i in range(31):
  if flag[i]=='1':
    ans*=pows[i]
    ans%=mod
ans-=1
rfacts=[pow(1,mod-2,mod)%mod,pow(1,mod-2,mod)%mod]
for i in range(2,2*(10**5)+1):
  rfacts.append((rfacts[-1]*pow(i,mod-2,mod))%mod)
if n<=2*10**5:
  fact=1
  for i in range(2,n+1):
    fact*=i
    fact%=mod
  ans-=(fact*rfacts[a]*rfacts[n-a])%mod
  ans%=mod
  ans-=(fact*rfacts[b]*rfacts[n-b])%mod
  ans%=mod
else:
  fact1=1
  for i in range(n,n-a,-1):
    fact1*=i
    fact1%=mod
  ans-=(fact1*rfacts[a])%mod
  ans%=mod
  fact2=1
  for i in range(n,n-b,-1):
    fact2*=i
    fact2%=mod
  ans-=(fact2*rfacts[b])%mod
  ans%=mod
print(ans)

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int d=0;
    int q=0;
    int o=0;
    for(int i = 0; i < n; i++) {
        if(a[i]%4==0)      q++;
        else if(a[i]%2==0) d++;
        else               o++;
    }

    if((d==0 && q>=o-1) || (d==n) || (q>=o)) cout << "Yes" << "\n";
    else cout << "No" << "\n";

    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <vector>

using namespace std;

using ll = long long;

const ll inf = 4e18;

ll n, t, q;
ll a[123456];
bool d[123456];
ll x[1000];
vector<ll> talkp;
ll place[123456];

inline ll mean(ll a, ll b) { return a/2 + b/2; }

int main()
{
	scanf("%lld %lld %lld", &n, &t, &q);
	a[0] = -inf; d[0] = true;
	for (int i = 1; i <= n; ++i)
	{
		int tmpd;
		scanf("%lld %d", a + i, &tmpd);
		d[i] = (tmpd == 1);
	}
	a[n + 1] = inf; d[n + 1] = false;
	for (int j = 0; j < q; ++j)
	{
		scanf("%lld", x + j);
	}
	for (int i = 0; i <= n; ++i)
	{
		if (d[i] && !d[i + 1])
		{
			talkp.push_back(mean(a[i], a[i + 1]));
		}
	}
	auto fritr = talkp.begin();
	auto bkitr = talkp.begin();

	for (int i = 0; i <= n; ++i)
	{
		place[i] = a[i];
		while (fritr != talkp.end() && (*fritr) < a[i])
		{
			bkitr = fritr;
			++fritr;
		}
		if (d[i])
		{
			ll dist = (*fritr) - a[i];
			if (dist < t)place[i] += dist;
			else place[i] += t;
		}
		else
		{
			ll dist = a[i] - (*bkitr);
			if (dist < t)place[i] -= dist;
			else place[i] -= t;
		}
	}
	for (int j = 0; j < q; ++j)
	{
		printf("%lld\n", place[x[j]]);
	}
	return 0;
}

Measured memory_bytes: 4492
import java.util.*;

class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        //入力値を設定する
        double numHP = sc.nextInt();
        double numAtk = sc.nextInt();
        
        Integer cnt = 0;
        cnt = (int)Math.ceil(numHP / numAtk);
        
        //出力する
        System.out.println(cnt);
    }    
}

Measured memory_bytes: 21844
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    while(true){
      int x = sc.nextInt();
      int y = sc.nextInt();
      if(x==0 && y==0){
        break;
      }
      if(x<y){
        System.out.println(x+" "+y);
      }else{
        System.out.println(y+" "+x);
      }
    }
  }
}



Measured memory_bytes: 36532
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main(void){
  /*  int r[1000],n,k;
    double rate=0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>r[i];
    }
    sort(r,r+n);
    for(int i=0;i<k;i++){
        if(rate<=r[n-k+i])
        rate=(rate+r[n-k+i])/2;
    }
    cout<<rate<<endl;
    */
    long long int a,b,ans;
    cin>>a>>b;
    ans=b;
    for(int i=0;i<a-1;i++){
        ans=ans*(b-1);
    }
    cout<<ans<<endl;
}

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

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

  int ans=1;
  for(int i=1; i<n; i++){
    bool fl=true;
    for(int j=0; j<i; j++){
      if(h[j]>h[i]){
        fl=false;
        break;
      }
    }
    if(fl)ans++;
  }

  cout<<ans<<endl;
}


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


int main(){
    long long A, B, C, D; cin >> A >> B >> C >> D;
    if (B < C || B < D) {
        cout << 0 << endl;
        return 0;
    }

    long long g = C / __gcd(C, D) * D;    
    long upper_count = B / C + B / D - B / g;
    long lower_count = (A - 1) / C + (A - 1) / D - (A - 1) / g;
 
    long long ans = B - A + 1 - upper_count + lower_count;
    cout << ans << endl;

    return 0;
}


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

using namespace std;
map <char, int> m;

int main(){
	m['A'] = 10;
	m['B'] = 11;
	m['C'] = 12;
	m['D'] = 13;
	m['E'] = 14;
	m['F'] = 15;
	char x, y;
	scanf("%c %c", &x, &y);
	if (m[x] < m[y]) printf("<\n");
	else if (m[x] == m[y]) printf("=\n");
	else if (m[x] > m[y]) printf(">\n");
	return 0;
}

Measured memory_bytes: 256
ALL = [*'a'..'z']
n = gets.to_i
Ss = Array.new(n) { gets.chomp }

tbl = Hash[ALL.map { |c| [c, 100] }]

n.times do |i|
  ALL.each do |c|
    tbl[c] = [tbl[c], Ss[i].count(c)].min
  end
end

ans = ALL.map { |c| c * tbl[c] }.join
puts ans


Measured memory_bytes: 1788
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long MOD = 1e9 + 7;
using namespace std;
typedef long long ll;

map<ll, int> mp;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> t(110000), x(110000), y(110000);
	t[0] = x[0] = y[0] = 0;
	for (int i = 0; i < n; i++) cin >> t[i + 1] >> x[i + 1] >> y[i + 1];
	bool can = true;
	for (int i = 0; i < n; i++) {
		int dt = t[i + 1] - t[i];
		int dist = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
		if (dt < dist) can = false;
		if (dist % 2 != dt % 2) can = false;
	}
	if (can) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 1536
def main():
    while True:
        try:
            a,b = map(int,input().split())
            c = a*b
            if a < b:
                a,b = b,a
            while a%b != 0:
                a,b = b,a%b
            print(b,c//b)
        except EOFError:
            exit()

if __name__ == '__main__':
    main()

Measured memory_bytes: 5592
#include <iostream>
#include <string>
#include <algorithm> 
#include <cstdlib>
#include <map>
#include <queue>
#include <vector>
#define ll long long
using namespace std;
int main(){
	string s;
	cin >> s;
	string t;
	t = "keyence";
	int cnt=0,cnt2=0;
	for(int i=0;i<s.size();i++){
		if(s[i]==t[i]){
			cnt++;
		}else{
			break;
		}
	}
	int j=0;
	for(int i=s.size()-1;i>=0;i--){
		if(s[i]==t[6-j]){
			cnt2++;
		}else{
			break;
		}
		j++;
	}
	if(cnt+cnt2>=7){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int n,m,tmp,cnt=0;
  vector <int> a,spread;
 
  cin>>n;
  for(int i=0;i<n;i++){ //input original
    cin>>tmp;
    a.push_back(tmp);
  }
  for(int i=0,tmp=1;tmp<=n;i++){ //make spread vector
    spread.insert(spread.begin(),tmp);
    tmp=3*tmp+1;
  }
  m=spread.size();
  cout<<m<<endl; //output spread amount
  for(int i=0;i<m-1;i++) cout<<spread[i]<<" ";
  cout<<spread[m-1]<<endl; //output all spread
  
  for(int k=0;k<m;k++){  //testing all spread
    for(int i=spread[k];i<n;i++){
      tmp=a[i];
      int j=i-spread[k];
      while(j>=0&&a[j]>tmp)
      {
        a[j+spread[k]]=a[j];
        j-=spread[k];
        cnt++;
      }
      a[j+spread[k]]=tmp;
    }
  }
  cout<<cnt<<endl; //output cnt&answer vector
  for(int i=0;i<n;i++) cout<<a[i]<<endl;
  return 0;
}

Measured memory_bytes: 6980
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using namespace std;
using ll = long long;
using Edge = pair<int,long long>;
using Graph = vector<vector<Edge>>;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
    int N,M;
    cin >> N >> M;
    vector<int> a(M),b(M),c(M);
    int d[N][N];
    rep(i,M){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
    }
    rep(i,N) rep(j,N){
        if(i == j) d[i][j] = 0;
        else d[i][j] = 1e9;
    }
    
    rep(i,M){
        d[a[i]][b[i]] = c[i];
        d[b[i]][a[i]] = c[i];
    }
    
    rep(k,N) rep(i,N) rep(j,N) d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
    
    int ans = M;
    rep(k,M){
        bool flag = false;
        rep(i,N) if(d[i][a[k]] + c[k] == d[i][b[k]]) flag = true;
        if(flag) ans--;
    }
    pr(ans);
}

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

void solve(std::string S) {
    if (S == "RRR") {
        cout << 3 << endl;
        return;
    }
    if (S == "RRS" || S == "SRR") {
        cout << 2 << endl;
        return;
    }
    if (S == "SSS") {
        cout << 0 << endl;
        return;
    }
    cout << 1 << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main() {
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3596
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,l = map(int, input().split())
    s = [input().rstrip() for _ in range(n)]
    s.sort()
    print(''.join(s))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = 99999999;
const ll linf = 999999999999999999;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
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; }

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////



int main(){
	int n,m,a,b,c;
	int d[100005] = {};
	string s;

	cin >> a  >> b;

	(a%3 == 0 || b%3==0 || (a+b)%3== 0)?P("Possible") :P("Impossible");
	return  0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
  
  public static void main(String[] abc) {
     Main answer = new Main();
     long solution = answer.solve();
     System.out.println(solution);
  }
  
  private long[] dp;
  
  private long solve() {
     Scanner sc = new Scanner(System.in);     
     int N = sc.nextInt();
     int M = sc.nextInt();
     Map<Integer, List<Integer>> graph = new HashMap<>();
     for(int i=0;i<M;i++) {
        int u = sc.nextInt();
        int v = sc.nextInt();
        List<Integer> children = graph.getOrDefault(u, new ArrayList<>());        
        children.add(v);
        graph.put(u, children);
     }
     long bestLen =0;
     dp = new long[1000000];
     Arrays.fill(dp, -1);
     for(int i=1;i<=N;i++) {
       bestLen = Math.max(bestLen, getBestLen(i, graph));
     }
     return bestLen;
  }
	  
  private long getBestLen(int u, Map<Integer, List<Integer>> graph) {
	 if (dp[u]!=-1) return dp[u];
     if (!graph.containsKey(u)){
        dp[u]=0;
        return dp[u];
     } else {
        long bestChildLen=0;
        for(int child: graph.get(u)){
         	 long currChildLen = getBestLen(child, graph);
             bestChildLen = Math.max(bestChildLen, currChildLen);
        }
		dp[u] = bestChildLen+1;
        return dp[u];
     }
  }
}


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

int main() {
  ll a,b,n;cin>>a>>b>>n;
  ll x = min(n, b-1);
  ll score = (ll)(a*x/b);
  cout<<score;
}


Measured memory_bytes: 3584
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> a, b;

int damage(int n, int h){
    int max_a, attack, hp;
    attack = 0;
    hp = h;
    sort(a.begin(), a.end());
    max_a = a[n-1];
    sort(b.begin(), b.end());
    for (int i=n-1; i>=0; --i){
        if(b[i] >= max_a){
            hp -= b[i];
            attack++;
        }
        // cout << hp << endl;
        if(hp <= 0 || b[i] < max_a){
            break;
        }
    }
    if(hp > 0){
        // cout << "l: " << hp << endl;
        attack += (hp / max_a) + ((hp % max_a == 0) ? 0 : 1);
    }
    return attack;
}

int main()
{
    int n, h;
    cin >> n >> h;
    a.resize(n);
    b.resize(n);
    for (int i=0; i<n; ++i){
        cin >> a[i] >> b[i];
    }
    cout << damage(n, h) << endl;
}


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

int main() {
	char a; cin >> a;
	if(a=='A') cout << 'T' << endl;
	else if(a=='T') cout << 'A' << endl;
	else if(a=='C') cout << 'G' << endl;
	else cout << 'C' << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int h,w;
	cin>>h>>w;
	char a[100+5][100+5];
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			cin>>a[i][j];
	for(int i=0;i<h;i++)
	{
		int flag=0;
		for(int j=0;j<w;j++)
		{
			if(a[i][j]=='#')
				flag=1;
		}
		if(flag==0)
			for(int j=0;j<w;j++)
				a[i][j]=1;
	}
	for(int i=0;i<w;i++)
	{
		int flag=0;
		for(int j=0;j<h;j++)
		{
			if(a[j][i]=='#')
				flag=1;
		}
		if(flag==0)
			for(int j=0;j<h;j++)
				a[j][i]=1;
	}
	for(int i=0;i<h;i++)
	{
		int flag=0;
		for(int j=0;j<w;j++)
		{
			if(a[i][j]!=1)
			{	
				flag=1;
				cout<<a[i][j];
			}
		}
		if(flag==1)
			cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long mp[100005],mp1[100005];
int main()
{
    long long t,n,m,i,j,k,x=0,y=0,z;
    cin>>n>>m;
    string ss="AC";
    for(i=1; i<=m; i++)
    {
        string s;
        long long aa;
        cin>>aa>>s;
        if(s==ss)
        {
            if(mp[aa]==0)
            {
                mp[aa]=1;
                x++;
            }
            else if(mp[aa]==-1)
            {
                mp[aa]=1;
                x++;
            }
            else{
                x=x;
            }
        }
        else
        {
            if(mp[aa]==0)
            {
                y++;
                mp[aa]=-1;
                mp1[aa]++;
            }
            else if(mp[aa]==-1)
            {
                mp1[aa]++;
                y++;
            }

        }

    }
    z=0;
    for(i=1;i<=n;i++){
        if(mp[i]==1){
            z=z+mp1[i];
        }
    }
    cout<<x<<" "<<z<<endl;
}


Measured memory_bytes: 1792
import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int[] ar, ss;
	int j, k, x, put, alo;
	while(sc.hasNext()){
put=0;alo=0;
	x = sc.nextInt();
	ar = new int[x];
	ss = new int[x];

	for(j=1; j<x; j++)
	    if(ar[j]==0){
		ss[put]=j+1;
		put++;
		for(k=j+1; k<x+1; k+=(j+1))
		    ar[k-1]=1;
	    }
	for(int pak=0; pak<x; pak++)
	    ar[pak]=0;
	for(int le=0; ss[le]!=0; le++)
	    ar[ss[le]-1] = 1;
	for(int pak=0; pak<x; pak++)
	    if(ar[pak]==1 && ar[x-pak-1]==1)
	   	alo++;
	System.out.println(alo);
    }
    }}

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

#define PI acos(-1)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define all(c) (c).begin(), (c).end()
#define TIMESTAMP fprintf(stderr, "Execution time: %.3lf s.\n", (double)clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair <int, int> pii;
typedef vector <vi> vvi;
typedef vector <pii> vpii;
typedef vector<string> vs;

const int INF = 10000500;
const int MAXN = 1e5 + 9;

int dd[105][105];
int init[105][105];
int n, m;
bool ok[100500];
map <pii, int> mp;
vi path;

void input() {                  
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) {
			dd[i][j] = INF;
			init[i][j] = INF;
			if(i == j) dd[i][j] = init[i][j] = 0;
		}
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		dd[u][v] = dd[v][u] = w;
		init[u][v] = init[v][u] = w;
		mp[ {u, v} ] = i;
		mp[ {v, u} ] = i;
	}
}

void solve() {
	for(int k = 0; k < n; k++) 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++) 
				if(dd[i][j] > dd[i][k] + dd[k][j]) 
					dd[i][j] = dd[i][k] + dd[k][j];
	for(int i = 0; i < n; i++) 
		for(int j = 0; j < n; j++) {
			if(i == j) continue; 
			for(int u = 0; u < n; u++) 
				for(int v = 0; v < n; v++) {
					if(u == v || init[u][v] == INF) continue;
					if(dd[i][j] == dd[i][u] + init[v][u] + dd[v][j]) ok[mp[ { u, v } ]] = 1;
					if(dd[i][j] == dd[i][v] + init[v][u] + dd[u][j]) ok[mp[ { u, v } ]] = 1;
				}
			}
	int ans = 0;
	for(int i = 0; i < m; i++) if(!ok[i]) ans++;
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);     
#ifdef LOCAL
	freopen("xxx.in", "r", stdin);
	freopen("xxx.out", "w", stdout);
#else
	//freopen("xxx.in", "r", stdin);
	//freopen("xxx.out", "w", stdout);
#endif	
	input();
	solve();
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<deque>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<int>> vvi;

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define REP(i, n)  for(int i=0; i<(int)(n); i++)
#define REPS(i, n)  for(int i=1; i<=(int)(n); i++)
#define PER(i, n) for(int i=(int)(n)-1; i>= 0; i--)
#define PERS(i, n)  for(int i=(int)(n); i>0; i--)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
#define RFOR(i, c)  for(__typeof((c).rbegin()) i=(c).rbegin(); i!=(c).end(); i++)
#define ALL(container)  (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) (container).size()
#define FILL0(n)  setfill('0') << right << setw(n)
#define mp(a, b)  make_pair(a, b)
#define toLower(c)  c+0x20
#define toUpper(c)  c-0x20
#define pb  push_back
#define eb  emplace_back

const int INF = 1e9;
const long long LLINF = 1e18;
const ll MOD = 1000000007;
const int MSIZE = 100007;
const double Pi = 3.14159265358979323146;

int main(){
  ll a, b, c, k; cin >> a >> b >> c >> k;
  ll ans = (k>=a ? a : k);
  k-=a;
  if(k>0){
    k-=b;
    if(k>0){
      ans -= k;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3632
def ok(l):
    # 長さlの連続部分列で重ならずに2回以上現れるものがある
    D = {}
    for i in range(n-l+1):
        h = hash(S[i:i+l])
        try:
            if D[h] + l <= i:
                return True
        except:
            D[h] = i
    return False


n = int(input())
S = input()
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)


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

const int Max = 1500;
int G[Max][Max], dp[Max][Max];
int H, W, LS;

int main()
{
    cin >> H >> W;
    LS = 0;
    for(int i=0; i<H; i++)
    {
        for(int j=0; j<W; j++)
        {
            cin >> G[i][j];
        }
    }
    for(int i=0; i<H; i++)
    {
        dp[i][0] = 1-G[i][0];
        LS = max(dp[i][0], LS);
    }
    for(int j=0; j<W; j++)
    {
        dp[0][j] = 1-G[0][j];
        LS = max(dp[0][j], LS);
    }

    for(int i=1; i<H; i++)
    {
        for(int j=1; j<W; j++)
        {
            if(G[i][j])
                dp[i][j] = 0;
            else
            {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
            }
            LS = max(LS, dp[i][j]);
        }
    }
    cout << LS*LS << endl;
    return 0;
}



Measured memory_bytes: 19504
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mp  make_pair
#define pb  push_back
#define rep(i,a,n) for(int i=a;i<n;i++)
void c_p_c(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
const int MAX=1e5+5;
vector<int> a[MAX];
bool visited[MAX];
int dis[MAX];
int b[MAX];
void dfs(int x){
    visited[x]=true;
    for(int i:a[x]){
        dis[i]=max(dis[i],dis[x]+1);
        --b[i];
        if(b[i]==0){
            dfs(i);
        }
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    rep(i,0,m){
        int x,y;
        cin>>x>>y;
        a[x].pb(y);
        ++b[y];
    }
    rep(i,1,n+1){
        if(!visited[i] and b[i]==0){
            dfs(i);
        }
    }
    int ans=0;
    rep(i,1,n+1){
        ans=max(ans,dis[i]);
    }
    cout<<ans<<endl;
}
int32_t main(){
    c_p_c();
    int t;
    t=1;
    //cin>>t;
    while(t--){
       solve(); 
    }
	return 0;
}


Measured memory_bytes: 15296
#include<iostream>
#include<cstdio>
#include<complex>
#include<cmath>

using namespace std;

typedef complex<double> xy_t;
double cross(xy_t a,xy_t b);

xy_t P[4];

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

  double x[4],y[4];
  
  for(int i=0;i<n;i++){
    cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> x[3] >> y[3];
    for(int j=0;j<4;j++){
      P[j]=xy_t(x[j],y[j]);
    }
    if(abs(cross(P[1]-P[0],P[3]-P[2]))<pow(10,-10)){
      cout << "YES" <<endl;
    }else{
      cout << "NO" <<endl;
    }
    
  }

  

}

double cross(xy_t a,xy_t b){return (conj(a)*b).imag();}
    

Measured memory_bytes: 1228
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 200010
#define x first
#define y second
using namespace std;
typedef long long ll;
pair<int,int> p[MAXN];
const double Pi=acos(-1);
int xl,yl,xr,yr;
int fx,fy;
int n;
int st[MAXN];
int main(){
	SF("%d%d%d%d",&xl,&yl,&xr,&yr);
	if(xl>xr)
		fx=-1;
	else
		fx=1;
	if(yl>yr)
		fy=-1;
	else
		fy=1;
	xl*=fx,xr*=fx,yl*=fy,yr*=fy;
	SF("%d",&n);
	for(int i=1;i<=n;i++){
		SF("%d%d",&p[i].x,&p[i].y);
		p[i].x*=fx;
		p[i].y*=fy;
		if(p[i].x<xl||p[i].x>xr||p[i].y<yl||p[i].y>yr){
			n--;
			i--;
			continue;
		}
	}
	sort(p+1,p+1+n);
	int top=0;
	for(int i=1;i<=n;i++){
		if(top==0||st[top]<p[i].y)
			st[++top]=p[i].y;
		else{
			int pos=lower_bound(st+1,st+1+top,p[i].y)-st;
			st[pos]=p[i].y;	
		}
	}
	double ans=(xr-xl)*100.0+(yr-yl)*100.0;
	ans=ans+(double)top*(Pi*5.0-20.0);
	if(top==min(xr-xl+1,yr-yl+1))
		ans+=Pi*5;
	PF("%.11lf",ans);
}

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r[] ={1,5,10,50,100,500};
		int t=0;
		for(int i=0;i<6;i++){
			t+=sc.nextInt()*r[i];
		}
		if(1000<=t){
			System.out.println("1");
		}else{
			System.out.println("0");
		}
	}
}

Measured memory_bytes: 26336
#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	int x=n;
	char s[n+1];
	scanf("%s", s);
	if (n%2==1) printf("No\n");
	else {
		n/=2;
		int flag=1;
		for (int i=0, j=n;i<n, j<x;i++, j++) {
			if (s[i]!=s[j]) {
				flag=0;
				break;
			}
		}
		if (flag) printf("Yes\n");
		else printf("No\n");
	}
}

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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define REP(i,n) for(int i=0; i < (n); ++i)
#define SIZE(c) (int) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
#define FWD(i,a,b) for (int i=(a); i<(b); ++i)
#define BCK(i,a,b) for (int i=(a); i>(b); --i)
#define PI 3.14159265358979311600
#define pb push_back
#define mp make_pair
#define st first
#define nd second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

typedef vector < int > VI;
typedef vector<ll> VL;

typedef long double K;

const int N = 100005;
const int M = 11;

int n, m, q;
vector<int> g[N];
int qd[N], qv[N], qc[N], d[N][M], result[N], dst[N], tm[N], timer;

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

	cin >> n >> m;
	REP(i, m) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	cin >> q;
	REP(i, q) {
		cin >> qv[i+1] >> qd[i+1] >> qc[i+1];
		--qv[i+1];
		d[qv[i+1]][qd[i+1]] = i+1;
	}

	for (int i = q; i >= 1; --i) {
		int v = qv[i];
		queue<pair<int,int>> que;
		que.push({v, qd[i]});
		while (!que.empty()) {
			int v = que.front().first;
			int s = que.front().second;
			que.pop();
			if (s > 0 && d[v][s-1] < d[v][s]) {
				d[v][s-1] = d[v][s];
				que.push({v, s-1});
			}
			for (auto& to : g[v]) {
				if (s > 0 && d[to][s-1] < d[v][s]) {
					d[to][s-1] = d[v][s];
					que.push({to, s-1});
				}
			}
		}
	}

	REP(i, n) {
		cout << qc[d[i][0]] << '\n';
	}

	return 0;
}

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

const int INF = 1 << 28;

struct Primal_Dual
{
  typedef pair< int, int > Pi;
 
  struct edge
  {
    int to, cap, cost, rev;
  };
  vector< vector< edge > > graph;
  vector< int > potential, min_cost, prevv, preve;
 
  Primal_Dual(int V):graph(V){}
 
  void add_edge(int from, int to, int cap, int cost)
  {
    graph[from].push_back((edge){to, cap, cost, (int)graph[to].size()});
    graph[to].push_back((edge){from, 0, -cost, (int)graph[from].size() - 1});
  }
 
  int min_cost_flow(int s,int t,int f)
  {
    
    int V = graph.size(), ret = 0;
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    potential.assign(V, 0);
    prevv.assign(V, -1);
    preve.assign(V, -1);

    while(f > 0){
      min_cost.assign(V, INF);

      que.push(Pi(0, s));
      min_cost[s] = 0;
      while(!que.empty()){
        Pi p = que.top(); que.pop();
        if(min_cost[p.second] < p.first) continue;
        for(int i = 0; i < graph[p.second].size(); i++){
          edge& e = graph[p.second][i];
          int nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];
          if(e.cap > 0 && min_cost[e.to] > nextCost){
            min_cost[e.to] = nextCost;
            prevv[e.to] = p.second, preve[e.to] = i;
            que.push(Pi(min_cost[e.to], e.to));

          }
        }
      }

      if(min_cost[t] == INF) return(ret);
      for(int v = 0; v < V; v++) potential[v] += min_cost[v];
      int addflow = f;
      for(int v = t; v != s; v = prevv[v]){
        addflow = min( addflow, graph[prevv[v]][preve[v]].cap);
      }
      f -= addflow;
      ret += addflow * potential[t];
      for(int v = t; v != s; v = prevv[v]){
        edge& e = graph[prevv[v]][preve[v]];
        e.cap -= addflow;
        graph[v][e.rev].cap += addflow;
      }
    }
    return(ret);
  }
};

int main()
{
  int N, A[1000], B[1000];
  cin >> N;
  vector< int > nums;
  for(int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    nums.push_back(A[i]);
    nums.push_back(B[i]);
  }
  sort(nums.begin(), nums.end());
  nums.erase(unique(nums.begin(), nums.end()), nums.end());
 
  int s = N + nums.size() + 1, g = s + 1;

  Primal_Dual MCF(g + 1);
  int ret = 0;
  for(int i = 0; i < N; i++) {
    A[i] = lower_bound(nums.begin(), nums.end(), A[i]) - nums.begin();
    B[i] = lower_bound(nums.begin(), nums.end(), B[i]) - nums.begin();
    MCF.add_edge(s, i, 1, 0);
    MCF.add_edge(i, N + A[i], 1, nums[A[i]]);
    MCF.add_edge(i, N + B[i], 1, nums[B[i]]);
    MCF.add_edge(i, N + nums.size(), 1, nums[A[i]] + nums[B[i]]);
    ret += nums[A[i]] + nums[B[i]];
  }

  for(int i = 0; i < nums.size(); i++) {
    MCF.add_edge(N + i, g, 1, 0);
  }

  MCF.add_edge(N + nums.size(), g, INF, 0);
  cout << ret - MCF.min_cost_flow(s, g, N) << endl;
}

Measured memory_bytes: 1664
use std::io;
//use std::collections::HashMap;
//use std::collections::BinaryHeap;
//use std::collections::HashSet;
//use std::mem; // mem::swap(&mut x,&mut y);
use std::cmp; // cmp::max,cmp::min

#[allow(dead_code)]
fn read_line() -> String{
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn read_charvec() -> Vec<char>{
    read_line().chars().collect()
}

#[allow(dead_code)]
fn read_ints() -> Vec<i64>{
    let s = read_line();
    let split:Vec<&str> = s.split(" ").collect();
    split.iter().map(|&x| x.to_string().parse().unwrap()).collect()
}

#[allow(dead_code)]
fn read_int() -> i64{
    read_ints()[0]
}

#[allow(dead_code)]
fn reverse(s: &String) -> String{
    s.chars().rev().collect::<String>()
}

#[allow(dead_code)]
fn read_lines(n:i64) -> Vec<String>{
    let mut xs = Vec::new();

    for _i in 0..n{
        xs.push(read_line());
    }

    xs
}

#[allow(dead_code)]
fn read_ints2(n:i64) -> Vec<i64>{
    read_lines(n).iter().map(|x| x.parse().unwrap()).collect()
}

//////////////////////////////////////////////////////////////////////



fn solve() -> bool{
    // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2012&lang=jp
    let e = read_int();
    let mut m = 10000000 as i64;
    if e == 0{
        return false;
    }

    for y in 0..1001 as i64{
        for z in 0..101 as i64{
            let x = e-y*y-z*z*z;
            if x < 0 {
                break;
            }

            m = cmp::min(m,x+y+z);
        }
    }
    println!("{}",m);
    return true;
}

fn main(){
    while solve(){};
}





/*
DOCS

///////////////// Vec /////////////////

let v = vec![0;2]; // [0,0]
let sum_x = xs.iter().fold(0,|s,i|s+i); // xs : Vec<i64>

s.chars().nth(i as usize).unwrap();

let xs : Vec<i32> = read_charvec().iter().map(|&c| 
    if c == 'A'{
        0
    }else if c == 'B'{
        1
    }else if c == 'X'{
        2
    }else{
        3
    }
).collect();

// search
let i = match xs.iter().find(|&&m| m==0){
    Some(_) => true,
    None => false,
};

///////////////// HashMap /////////////////

let mut h = HashMap::new();
let a = 5;
h.insert(a,true);
match h.get(&a){
    Some(v) => println!("{}",v),
    None    => println!("none"),
}

///////////////// swap /////////////////

let mut x = 5;
let mut y = 1;
mem::swap(&mut x,&mut y);

///////////////// priority queue /////////////////

// https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
let mut heap = BinaryHeap::new();

heap.push(1);
heap.push(5);
heap.push(2);

assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);

let mut vs = heap.into_vec();
vs.reverse();

*/



Measured memory_bytes: 5048
N, M = map(int, input().split())
A = list(map(int, input().split()))

from math import gcd
def lcm(x, y):
    return x * y // gcd(x, y)

def f(n):
    cnt = 0
    while n:
        if n % 2 == 0:
            n //= 2
            cnt += 1
        else:
            break
    return cnt

l = A[0]//2
cnt = f(l)

for k in range(1, N):
    a = A[k]//2
    c = f(a)
    if cnt != c:
        print(0)
        exit()
    l = lcm(l, a)

print((M // l + 1) // 2)


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

const int MAXN = 200010;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
std::vector<int> ws[MAXN];
int n, cnt[MAXN], X, Y;
int fac[MAXN], inv[MAXN];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i != MAXN; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = mul(inv[mod % i], mod - mod / i);
	}
	for (int i = 2; i != MAXN; ++i)
		inv[i] = mul(inv[i - 1], inv[i]);
	std::cin >> n >> X >> Y;
	for (int i = 1, w, c; i <= n; ++i)
		std::cin >> c >> w, ws[c].push_back(w);
	int atv = INF, sev = INF;
	for (int i = 1; i <= n; ++i) if (!ws[i].empty()) {
		std::sort(ws[i].begin(), ws[i].end());
		int v = *ws[i].begin();
		if (v < atv) sev = atv, atv = v;
		else sev = std::min(sev, v);
	}
	for (int i = 1; i <= n; ++i) if (!ws[i].empty()) {
		int v = *ws[i].begin(), ouv = v == atv ? sev : atv;
		if (ouv <= Y - v)
			for (auto t : ws[i]) cnt[i] += t + v <= X || t + ouv <= Y;
	}
	int ans = fac[std::accumulate(cnt + 1, cnt + 1 + n, 0)];
	for (int i = 1; i <= n; ++i) ans = mul(ans, inv[cnt[i]]);
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 11648
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    int rev;     // 無向グラフの対の辺
    Edge(int from, int to, Weight weight) :
        from(from), to(to), weight(weight) { }
    Edge(int from, int to, Weight weight, int rev) :
        from(from), to(to), weight(weight), rev(rev){ }
};
bool operator < (const Edge &a, const Edge &b){
    if(a.weight != b.weight) return a.weight > b.weight;
    if(a.from != b.from) return a.from > b.from;
    return  a.to > b.to;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void addFlowEdge(Graph &g, int a, int b, Weight c){
    g[a].push_back(Edge(a, b, c, g[b].size()));
    g[b].push_back(Edge(b, a, 0, g[a].size() - 1));
}
void addUndirectedEdge(Graph &g, int a, int b, Weight c){
    g[a].push_back(Edge(a, b, c, g[b].size()));
    g[b].push_back(Edge(b, a, c, g[a].size() - 1));
}
const int INF = (int)1e+15;
void dijkstra(const Graph &g, int s, vector<Weight> &dist, vector<int> &prev){
    int n = g.size();
    dist.assign(n, INF);
    dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> Q;     // a < b <-> a.weight > b.weight
    Q.push(Edge(-2, s, 0));
    while(!Q.empty()){
        Edge e = Q.top(); Q.pop();
        if(prev[e.to] != -1) continue;
        prev[e.to] = e.from;
        EACH(i, g[e.to]){
        //for(Edges::const_iterator i=g[e.to].begin(); i!=g[e.to].end(); ++i){    //マクロが使えないとき
            if(dist[i -> to] > dist[i -> from] + i -> weight){
                dist[i -> to] = dist[i -> from] + i -> weight;
                Q.push(Edge(i -> from, i -> to, dist[i -> to]));
            }
        }
    }
}
vector<int> buildPath(const vector<int> &prev, int t){
    vector<int> path;
    for(int v = t; v >= 0; v = prev[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

void solve(long long K){
    Graph g(K);
    for(int i = 0; i < K; ++i) {
        g[i].push_back(Edge(i, (i + 1) % K, 1));
        g[i].push_back(Edge(i, (i * 10) % K, 0));
    }
    vector<int> dist, prev;
    dijkstra(g, 1, dist, prev);
    cout << dist[0] + 1 << endl;
}

signed main(){
    long long K;
    scanf("%lld",&K);
    solve(K);
    return 0;
}

Measured memory_bytes: 14200
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
T=[a,b,c,d,e]
A=list(map(lambda x:x%10,T))
S=list(map(lambda y:y//10,T))
count=0
B=[]
for j in range(5):
    if A[j]!=0:
        count+=1
        B.append(A[j])
if len(B)==0:
    print(10*(sum(S)+count))
else:
    print(10*(sum(S)+count-1)+min(B)) 

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    if(n % 10 == 9 || n / 10 == 9) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
 
  }
}


Measured memory_bytes: 21460
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
#define N 200005
#define pii pair<int, int>
using namespace std;

int n, m, a[N], b[N];

inline int check(int mid) {
    for (int i = 1; i <= mid; ++i) b[i] = a[i];
    for (int i = mid + 1; i <= n + n; ++i) b[i] = a[i] - m;
    sort(b + 1, b + n + n + 1);
    int res = 0, ok = 1;
    for (int i = 1, tmp; i <= n && ok; ++i) {
        if ((tmp = b[i] + b[n + n - i + 1]) < 0) ok = 0;
        res = max(res, tmp);
    }
    if (!ok) return -1;
    else return res;
}

int main() {
#ifdef whyqx
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif

    cin >> n >> m;
    for (int i = 1; i <= n + n; ++i)
        scanf("%d", a + i);

    sort(a + 1, a + n + n + 1);

    int l = 0, r = n * 2, res = n * 2;

    while (l <= r) {
        int mid = (l + r) >> 1;
        if (~~~check(mid)) r = (res = mid) - 1;
        else l = mid + 1;
    }

    cout << check(res) << endl;

    return 0;
}


Measured memory_bytes: 1920
import numpy as np

N, D = map(int, input().split())

X = []

for i in range(N):
    X.append([int(i) for i in list(input().split())])

res = 0
X = np.array(X)
for i in range(N):
    for j in range(i + 1, N):
        if np.linalg.norm(X[i] - X[j]).is_integer():
            res += 1

print(res)

Measured memory_bytes: 12504
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main(){
  int s, w;
  cin >> s >> w;
  if(s > w) cout << "safe\n";
  else cout << "unsafe\n";
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;


int main(){
	int n, m;
	cin >> n >> m;
	vector<pair<ll, ll> > vec(n);
	for (int i = 0; i < n; i++){
		cin >> vec[i].first >> vec[i].second; 
	}
	sort(vec.begin(), vec.end());
	int now = 0;
	ll ans = 0;
	for (int i = 0; i < n; i++){
		if (vec[i].second + now < m){
			now += vec[i].second;
			ans += vec[i].first*vec[i].second;
		}else{
			ans += vec[i].first*(m-now);
			break;
		}
	}
	cout << ans << endl;
	return 0;
 }



Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <limits.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<lint> vl;
typedef pair<lint,lint> pll;


int main()
{
    ios_base::sync_with_stdio(0);    cin.tie(NULL);    cout.tie(NULL);
    
    
    int a, b; cin>>a>>b;
    cout<<a*b;

}


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

int main(){
 	string a;
  	cin >> a;
  	if(a[6] <= '4' && a[5] != '1'){
    	cout << "Heisei" << endl;
    } else {
      	cout << "TBD" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,a) for(int i = 0; i < (a); i++)
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

int par[200010],r1[200010],par2[200010],r2[200010];

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

void uf(int x,int y){
    x = find(x);
    y = find(y);
    if (x==y) return;
    if(r1[x]<r1[y]) par[x] = y;
    else {
        par[y]=x;
        if(r1[x]==r1[y]) r1[x]++;
    }
}

int find2(int x){
    if(par2[x]==x) return x;
    return par2[x]=find2(par2[x]);
}

void uf2(int x,int y){
    x = find2(x);
    y = find2(y);
    if (x==y) return;
    if(r2[x]<r2[y]) par2[x] = y;
    else {
        par2[y]=x;
        if(r2[x]==r2[y]) r2[x]++;
    }
}

int main(){
    int n,k,l,p,q,r,s;
    cin>>n>>k>>l;
    for(int i=0;i<200005;i++){ par[i]=i; r1[i]=0; par2[i]=i; r2[i]=0;}
    for(int i=0;i<k;i++){ cin>>p>>q; p--; q--; uf(p,q);}
    for(int i=0;i<l;i++){ cin>>r>>s; r--; s--; uf2(r,s);}
    map<pair<int ,int>, int> V;
    for(int i=0;i<n;i++) V[make_pair(find(i),find2(i))]++;
    for(int i=0;i<n;i++) cout<<V[make_pair(find(i),find2(i))]<<' ';
    cout<<endl;
    return 0;
}

Measured memory_bytes: 15232
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int k,x;
  cin >> k >> x;
  if(500 * k >= x) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
ll strtoint(string str);
int main(){
	fast;
	string s,t; cin>>s>>t;
	cout<<t+s<<'\n';
	return 0;
}
ll strtoint(string str){
	ll x=0;
	stringstream ss;
	ss<<str;
	ss>>x;
	return x;
}

Measured memory_bytes: 256
n = int(input())
CSF = []
for i in range(n-1):
  CSF.append(list(map(int, input().split())))
for i in range(n-1):
  s = CSF[i][1]
  for j in range(i,n-1):
    s += CSF[j][0]
    if j < n-2:
      if s < CSF[j+1][1]:
        s = CSF[j+1][1]
      if s%CSF[j+1][2] != 0:
        s = (s//CSF[j+1][2]+1) * CSF[j+1][2]
  print(s)
print(0)


Measured memory_bytes: 3188