akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;

int main(){
  int n, k;
  cin >> n >> k;
  if((n-1) *(n-2) /2 < k){
    cout << -1 << endl;
    return 0;
  }
  int mx = (n-1) *(n-2) /2;
  vector<P> ans(0);
  for(int i=2; i<=n; ++i){
    ans.push_back(P(1,i));
  }
  for(int i=2; i<n; ++i) for(int j=i+1; j<=n; ++j){
    if(mx > k){
      ans.push_back(P(i,j));
      --mx;
    }else break;
  }
  
  cout << ans.size() << endl;
  for(auto pi: ans){
    printf("%d %d\n",pi.first,pi.second);
  }
}

Measured memory_bytes: 384
object Main extends App {
  val in = scala.io.Source.stdin.getLines().toIndexedSeq
  .map(_.split(' ').map(_.toLong))
  val in0 = in.head
  val N = in0(0)
  val P = in0(1)
  
if(N == 1L) println(P) else
  {  
  var x = 1L
  var cont = false
  var ret = 1L
  do {
    x += 1L
    //val xN = (1L to N).foldLeft(1L)( (a, _) => a * x )
    val xN:Long = Math.pow(x, N).toLong
    /*
    var xN = 1L
    var j = 0L
    while(j < N){
      xN *= x
      j += 1L
    }
    */
    if(P % xN == 0L) ret = x
    cont = xN <= P
  } while(cont)
  println(ret)
  }
}


Measured memory_bytes: 25532
def solve():
    N, K = map(int, input().split())
    count = 0
    is_k_even = K%2 == 0
    # half_k_mod = []
    half_k_mod = 0
    # k_mod = []
    k_mod = 0
    for i in range(1, N+1):
        if (i % K) == 0:
            # k_mod.append(i)
            k_mod += 1
        elif is_k_even and (i % K) == K//2:
            # half_k_mod.append(i)
            half_k_mod += 1
    
    count = k_mod ** 3 + half_k_mod ** 3
    print(count)
    
solve()

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

int main() {
  int N;
  int T;
  int A;
  cin >> N >> T >> A;
  vector<int> H(N);
  for(int i=0;i<N;i++) {
    cin >> H[i];
  }

  double min = 10000000;
  int ans = N+1;
  for(int i=0;i<N;i++) {
    double tem = T - H[i] * 0.006;
    if(abs(tem - A) < min) {
      min = abs(tem - A);
      ans = i+1;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int n, i, j, a[101], key, k;

    scanf("%d", &n);
    for(i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    for(k=0;k<n-1;k++)printf("%d ", a[k]);
    printf("%d\n", a[k]);
    for(i=1;i<n;i++){
        key = a[i];
        j=i-1;
        while(j>=0 && a[j]>key){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
        for(k=0;k<n-1;k++)printf("%d ", a[k]);
        printf("%d\n", a[k]);
    }

return 0;
}



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





int main(){
    ll N; cin >> N;
    vector<long double> P(N); for(int i = 0; i < N; i++) cin >> P[i];
    vector<vector<long double>> DP(N+2, vector<long double>(N+1));
    DP[1][0] = 1.0;
    for(int i = 1; i <= N+1; i++){
        for(int j = 1; j <= N; j++){
            DP[i][j] = DP[i-1][j-1]*P[j-1] + DP[i][j-1]*(1.0-P[j-1]);
        }
    }
    long double ans = 0;
    for(int i = N/2+1; i <= N; i++){
        ans += DP[i+1][N];
    }
    cout <<setprecision(20)<<  ans << endl;


}


Measured memory_bytes: 141184
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i, n) for(ll i=0;i<n;i++)
#define revf(i,n) for(ll i=n-1;i>=0;i-=2)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep1(i,b) for(ll i=1;i<=b;i++)
#define inp(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define outp(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" "
#define outp1(a,n) for(ll i=1;i<n;i++)cout<<a[i]<<" "
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (((a)*(b))/gcd((a),(b)))
#define pb push_back
#define mp make_pair
#define mem(x,n) memset(x,n,sizeof(x))
#define BINSC binary_search
#define BITOUT __builtin_popcount
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define cn cout<<"\n";
int main()
{
       ll n;
        cin>>n;
        ll ar[n];
        inp(ar,n);
        ll out=0;
        set<string>s;
        forr(i,n-2)
        {
             REP(j,i+1,n-1)
             {
                  REP(k,j+1,n)
                  {
                       
                       if(ar[i]!=ar[j]&&ar[j]!=ar[k]&&ar[i]!=ar[k])
                       {
                            if(ar[i]+ar[j]>ar[k]&&ar[i]+ar[k]>ar[j]&&ar[k]+ar[j]>ar[i])
                            out++;
                       }
                  }
             }
        }
        cout<<out;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 2e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(x), b(y), c(z);
    rep(i, 0, x) cin >> a[i];
    rep(i, 0, y) cin >> b[i];
    rep(i, 0, z) cin >> c[i];

    sort(all(a), greater<ll>());
    sort(all(b), greater<ll>());
    sort(all(c), greater<ll>());

    priority_queue<tuple<ll, int, int, int>> pq;
    pq.push(make_tuple(a[0] + b[0] + c[0], 0, 0, 0));
    set<tuple<int, int, int>> used;
    used.insert(make_tuple(0, 0, 0));
    vector<ll> ans;

    while ((int)ans.size() < k) {
        ans.push_back(get<0>(pq.top()));
        int A = get<1>(pq.top());
        int B = get<2>(pq.top());
        int C = get<3>(pq.top());
        pq.pop();

        if (A < x - 1) {
            if (!used.count(make_tuple(A + 1, B, C))) {
                pq.push(make_tuple(a[A + 1] + b[B] + c[C], A + 1, B, C));
                used.insert(make_tuple(A + 1, B, C));
            }
        }

        if (B < y - 1) {
            if (!used.count(make_tuple(A, B + 1, C))) {
                pq.push(make_tuple(a[A] + b[B + 1] + c[C], A, B + 1, C));
                used.insert(make_tuple(A, B + 1, C));
            }
        }

        if (C < z - 1) {
            if (!used.count(make_tuple(A, B, C + 1))) {
                pq.push(make_tuple(a[A] + b[B] + c[C + 1], A, B, C + 1));
                used.insert(make_tuple(A, B, C + 1));
            }
        }
    }

    sort(all(ans), greater<ll>());
    rep(i, 0, k) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 1024
import math
MOD = 10**9+7


def dist(a, b):
    dx = a[0]-b[0]
    dy = a[1]-b[1]
    return math.sqrt(dx * dx + dy * dy)


def max_dist(p, x, y):
    result = 0
    for i in range(len(p)):
        result = max(result, dist((x, y), p[i]))
    return result


def ternary_search2(p, x):
    l = 0
    r = 1000
    for i in range(100):
        c1 = (l*2+r)/3
        c2 = (l+r*2)/3
        if(max_dist(p, x, c1) > max_dist(p, x, c2)):
            l = c1
        else:
            r = c2
    return max_dist(p, x, l)


def ternary_search1(p):
    l = 0
    r = 1000
    for i in range(100):
        c1 = (l*2+r)/3
        c2 = (l+r*2)/3
        if(ternary_search2(p, c1) > ternary_search2(p, c2)):
            l = c1
        else:
            r = c2

    return ternary_search2(p, l)


def main():
    n = int(input())
    p = []
    for i in range(n):
        p.append(list(map(int, input().split())))

    print(ternary_search1(p))


main()


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>
#include <bitset>
#include <limits>

using namespace std;

#define ll long long

int main(void){
    int x;
    cin >> x;

    if(x < 600){
        cout << '8' << endl;
    }else if(x < 800){
        cout << '7' << endl;
    }else if(x < 1000){
        cout << '6' << endl;
    }else if(x < 1200){
        cout << '5' << endl;
    }else if(x < 1400){
        cout << '4' << endl;
    }else if(x < 1600){
        cout << '3' << endl;
    }else if(x < 1800){
        cout << '2' << endl;
    }else{
        cout << '1' << endl;
    }

    return 0;
}

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

typedef pair<int,int> P;

bool comp(const P& a, const P& b) {
	if (a.first != b.first) return (a.first > b.first);
	return (a.second < b.second);
}

int main() {
	P place[100];
	int n, m;
	while (cin >> n >> m, n||m) {
		for (int i = 0; i < m; i++) {
			place[i].first = 0;
			place[i].second = i+1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int k; cin >> k;
				place[j].first += k;
			}
		}
		
		sort(place, place+m, comp);
		
		cout << place[0].second;
		for (int i = 1; i < m; i++)
			cout << " " << place[i].second;
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	int a = 0, b = 0;
	for(int i = 0; i < n; i ++)
	{
		int x;
		cin >> x;
		if(x % 4 == 2)
		{
			a ++;
		}
		if(x % 4 == 0)
		{
			b ++;
		}
	}
	if(a + b * 2 >= n || b * 2 == n - 1)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <cctype>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <queue>
#include <stdio.h>
#include <stack>
#include <ctime>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define TR(i,x) for(__typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define ALL(x) x.begin(),x.end()
#define SORT(x) sort(ALL(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))
#define PB push_back
#define MP make_pair

using namespace std;

const double eps = 1e-8;

typedef map<int,int> MII;
typedef map<string,int> MSI;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<long double> VD;
typedef pair<int,int> PII;
typedef long long int64;
typedef long long LL;
typedef unsigned int UI;
typedef long double LD;

int main() {
    LL n;
    LL ans = 0;
    cin >> n;
    for (LL i = 1; i <= n; ++i) {
        if ((i % 3 == 0) && (i % 5 == 0)) {
            continue;
        } else if (i % 3 == 0) {
            continue;
        } else if (i % 5 == 0) {
            continue;
        } else {
            ans += i;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
import java.util.HashSet;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Comparator;
import java.util.Set;
import java.util.HashMap;

public class Main {
    // 標準入力
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 標準入力数値配列用 int
    static int[] inputval() throws Exception {
        String[] strarray = br.readLine().trim().split(" ");
        int[] intarray = new int[strarray.length];
        for (int i = 0; i < intarray.length; i++) {
            intarray[i] = Integer.parseInt(strarray[i]);
        }
        return intarray;
    }

    // 標準入力数値リスト用 int
    static List<Integer> inputIntList() throws Exception {
        List<String> strList = Arrays.asList(br.readLine().trim().split(" "));
        List<Integer> intList = new ArrayList<Integer>();
        for (String elem : strList){
            intList.add(Integer.parseInt(elem));
        }
        return intList;
    }

    // 標準入力数値配列用 integer 降順ソート用
    static Integer[] inputvalInteger() throws Exception {
        String[] strarray = br.readLine().trim().split(" ");
        Integer[] intarray = new Integer[strarray.length];
        for (int i = 0; i < intarray.length; i++) {
            intarray[i] = Integer.parseInt(strarray[i]);
        }
        return intarray;
    }

    public static void main(String[] args) throws Exception {
        // write your code here
        int n = Integer.parseInt(br.readLine());
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        for(int i=0; i<n; i++){
            String line = br.readLine().trim();
            if (map.get(line) == null){
                map.put(line,1);
            }else{
                map.replace(line,map.get(line)+1);
            }
        }
        int m = Integer.parseInt(br.readLine());
        for(int i=0; i<m; i++){
            String line = br.readLine().trim();
            if (map.get(line) != null){
                map.replace(line,map.get(line)-1);
            }
        }
        int max = map.values().stream().max(Integer::compare).get();
        System.out.println(Math.max(max, 0));

    }

}



Measured memory_bytes: 33984
#include <iostream>
#include <cstdio>
#include <string>
#define INF 1e9
#define eps 1e-6
typedef long long ll;
using namespace std;

ll t, n, k, cnt1, cnt2, ans;
string a, b;
bool bb;

int main(){

	cin >> a >> k;
	n = a.size();
	cnt1 = cnt2 = ans = 0;
	b = a + a;
	bb = false;
	n = a.size();
	for(int i = 1; i < a.size(); i++)
		if(a[i] != a[0])
			bb = true;
	if(!bb){
		printf("%lld\n", n * k / 2);
		return 0;
	}
	for(int i = 1; i < a.size(); i++)
		if(a[i] == a[i - 1])
			a[i] = 'A', cnt1++;
	for(int i = 1; i < b.size(); i++)
		if(b[i] == b[i - 1])
			b[i] = 'B', cnt2++;
	ans = cnt1 + (cnt2 - cnt1) * (k - 1);
	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>

typedef long long ll;

int n,k,i,w[100000];

bool checkP(int p){
  int idx=0;
  ll sum;
  for (i = 0; i < k; ++i) {
    sum=0;

    while (sum+w[idx]<=p) {
        sum+=w[idx];
        ++idx;
        if (idx==n){
          return true;
        }
    }
  }
  return false;
}

int main() {
  ll r=0,l,mid;
  std::cin >> n>>k;
  for (i = 0; i < n; ++i) {std::cin >>w[i];}
  for (i = 0; i < n; ++i) {r+=w[i];}
  l=(r+k-1)/k;
  while(l<=r){
    mid=(r+l)/2;
    if (checkP(mid)){
      r=mid-1;
    }else{
      l=mid+1;
    }

  };
  std::cout << r+1<< '\n';
}



Measured memory_bytes: 3504
#include "bits/stdc++.h"
using namespace std;
int main()
{
    int n, k, test = 0;
    char c[7];
    list<int> li;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", c);
        test++;
        if (c[0] == 'i')
        {
            scanf("%d", &k);
            li.push_front(k);
        }
        else if(c[0] == 'd')
        {
            if (c[6] == 'F')
            {
                li.pop_front();
            }
            else if (c[6] == 'L')
            {
                li.pop_back();
            }
            else
            {
                scanf("%d", &k);
                auto ite = find(li.begin(), li.end(), k);
                if (ite != li.end())
                {
                    li.erase(ite);
                }
            }
        }
    }
    
    bool a = false;
    for (auto i = li.begin(); i != li.end(); i++)
    {
        if (a)
        {
            printf(" ");
        }
        a = true;
        printf("%d", *i);
    }
    printf("\n");
}


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

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    vector<vector<ll>> a(2, vector<ll>(n));
    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a.at(i).at(j);
        }
    }
    vector<vector<ll>> cs(2, vector<ll>(n, 0));
    cs.at(0).at(0) = a.at(0).at(0);
    for(int i = 1; i < n; ++i){
        cs.at(0).at(i) = cs.at(0).at(i - 1) + a.at(0).at(i);
    }
    cs.at(1).at(n - 1) = a.at(1).at(n - 1);
    for(int i = n - 2; i >= 0; --i){
        cs.at(1).at(i) = cs.at(1).at(i + 1) + a.at(1).at(i);
    }
    
    ll ans = 0;
    for(int i = 0; i < n; ++i){
        ans = max(ans, cs.at(0).at(i) + cs.at(1).at(i));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define tarce(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define pb push_back
#define inf 2e18
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define mem(a,v) memset(a,v,sizeof(a))
#define pii pair<int,int>
#define mkp make_pair
using namespace std;
#define N 200005


int32_t main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        
       int n;
       cin >> n;
       map<int,int>mp;
       int a[n+1],i,j;
       for(i=1; i<=n; i++)cin >> a[i];
    int m=0;
    mp[0]=0;
       for(i=1; i<=n; i++){
           if(mp.find(a[i]-1)!=mp.end()){
           mp[a[i]]=mp[a[i]-1]+1;
           m=max(m,mp[a[i]]);
           }
       }
       if(m==0) cout << -1;
       else
       cout << n-m << '\n';
        

}

Measured memory_bytes: 14336
#pragma GCC optimize("O2")

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

#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)
#define endl "\n"
#define max(a, b) (a < b ? b : a)
#define min(a, b) ((a > b) ? b : a)
typedef long long ll;
#define mk(arr, n, type) type *arr = new type[n]
const int mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

#define watch(x) cout << (#x) << " is : " << (x) << "\n"
#define watch2(x, y) cout << (#x) << " is " << (x) << " and " << (#y) << " is " << (y) << "\n"

void b_v_r()
{
    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
}

int main()
{
    b_v_r();

    ll n,i;
    cin >> n;
    string s;
    cin >> s;
    ll swap = 0LL;
    // RRRRRR ... WWWWWWW ... 
    ll left = 0LL, right = n-1;
    while(left < right)
    {
        if(s[left] == 'W')
        {
            if(s[right] == 'R')
            {
                swap++;
                left++;
                right--;
            }
            else
            {
                right--;
            }
        }
        else
        {
            left++;
        }
    }

    cout << swap << endl;
    
    return 0;
}


Measured memory_bytes: 3788
board=[]
visited=[[0, 0, 0],[0, 0, 0],[0, 0, 0]]
for i in range(3):
  board.append(list(map(int, input().split())))
N = int(input())

for _ in range(N):
  X = int(input())
  for i in range(3):
    for j in range(3):
      if board[i][j]==X:
        visited[i][j] = 1

check=False
for i in range(3):
  rows = 0
  cols = 0
  for j in range(3):
    rows+=visited[i][j]
    cols+=visited[j][i]
  if rows==3 or cols==3:
    check=True

rows = 0
for i in range(3):
  rows += visited[i][i]
if rows==3:
  check=True
rows = 0
cols = 0
for i in range(3):
  rows += visited[i][2-i]
  cols += visited[2-i][i]
if rows==3 or cols==3:
  check=True

if check:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 3188
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    sc.close();

    int count = 0;
    for (int i = 0; i < N-2; i++) {
      if (S.substring(i, i+3).equals("ABC")) {
        count++;
      }
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 21972
# dpC - Vacation
# 3 variables
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    a, b, c = A[0]
    for x, y, z in A[1:]:
        a, b, c = x + max(b, c), y + max(a, c), z + max(a, b)
    print(max(a, b, c))


if __name__ == "__main__":
    main()

Measured memory_bytes: 21308
s = list(str(input()))

if len(set(s)) == 1:
    print(0)
    exit()

import copy
ans = 101
for i in range(26):
    c = chr(i+ord('a'))
    t = copy.copy(s)
    cnt = 0
    while True:
        temp = []
        cnt += 1
        for j in range(len(t)-1):
            if t[j] == c:
                temp.append(t[j])
            elif t[j+1] == c:
                temp.append(t[j+1])
            else:
                temp.append(t[j])
        t = copy.copy(temp)
        if len(set(t)) == 1:
            break
    ans = min(ans, cnt)
print(ans)


Measured memory_bytes: 74972
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = 0
for i in A:
    ans += B[i - 1]

for i in range(N - 1):
    if A[i + 1] == A [i] + 1:
        ans += C[A[i] - 1]

print(ans)
    
    


Measured memory_bytes: 9176
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	N := nextInt()
	if N == 1 {
		fmt.Println("Yes")
		return
	}
	prev := nextInt()
	for i := 1; i < N; i++ {
		cur := nextInt()
		if prev > cur {
			if i != 1 || (i == 1 && prev-cur > 1) {
				fmt.Println("No")
				return
			}
		} else if prev < cur {
			cur--
		}
		prev = cur
	}
	fmt.Println("Yes")
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -a
	}
}

func pow(p, q int) int {
	res := p
	if q == 0 {
		return 1
	}
	for i := 0; i < q-1; i++ {
		res *= p
	}
	return res
}

func MinOf(vars ...int) int {
	min := vars[0]
	for _, i := range vars {
		if min > i {
			min = i
		}
	}
	return min
}

func MaxOf(vars ...int) int {
	max := vars[0]
	for _, i := range vars {
		if max < i {
			max = i
		}
	}
	return max
}

func gcdof2numbers(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcdof2numbers(b, a%b)
}

func lcmof2numbers(a int, b int) int {
	return a / gcdof2numbers(a, b) * b
}

// マイナスの場合は考慮していない
func fuctorial(a int) int {
	if a == 1 || a == 0 {
		return 1
	} else {
		return fuctorial(a-1) * a
	}
}

func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// 素因数分解したmapを返す
func primeFuctorize(n int) map[int]int {
	pf := map[int]int{}
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			pf[i]++
			n /= i
		}
	}
	if n != 1 {
		pf[n]++
	}
	return pf
}


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


int main(){
  ll N, i, count = 0;
  vector<ll> A(200000), box(200000, 0);
  cin >> N;
  rep(i, N){
    cin >> A[i];
    box[A[i] - 1]++;
  }
  rep(i, N){
    if(box[i] > 0){
      count += box[i]*(box[i] - 1)/2;
    }
  }
  rep(i, N){
    cout << count - box[A[i] - 1] + 1 << endl;
  }
  
  return 0;
}

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

const int INF = 1<<25;
int main() {
	int t, d, ta, tb, da, db;
	cin >> t >> d >> ta >> tb >> da >> db;
	double ans = INF;
	for(int i = 0; da * i <= d; ++i){
		for(int j = 0; db * j <= d; ++j){
			if(da * i + db * j <= d){
				double temp = (ta * (da * i) + tb * (db * j)) / double((da * i) + (db * j));
				ans = min(ans, abs(t - temp));
			}
		}
	}
	cout << fixed << ans << endl;
	return 0;
}

Measured memory_bytes: 1240
import math
from functools import reduce
import itertools
A,B,C,K = map(int,input().split())

count=0
if A>=K:
    ans=K
else:
    count+=A
    if A+B>=K:
        ans=A

    else:
        count-=(K-(A+B))
        ans=count

print(ans)


Measured memory_bytes: 9572
#include <stdio.h>
#include <string.h>
typedef long long ll;

int len;
char str[200010];
ll dp[200005];
ll sum;

int solve(int idx);

int main()
{
    for (int i = 0; i < 200005; i++) {
        dp[i] = -1;
    }
    
    scanf("%s", str);
    len = strlen(str);

    for (int i = len - 1; i >= 0; i--) {
        if (str[i] == 'A') {
            dp[i] = solve(i + 1);
            sum += dp[i];
        }
    }

    printf("%lld\n", sum);

    return 0;
}

int solve(int idx)
{
    if (dp[idx] != -1) {
        return dp[idx];
    }
    if (!(str[idx] == 'B' && str[idx + 1] == 'C')) {
        return 0;
    }

    return dp[idx] = solve(idx + 2) + 1;
}


Measured memory_bytes: 2944
#include <stdio.h>
#include <stdlib.h>
long gcd(long x,long y)
{
    if(x<y)
    {
        x+=y;
        y=x-y;
        x-=y;
    }
    long a,b,c;
    a=y,b=x%y;
    while(b!=0)
    {
        c=a;
        a=b;
        b=c%a;
    }
    return a;
}
int main()
{
    long a,b;
    scanf("%ld %ld",&a,&b);
    printf("%ld\n",a*b/gcd(a,b));
    return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int n,i,a[1000],q,k,b,e,cnt,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)	scanf("%d",&a[i]);
	scanf("%d",&q);
	for(i=0;i<q;i++)	{
		scanf("%d %d",&b,&e);
		e--;
		while(b<e)	{
			swap(a[b],a[e]);
			b++;	e--;
		}
	}
	printf("%d",a[0]);
	for(i=1;i<n;i++)	printf(" %d",a[i]);
	printf("\n");
	return 0;
}


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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<pair<int, int>> A(N);
    for(int i = 0; i < N; ++i){
        int a;
        cin >> a;
        A[i] = make_pair(a, i);
    }

    sort(A.begin(), A.end());
    for(int i = 0; i < N; ++i){
        cout << A[i].second+1 << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 1664
// ABC158-E 
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
namespace you {
    std::string to_string(char val) {
        return std::string(1, val);
        // return std::string{val};
        // you::to_string(char)
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int h,n;
    cin>>h>>n;
    vector<int> a(n+1);
    vector<int> b(n+1);

    int max_=0;
    rep(i,n){
        cin>>a[i+1]>>b[i+1];
        if(a[i+1]>max_) max_=a[i+1];
    }
    vector<vector<int>> dp(n+1,vector<int>(h+max_,pow(10,9)));

    rep(i,n+1) dp[i][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=h+max_-1;j++){
            if(a[i]<=j){
                dp[i][j]=min(dp[i-1][j],dp[i][j-a[i]]+b[i]);
            }else dp[i][j]=min(dp[i-1][j],dp[i][j]);
            //cout<<dp[i][j]<<endl;
        }
    }
    int ans=pow(10,9);
    for(int i=1;i<=n;i++){
        for(int j=h;j<h+max_;j++){
            if(dp[i][j]<ans) ans=dp[i][j];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 44288
def main():
	N, K = map(int, input().split())
	DIV = 10**9+7
	size = 2001
	fact = [0]*size
	inverse = [0]*size
	inv_cal = [0]*size
	fact[:2] = [1, 1]
	inverse[:2] = [1, 1]
	inv_cal[:2] = [0, 1]

	for i in range(2, size):
		fact[i] = (fact[i-1]*i%DIV)
		inv_cal[i] = (-inv_cal[DIV%i]*(DIV//i))%DIV
		inverse[i] = inverse[i-1]*inv_cal[i]%DIV

	def C(n, r):
		ans = fact[n]*inverse[r]%DIV
		return ans*inverse[n-r]%DIV

	for i in range(K):
		ans = 0
		if i+1 <= N-K+1:
			ans = (C(N-K+1, i+1)*C(K-1, i))%DIV
		print(ans)


if __name__ == '__main__':
	main()

Measured memory_bytes: 3572
K=int(input())
L1=[1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 
8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
print(L1[K-1])

Measured memory_bytes: 9384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 1; i <= n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

int main()
{
	/*int l, r, d;
	cin >> l >> r >> d;
	cout << r / d - (l - 1) / d;*/


	/*int n;
	cin >> n;
	int a;
	int ans = 0;
	rep(i, n){
		cin >> a;
		if (i % 2 == 0 && a % 2 == 1)ans++;
	}
	cout << ans;*/


	int n;
	cin >> n;
	int rn = (int)sqrt(n) + 1;
	for (int i = 1; i <= n; i++) {
		ll ans = 0;
		rep(x, rn)rep(y, x)rep(z, y) {
			if (x * x + y * y + z * z + x * y + y * z + z * x == i) {
				if (x == y && y == z)ans++;
				else if (x != y && y != z && z != x)ans += 6;
				else ans += 3;
				break;
			}
		}
		cout << ans << "\n";
	}



	return 0;
}

Measured memory_bytes: 3644
from itertools import product

H, W, K = map(int, input().split())

mod = 10 ** 9 + 7

dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1

for i, j, k in product(range(H), range(W), range(1 << (W - 1))):
    ok = True
    for l in range(W - 2):
        if (k >> l) & 1 and (k >> (l + 1)) & 1:
            ok = False
    if not ok:
        continue

    if j >= 1 and ((k >> (j - 1)) & 1):
        dp[i + 1][j - 1] += dp[i][j]
        dp[i + 1][j - 1] %= mod
    elif j <= W - 2 and (k >> j) & 1:
        dp[i + 1][j + 1] += dp[i][j]
        dp[i + 1][j + 1] %= mod
    else:
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod
print(dp[H][K - 1])


Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
int matrixChainOrder(int *, int);

int p[100];

int main(void){
  int i, n;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%d%d",&p[i], &p[i+1]);
  }
  printf("%d\n",matrixChainOrder(p,n));
  
  return 0;
}


int matrixChainOrder(int *p, int n)
{
  int i, j, k, l, q;
  int M[100][100];
  
  for(i=1; i<=n; i++)M[i][i] = 0;
  
  for(l=2; l<=n; l++){
    for(i=1; i<=n-l+1; i++){
      j = i+l-1;
      M[i][j] = 100000000;
      
      for(k = i; k < j; k++){
	q = M[i][k] + M[k+1][j] + p[i-1]*p[k]*p[j];
	if(M[i][j] > q) M[i][j] = q;
	
      }
    }
  }
  return M[i-1][j];
}

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

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

Measured memory_bytes: 256
n=gets.to_i
f=[]
g=[]
h=[]
i=[]
n.times{
  s=gets.chomp
  a = s[-1] == 'A'
  b = s[0] == 'B'
  if a and b
    f << s
  elsif a
    g << s
  elsif b
    h << s
  else
    i << s
  end
}

if g.size > 0 and h.size > 0
  ans = g.pop + (f * '') + h.pop
elsif g.size > 0
  ans = g.pop + (f * '')
elsif h.size > 0
  ans = (f * '') + h.pop
else
  ans = f * ''
end

while g.size > 0 and h.size > 0
  ans += g.pop + h.pop
end
ans += (g * '') + (h * '') + (i * '')

p `echo #{ans} | grep -o AB | wc -l`.to_i


Measured memory_bytes: 75132
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    ll m=0,a=0,r=0,c=0,h=0;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s[0]=='M')
            m+=1;
        else if(s[0]=='A')
            a+=1;
        else if(s[0]=='R')
            r+=1;
        else if(s[0]=='C')
            c+=1;
        else if(s[0]=='H')
            h+=1;
    }
    ll ans=0;
    ans+=m*a*r;
    ans+=m*a*c;
    ans+=m*a*h;
    ans+=m*r*c;
    ans+=m*r*h;
    ans+=m*c*h;
    ans+=a*r*c;
    ans+=a*r*h;
    ans+=a*c*h;
    ans+=r*c*h;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    int N,K;
    int number;
    cin >> N >> K;
    for(int i=1;i<=N;i++){
        int a;
        cin >> a;
        if(a == 1){
            number = i;
        }
    }
    int ans = 0;
    int l,r;
    l = r = number;
    while(l > 1){
        
        l = l - K + 1;
        ans++;
    }
    if(l <= 0){
        r = r - l + 1;
    }
    while(r < N){
        r = r + K - 1;
        ans++;
    }
    

    cout << ans << endl;
}


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

int main()
{
	map<int, int> cnt;
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		int m;
		cin >> m;
		cnt[m]++;
	}
	int ans = 0;

	for (auto u : cnt)
	{
		if (u.second >= u.first)
			ans += (u.second - u.first);
		else
			ans += u.second;
	}
	cout << ans << endl;

	return 0;
}
//8
//2 7 1 8 2 8 1 8

Measured memory_bytes: 8040
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <limits.h>
 
#define YesNo(b) ((b) ? "Yes" : "No")
#define YESNO(b) ((b) ? "YES" : "NO")

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;



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

    int ans = 0;
    for (int a = 1; a <= K; ++a)
    {
        for (int b = 1; b <= K; ++b)
        {
            int gcd_ab = gcd(a, b);
            for (int c = 1; c <= K; ++c)
            {
                ans += gcd(gcd_ab, c);
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int m = max({a,b,c});
  int ans = m*9 + a + b + c;
  cout << ans << endl;
}


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

class Main {
  static final Scanner in = new Scanner(System.in);
  static int N, K;

  static int[] h;
  // static int dp[][];
  static int dp[];
  static final int MOD = 1000000007;
  static int[] pre;

  public static void main(String[] args) throws Exception {
    N = in.nextInt();
    K = in.nextInt();
    h = new int[N];
    dp = new int[N];

    // dp = new int[N + 1][K + 1];
    // pre = new int[N];

    int old_sum = 0;
    for (int i = 0; i < N; i++) {
      h[i] = in.nextInt();
      //   pre[i] = old_sum + a[i];
      //   old_sum = pre[i];
      // Arrays.fill(dp[i],-1);
    }
    Arrays.fill(dp, -1);

    F_topDown();
    System.out.println(dp[N - 1]);
  }

  // static int F(int i, int k) {
  //   // System.out.println("\tat i == " + i + " k = " + k);
  //   if (i < N && k > pre[i]) return 0;
  //   if (i < N && k == pre[i]) return 1;

  //   if (i == 1) {
  //     // System.out.println("\tat i == 0 k = "+k);
  //     if (k > a[0]) {
  //       // System.out.println("\treturning 0");5
  //       return 0;
  //     }
  //     // System.out.println("\treturning 1");
  //     return 1;
  //   }

  //   if (dp[i][k] != -1) return dp[i][k];

  //   int val = 0;
  //   for (int j = 0; j <= a[i - 1]; j++) {
  //     // System.out.println("\t\tat i == " + i + " k = " + k + " j = " + j);
  //     if (k < j) break;
  //     val += F(i - 1, k - j) % MOD;
  //     val %= MOD;
  //   }
  //   // System.out.println("\t\tat i == " + i + " k = " + k + " val = " + val);
  //   dp[i][k] = val % MOD;
  //   return dp[i][k];
  // }

  static void F_topDown() {
    dp[0] = 0;
    dp[1] = Math.abs(h[0] - h[1]);
    for (int i = 2; i < N; i++) {
      int cost = Integer.MAX_VALUE;
      for (int k = 1; k <= K; k++) {
        if (k > i) break;
        cost = Math.min(cost, dp[i - k] + Math.abs(h[i - k] - h[i]));
      }

      dp[i] = cost;
    }

    
  }
  // static int F_topDown(int i) {
  //   for (int i = 0; i < N; i++) {
  //     //..if we have only 1 stone
  //     if (i == 0) {
  //       dp[i] = 0;
  //       continue;
  //     }

  //     //..if we have 2 stones
  //     if (i == 1) {
  //       dp[i] = Math.abs(h[0] - h[1]);
  //       continue;
  //     }

  //     //..if frog jumps from previous stone
  //     int cost1 = F(i - 1) + Math.abs(h[i - 1] - h[i]);

  //     //..if frog jumps from two stones back
  //     int cost2 = F(i - 2) + Math.abs(h[i - 2] - h[i]);

  //     //..store it before returning
  //     dp[i] = Math.min(cost1, cost2);
  //   }
  //   //..if value is already been calculated return directly
  //   if (dp[i] != -1) return dp[i];

  //   //..if frog jumps from previous stone
  //   int cost1 = F(i - 1) + Math.abs(h[i - 1] - h[i]);

  //   //..if frog jumps from two stones back
  //   int cost2 = F(i - 2) + Math.abs(h[i - 2] - h[i]);

  //   //..store it before returning
  //   dp[i] = Math.min(cost1, cost2);
  //   return dp[i];
  // }
}


Measured memory_bytes: 60456
import sys
from collections import Counter

straight = [list(range(i, i+5)) for i in range(1, 10)] + [[1,10,11,12,13]]

def hantei(hand):
	l = sorted(Counter(hand).values(), reverse=True)
	if l[0] == 4: return "four card"
	if l[0] == 3 and l[1] == 2: return "full house"
	if hand in straight: return "straight"
	if l[0] == 3: return "three card"
	if l[0] == l[1] == 2: return "two pair"
	if l[0] == 2: return "one pair"
	return "null"

for line in sys.stdin:
	hand = sorted(map(int, line.split(',')))
	print(hantei(hand))

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

using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)

bool sosu[100000];
map<ll,int> yaku;
ll n,m;
vector<ll> v;

int main(){
  cin >> n >> m;
  for(ll i = (int)m/n; i > 0; i--){
    if(m%i==0){
      cout << i <<endl;
      return 0;
    }
  }
}

/*
int main(){
  cin >> n >> m;
  REP(i,100000) sosu[i] = true;
  sosu[2] = true;
  sosu[0] = sosu[1] = false;
  FOR(i,2,100000){
    if(!sosu[i]) continue;
    ll j = 1;
    while(true){
      if(i*j>=100000) break;
      sosu[i*j] = false;
      j++;
    }
    yaku[i] = 0;
  }
  v.push_back(1);
  ll tmp = m;
  for(auto x : yaku) {
    while(tmp%x.first ==0){
      x.second++;
      tmp/=x.first;
      ll s = v.size();
      for(ll i =0;i<s;i++){
        if(v[i]>=n) continue;
        v.push_back(v[i]*x.first);
      }
    }
  }
  sort(v.begin(),v.end());
  REP(i,v.size()){
    if(v[i]>=n){
      cout << m/v[i] <<endl;
      return 0;
    }
  }
}
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char mp[2005][2005];
vector<int> r[2005],c[2005];
int main(){
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		r[i].push_back(0);
	}
	for(int j=1;j<=m;j++){
		c[j].push_back(0);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j]=='#') r[i].push_back(j);
			if(mp[i][j]=='#') c[j].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		r[i].push_back(m+1);
	}
	for(int j=1;j<=m;j++){
		c[j].push_back(n+1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='#') continue;
			auto it=upper_bound(r[i].begin(),r[i].end(),j);
			int x=*it-*(it-1)-1;
			it=upper_bound(c[j].begin(),c[j].end(),i);
			int y=*it-*(it-1)-1;
			ans=max(ans,x+y-1);
		}
	}
	cout<<ans<<endl;
}

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

#define ALL(c) c.begin(),c.end()
#define LOOP(v_name, loop_start, loop_bound) for (int(v_name) = (loop_start); (v_name) < (loop_bound); ++(v_name))
#define RLOOP(v_name, rloop_start, rloop_bound) for (int(v_name) = (rloop_start-1); v_name >= (rloop_bound); --(v_name))
#define EN_FAST_IO ios::sync_with_stdio(0);cin.tie(0);

using namespace std;
using ll = long long;
typedef vector<ll> vll;



int main(){
    EN_FAST_IO;

    int n;
    cin>>n;

    vector<double> a(n);

    for(double &x:a)cin>>x;

    sort(ALL(a));

    ll ans = 0;

    LOOP(i,1,n){
        a[i] = (a[i]+a[i-1])/2;
    }
    cout<<a[n-1];
    return 0;
}

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

using namespace std;


void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    int res = min(n*a, b);
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
import sys,collections as cl,bisect as bs,math
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = onem()

a = l()
k = 0
for i in range(n):
	if a[-(i+1)] == 1:
		k = n - i
		break

m = [0 for i in range(k+1)]
al = 0
for i in range(k,0,-1):
	co = 0
	if k // i < 2:
		m[i] = a[i-1]
		al += a[i-1]
	else:
		if i != 1:
			for j in range(1,k // i):
				co += m[i * (j+1)]
				co %= 2
			m[i] = (co ^ a[i-1])
			al += m[i]
		else:
			al %= 2
			m[1] = (al ^ a[0])

print(sum(m))
kkkk = []

for i in range(len(m)):
	if m[i] == 1:
		kkkk.append(i)
if len(kkkk) != 0:
	print(jo(kkkk))




Measured memory_bytes: 81904
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int dp[123456], ddp[123456], dpp[123546];
int aa[123456], bb[123456], cc[123456];
int main() {
	long long n, a, b, c, sum = 0; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> a >> b >> c;
		aa[h] = a; bb[h] = b; cc[h] = c;
	}
	dp[0] = aa[0]; ddp[0] = bb[0]; dpp[0] = cc[0];
	for (int h = 1; h < n; h++) {
		dp[h] = max(ddp[h - 1], dpp[h - 1]) + aa[h];
		ddp[h] = max(dp[h - 1], dpp[h - 1]) + bb[h];
		dpp[h] = max(dp[h - 1], ddp[h - 1]) + cc[h];
	}
	cout << max(dp[n - 1], max(ddp[n - 1],dpp[n - 1])) << endl;
	cin >> n;
}

Measured memory_bytes: 2560
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	vector<pair<long long int, long long int> > v;
	for(int i = 0; i < n; i++){
		long long int a, b;
		cin >> a >> b;
		v.push_back(make_pair(b, a));
	}
	sort(v.begin(), v.end());
	long long int now = 0;
	for(int i = 0; i < n; i++){
		long long int a = v[i].second;
		long long int b = v[i].first;
		if(now + a > b){
			cout << "No" << endl;
			return 0;
		}
		now += a;
	}
	cout << "Yes" << endl;
}

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

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

int main(){
	int n;
	char s,t,b;
	while(cin >> n,n){
		cin >> s >> t >> b;
		double dp[16][3][3] = {};
		int sn = s - 'A',tn = t - 'A',bn = b - 'A';
		dp[0][sn / 3][sn % 3] = 1;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < 3;j++){
				for(int k = 0;k < 3;k++){
					for(int l = 0;l < 4;l++){
						int x = j + dx[l],y = k + dy[l];
						if(x >= 0 && x < 3 && y >= 0 && y < 3 && x * 3 + y != bn){
							dp[i + 1][x][y] += dp[i][j][k] / 4.0;
						}
						else dp[i + 1][j][k] += dp[i][j][k] / 4.0;
					}
				}
			}
		}
		printf("%.9f\n",dp[n][tn / 3][tn % 3]);
	}
	return 0;
}

Measured memory_bytes: 3136
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int q = sc.nextInt();

        int[] points = new int[n];
        for (int i = 0; i < n; i++) {
            int minPoint = k - q;
            points[i] = minPoint;
        }

        for (int i = 0; i < q; i++) {
            points[sc.nextInt()-1]++;
        }

        for (int i = 0; i < n; i++) {
            if (points[i] < 1) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }
        }
    }
}

Measured memory_bytes: 69740
using System;
class Program
    {
    	static void Main(string[] args)
    	{
    		// 整数の入力
    		string[] input = Console.ReadLine().Split(' ');
            long[] a = {long.Parse(input[0]), long.Parse(input[1])};

    		string s = Console.ReadLine();
            string t = Console.ReadLine();

    		//出力
            long n = Math.Max(a[0], a[1]), m = Math.Min(a[0], a[1]);
            long big = n; long small = m;
    		while (big % small > 0)
            {
                long buf = big % small;
                big = small;
                small = buf;
            }
            long gcc = small;
            long ret = n * m / gcc;
            for (long i = 0; i < gcc; i++)
            {
                if (s[(int)(a[0] / gcc * i)] != t[(int)(a[1] / gcc * i)])
                {
                    ret = -1;
                    break;
                }
            }
            Console.WriteLine(ret);
        }
    }
    //mcs Main.cs
    //mono Main.exe

Measured memory_bytes: 13268
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    string S; cin >> S;
    vector<string> T = {"KIHBR", "AKIHBR", "KIHABR", "KIHBAR", "KIHBRA", "AKIHABR", "AKIHBAR", "AKIHBRA", "KIHABAR", "KIHABRA", "KIHBARA", "AKIHABAR", "AKIHABRA", "AKIHBARA", "KIHABARA", "AKIHABARA"};
    for (auto str : T) {
        if (S == str) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 3608
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf
import Debug.Trace

readInt = ( readLn :: IO Int )
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = readInts >>= flip replicateM getLine . head >>= mapM_ putStrLn . transpose . compress . transpose . compress

compress = filter $ any ( /= '.' )

Measured memory_bytes: 1788