akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const int MOD = 1000000007;

int main() {
    int n,d,x;
    cin>>n>>d>>x;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    for (int i=1; i<=d; i++) {
        for (int j=0; j<n; j++) {
            if (a[j]!=1&&i%a[j]==1) x++;
            else if (a[j]==1) x++;
        }
    }
    cout<<x<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
int main(){
    int64_t h,w;
    cin>>h>>w;
    if(h==1 || w==1){
        cout<<1<<endl;
    }
    else if(h%2==0){
        cout<<h/2*w<<endl;
    }
    else if(w%2!=0){
        cout<<h/2*(w/2) + (h/2+1)*(w/2+1)<<endl;
    }
    else{   
        cout<<h/2*(w/2) +(h/2+1)*(w/2)<<endl;
    }
}

Measured memory_bytes: 256
num = int(input())


beforTime = 0
beforX = 0
beforY = 0
resultFrag = True
for travel in range(num):
    time, x, y = map(int, input().split())
    move = abs(beforX - x) + abs(beforY - y)
    canMoveTime = time - beforTime
    if move <= canMoveTime and (move + canMoveTime) % 2 == 0:
        beforTime = time
        beforX = x
        beforY =  y
        continue
    resultFrag = False
    break

print("Yes" if resultFrag else "No")

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

using namespace std;

typedef long long ll;

int main(){
  int n, h; cin >> n >> h;
  int a[n], b[n];
  int amax = 0;
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i];
    amax = max(amax, a[i]);
  }
  priority_queue<int> throwable;
  for(int i=0;i<n;i++){
    if(b[i] > amax) throwable.push(b[i]);
  }
  int d=0, cnt=0;
  while(d < h){
    if(!throwable.empty()){
      d = d+throwable.top(); throwable.pop();
    }else{
      d = d+amax;
    }
    cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;

#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define fst first
#define snd second

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n), b(n), c(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> c[i];
    }
    sort(ALL(a));
    sort(ALL(b));
    sort(ALL(c));
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ll x = lower_bound(ALL(a), b[i]) - a.begin();
        ll y = c.end() - upper_bound(ALL(c), b[i]);
        ans += x * y;
    }
    cout << ans;
    return 0;
}

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

using namespace std;

int main()
{
    int n;
    
    while (scanf("%d", &n) && n){
        pair<int, int> a[32];
        
        for (int i = 0; i < n; i++){
            scanf("%d %d", &a[i].second, &a[i].first);
        }
        
        sort(a, a + n);
        
        bool ok = true;
        
        for (int i = 0; i < n; i++){
            if (i) a[i].second += a[i - 1].second;
            if (a[i].first < a[i].second) ok = false;
        }
        
        if (ok) printf("Yes\n");
        else printf("No\n");
    }
    
    return (0);
}

Measured memory_bytes: 1168
let (n, m) = Scanf.sscanf (read_line ()) "%d %d" @@ fun n m -> (n, m)
let ab = Array.init m @@ fun _ -> Scanf.sscanf (read_line ()) "%d %d" @@ fun a b -> (a, b)

let cnt = Array.make 100_001 0

let () =
  Array.iter (fun (a, b) ->
    cnt.(a) <- cnt.(a) + 1;
    cnt.(b) <- cnt.(b) + 1
  ) ab;
  print_endline @@ if cnt 
    |> Array.map (fun cnt -> cnt mod 2 = 0)
    |> Array.fold_left (&&) true 
    then "YES" else "NO"

Measured memory_bytes: 8320
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#include<assert.h>

typedef long long ull;
typedef unsigned long long ll;

#define mod 1000000007LL

int main()
{
    int n;
    ll* a;
    ll sum = 0, b, m;
    scanf("%d", &n);
    a = calloc(n, sizeof(ll));
    for (size_t i = 0; i < n; i++)
    {
        scanf("%lld", a + i);
    }

    b = 1;
    for (size_t i = 0; i < 61; i++)
    {
        m = 0;
        for (size_t j = 0; j < n; j++)
        {
            if(a[j] & b) m++;
        }
        sum += ((((b % mod) * m) % mod) * (n - m)) % mod;
        sum %= mod;
        b <<= 1;
    }

    printf("%lld", sum);

    return 0;
}



Measured memory_bytes: 2560
#include <iostream>

int main()
{
    long long A, B, K;
    std::cin >> A >> B >> K;

    for (long long i = A; i <= B; i++) {
        if (i - A < K || B - i < K) {
            std::cout << i << std::endl;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  long long n,a=1,i,j;
  char s[100010];
  scanf("%lld",&n);
  for(i=1;1;i++){
    a*=26;
    if(a>=n)break;
    n-=a;
  }
  //printf("%lld\n",i);
  n--;
  for(j=0;j<i;j++){
    s[i-j-1]=n%26+'a';
    n/=26;
  }
  s[i]=0;
  printf("%s\n",s);
  return 0;
}


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

int main(){

  int a,b, tmp;
  cin >> a >> b;
  vector<int> prices;
  
  tmp = a*100/8;
  prices.push_back(tmp);
  prices.push_back(tmp+1);
  tmp = b*100/10;
  prices.push_back(tmp);
  prices.push_back(tmp+1);
  

  rep(i,4){
    if(prices[i]*8/100 == a && prices[i]*10/100 == b){
      cout << prices[i] << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define watch(x) cout <<(#x)<<" is "<<(x)<<endl
#define debug cout <<"hi"<<endl
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
int main(){
  ll n,k; cin >>n >>k;
  cout <<((k-n-2)*(k*(2*k-n-2)-n*(n+1)-6)/6)%MOD;
return 0;}

Measured memory_bytes: 3672
N,C=map(int,input().split())

D=[list(map(int,input().split())) for i in range(C)]
grid=[list(map(int,input().split())) for i in range(N)]

a=[[0]*C for i in range(3)]


for i in range(N):
    tmp=i%3
    for j in range(N):
        a[tmp][grid[i][j]-1]+=1
        tmp=(tmp+1)%3

b=[[0]*C for i in range(3)]
for i in range(3):
    for j in range(C):
        b[i][j]=sum([ D[k][j] * a[i][k] for k in range(C)])

b=[ sorted([ [b[i][j],j] for j in range(C)]) for i in range(3)]

ans=10**15
for i in range(3):
    for j in range(3):
        for k in range(3):
            if b[0][i][1]!=b[1][j][1] and b[1][j][1]!=b[2][k][1] and b[2][k][1]!=b[0][i][1]:
                ans=min(ans,b[0][i][0]+b[1][j][0]+b[2][k][0])

print(ans)

Measured memory_bytes: 5620
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a) memset(a,0,sizeof(a));
#define il inline
#define sz(a) ((int)o.size())
#define run(x) for(int k=head[x];k;k=e[k].ne)
#define v e[k].t
#define all(a) o.begin(),o.end()
#define mp make_pair
#define pb push_back 
#define w1 first
#define w2 second
#define adm(a,b,c) {a=a+b;if(a>=c)a-=c;else if(a<0)a+=c;}
typedef double db;
typedef long long ll;typedef long double ld;typedef unsigned long long ull;
typedef pair<int,int> pa;
const int N=1e6+5,M=1e7+5,INF=1e9,mod=1e9+7;
const ll linf=1e18;const double eps=1e-8,pi=acos(-1);
il int gmin(int &a,int b){if(a>b)a=b;}il ll gmin(ll &a,ll b){if(a>b)a=b;}il int gmax(int &a,int b){if(a<b)a=b;}il ll gmax(ll &a,ll b){if(a<b)a=b;}
il void read(ll&x){ll f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il ll read(ll&x,ll&y){read(x);read(y);}
il void read(int&x){int f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il int read(int&x,int&y){read(x);read(y);}
il void read(int&a,int&b,int&c){read(a);read(b);read(c);}il void read(ll&a,ll&b,ll&c){read(a);read(b);read(c);}
il int read(){int x;read(x);return x;}
il ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;}il ll qpow(ll a,ll b){ll ret=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod;return ret;}
il ll qmul(ll a,ll b,ll p){ll ret=0;for(;b;b>>=1,a=(a<<1)%p)if(b&1)adm(ret,a,p);return ret;}il ll qmul(ll a,ll b){ll ret=0;for(;b;b>>=1,a=(a<<1)%mod)if(b&1)adm(ret,a,mod);return ret;}
il void judge(){
	freopen("dato.in","r",stdin);
	freopen("dato.out","w",stdout);
}
ll res[N],st[N],f[N];int top,n,q;
int main(){
	read(n,q);st[0]=n;
	rep(i,1,q){
		ll w;read(w);
		if(w<=st[0]){st[0]=w;top=0;}else{
			while(top&&st[top]>=w)top--;
			st[++top]=w;
		}
	}f[top]=1;
	repd(i,top,1){
		ll o=st[i];
		while(o>=st[0]){
			int id=upper_bound(st,st+i,o)-st-1;
			f[id]+=o/st[id]*f[i];
			o%=st[id];
		}res[o]+=f[i];
	}res[st[0]]+=f[0];
	repd(i,n-1,1)res[i]+=res[i+1];
	rep(i,1,n)printf("%lld\n",res[i]);
}

Measured memory_bytes: 10624
package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	k := getNextInt(scanner)
	aa := make([]int64, n)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt64(scanner)
	}
	for i := k; i < n; i++ {
		if aa[i] > aa[i-k] {
			fmt.Fprintln(writer, "Yes")
			continue
		}
		fmt.Fprintln(writer, "No")
	}
}


Measured memory_bytes: 6364
N, M = map(int, input().split())
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
mod = 10 ** 9 + 7
for _ in range(M):
    dp[int(input())] = -1
for i in range(2, N+1):
    dp[i] = ((dp[i-1] if dp[i-1] != -1 else 0) + (dp[i-2] if dp[i-2] != -1 else 0))%mod if dp[i] != -1 else -1
print(dp[N])

Measured memory_bytes: 44760
#include <stdio.h>

int main(){
    int n;

    scanf("%d", &n);

    int B[n-1];
    for(int i = 0; i < n; i++){
        scanf("%d", &B[i]);
        /* printf("%d\n",B[i]); */
    }

    int A[n];
    A[0] = B[0];
    for(int i = 0; i < n-2; i++){
        if(B[i] <= B[i+1])
        {
            A[i+1] = B[i];
            /* printf(">%d,%d\n", i,A[i+1]); */
        } else {
            A[i+1] = B[i + 1];
            /* printf("<%d\n", A[i+1]); */
        }
    }
    /* printf("%d\n",B[n-1]); */
    A[n-1] = B[n-2];

    int count=0;
    for(int i=0; i < n ; i++){
        count += A[i];
        /* printf("i=%d,A=%d\n",i, A[i]); */
    }
    printf("%d", count);
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int digit=0;
  int temp=n;
  while(temp>0){
    digit+=temp%10;
    temp/=10;
  }
  if(n%digit==0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return(0);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
*/

double a,b,x,ans;

bool f(double arg){
	double V=0;
	if(a*tan(arg/180*M_PI)<=b){
		V = a*(a*b - a*a*tan(arg/180*M_PI)/2);
	}else{
		V = a*(b*b*tan((90-arg)/180*M_PI)/2);
	}
	// cerr<<arg<<","<<V<<endl;
	return V>=x;
}

int main(void){
	cin>>a>>b>>x;
	if(a*a*b/2<x){
		cout<<fixed<<setprecision(15)<<atan2((a*b-x/a)*2/a/a,1.0)/M_PI*180<<endl;
	}else{
		cout<<fixed<<setprecision(15)<<90-atan2(2*x/(a*b*b),1.0)/M_PI*180<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    boolean A = false;
    boolean B = true;
    int C = 0;
    for(int i = 0; i < S.length(); i++){
      if(i == 0){
        if(S.charAt(i) == 'A'){
          A = true;
        }
      }else if(i == 1 || i == S.length()-1){
        if(S.charAt(i) >= 'A' && S.charAt(i) <= 'Z'){
          B = false;
        }
      }else{
        if(S.charAt(i) == 'C'){
          C++;
        }else{
          if(S.charAt(i) >= 'A' && S.charAt(i) <= 'Z'){
            B = false;
          }
        }
      }
    }
    System.out.println((A && B && C==1) ? "AC" : "WA");
  }
}

Measured memory_bytes: 21844
open System 

type Explicit =          
    static member inline ($) (_:int32, _:Explicit) = int
    static member inline ($) (_:int64, _:Explicit) = int64

let inline convert (value:'a): 'b = 
    (Unchecked.defaultof<'b> $ Unchecked.defaultof<Explicit>) value

let inline fromInt (x: int): 'a = convert x

module NumericLiteralG =
    let inline FromZero(): ^a = LanguagePrimitives.GenericZero
    let inline FromOne(): ^a = LanguagePrimitives.GenericOne
    let inline FromInt32 n = fromInt n

let R() = Console.ReadLine()

let f (n: int) (m: int): int = 
    n * (n - 1) / 2 
    + m * (m - 1) / 2
    

let N, M = let t = R().Split() |> Array.map (string>>int) in t.[0], t.[1]

f N M 
|> printfn "%i"

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

#include <fstream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  /*
  ifstream in("input.txt");
  cin.rdbuf(in.rdbuf());
  //*/
  int X;
  cin >> X;
  if(X >= 30) cout << "Yes" <<endl;
  else cout << "No" <<endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int N=1e5+5;
int main()
{
    ios::sync_with_stdio(false);
    ll x,i,j,x1,x2;
    scanf("%lld",&x);
	for(i=-1000;i<=1000;i++)
	{
		for(j=-1000;j<=1000;j++)
		{
			x1=pow(i,5);x2=pow(j,5);
			if(x==x1-x2)
			{
				printf("%lld %lld\n",i,j);return 0;
			}
		}
	}
    return 0; 
}

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

int main() {
	unsigned int r=0,c=0;

	scanf("%d %d", &r, &c);
	int input[r+1][c+1];
	int sum=0;

	memset(input,0,sizeof(input)/sizeof(int));

	//初期化
	for(int i=0;i<=r;i++){
		for(int j=0;j<=c;j++){
			input[i][j]=0;
		}
	}

	for(int i=0;i<r;i++){
		char ANums[c*sizeof(int)+1];
		scanf("\n%[^\n]",ANums);
		//文字列から数字を取り出す
		int digitcount=0;
		for(int j=0;j<c;j++){
			//次の数値に
			while(ANums[digitcount]==' '){
				digitcount++;
			}
			//数値を取り出す
			int num =atoi(&ANums[digitcount]);
			input[i][j]=num;
			input[i][c]+=num;
			input[r][j]+=num;
			sum+=num;

			//ラストでなければ次の空白に
			if(j!=c-1){
				while(ANums[digitcount]!=' '){
					digitcount++;
				}
			}
		}
	}

	input[r][c]=sum;

	//表示
	for(int i=0;i<=r;i++){
		for(int j=0;j<=c;j++){
			printf("%d",input[i][j]);
			if(j != c){
			    printf(" ");
			}
		}
		puts("");
	}

	return 0;
}



Measured memory_bytes: 2052
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
        long[] a = Read.Ints();HashSet<long> s = new HashSet<long> { };
        Console.WriteLine(Math.Max(0,a[2]*(a[0]-1)+a[1]+1-(a[2]+(a[0]-1)*a[1])));
        Console.ReadLine();
    }
    public static Boolean uso() { return false; }
    public static int gcd(int a,int b)
    {
        while (true)
        {
            if (a == 0) { return b; }
            if (b == 0) { return a; }
            if (a > b) { a -= b; }
            else { b -= a; }
        }
    }
    public static int lcm(int a,int b)
    {
        return a * b / gcd(a,b);
    }
    public static bool IsPrime(long n)
    {
        if (n < 2) return false;
        if (n == 2) return true;

        for (int i = 2; i < n; i++)
        {
            if (n % i == 0) return false;
        }
        return true;
    }

}
public static class Read
{
    public static void outl(string n = "") { Console.WriteLine(n); return; }
    public static int Int()
    {
        return int.Parse(Console.ReadLine());
    }
    public static long[] Ints()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }
    public static string Str() { return Console.ReadLine(); }
    public static string[] Strs() { return Console.ReadLine().Split(); }
}

Measured memory_bytes: 13280
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll a,b,p;
    string s,ss,sss;
    vector<string>v;
    cin>>s>>ss;
    //a=s.size(); b=ss.size();
    for(ll i=0,j=0;i<s.size();i++,j++)
    {
        cout<<s[i];
        if(j<ss.size())cout<<ss[i];
    }
}


Measured memory_bytes: 256
/* ＵＴＦ－８ */
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	int N;
	std::cin >> N;
	
	int M = N / 1.08;
	if (N == (int)(M * 1.08)) {
		std::cout << M << "\n";
	} else if (N == (int)((M+1) * 1.08)) {
		std::cout << (M+1) << "\n";
	} else if (N == (int)((M-1) * 1.08)) {
		std::cout << (M-1) << "\n";
	} else {
		std::cout << ":(\n";
	}
}


Measured memory_bytes: 256
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>

const int N = 1e5 + 100;
bool opened[N], closed[N], open = false;
vector<vector<int>> a(N);
signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    a[v].push_back(u);
    opened[u] = true;
    closed[v] = true;
  }

  for (int i = 1; i <= n; i++) {
    sort(a[i].begin(), a[i].end());
  }

  int ans = 0;
  int last = -1;
  for (int i = 1; i <= n; i++) {
    if (closed[i] && open) {
      int lb = lower_bound(a[i].begin(), a[i].end(), last) - a[i].begin();
      if (lb != sz(a[i])) {
        last = i;
        ans++;
        open = false;
      }
    }
    if (opened[i]) {
      open = true;
    }
  }
  cout << ans << "\n";
}



Measured memory_bytes: 5372
/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
int a[3];
void solve() {
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if(a[0] + a[1] == a[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
}
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    solve();
    return 0;
}


Measured memory_bytes: 384
s = int(input())
if 10**9 >= s:
    print(0,0,s,0,0,1)
    exit()
x = int(s**0.5)
if x**2 >= s:
    t = x**2-s
    if t <= 10**9:
        print(0,0,x,1,t,x)
else:
    if x*(x+1) >= s:
        t = x*(x+1) -s
        if t <= 10**9:
            print(0,0,x,1,t,x+1)
    elif (x+1)**2 >= s:
        t = (x+1)**2 - s
        if t <= 10**9:
            print(0,0,x+1,1,t,x+1)


Measured memory_bytes: 9384
#include <iostream>

int main()
{
    int a, b, c, n = 3;
    std::cin >> a >> b >> c;
    if ((a == b) && (a == c)) n = 1;
    else if ((a == b) || (b == c) || (a == c)) n = 2;
    std::cout << n << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[1000001];
int b[1000001];
int c[1000001];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<n;i++)
		scanf("%d",&c[i]);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=b[i];
		if(a[i]==a[i-1]+1)
			ans+=c[a[i-1]];
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 4352
n = int(input())
ans = [0] * 1030302

for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            number = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            ans[number] += 1


for x in range(1, n+1):
    print(ans[x])

Measured memory_bytes: 16948
import java.util.*;
class Main{
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args){
        int N = sc.nextInt(),//人数
        K=sc.nextInt(),//ポイント
        point[] = new int[N],
        Q=sc.nextInt();//回数
        //A[] = new int[N];//そのラウンドで正解した人
        Arrays.fill(point,0);
        for(int i=0;i<Q;i++) {
            point[sc.nextInt()-1]++;
        }
        for(int i=0;i<N;i++){
                System.out.println(point[i]-Q+K>0?"Yes":"No");
        }
    }
}

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

/*

2xy + x + y - a = 0
2xy + y = a - x
y(2x + 1) = a - x

*/

bool check(int a)
{
	for (int x = 1; x * x <= a; x++){
		int y = (a - x) / (2 * x + 1);
		// cout << x << " " << y << endl;
		if (2 * x * y + x + y == a){
			return false;
		}
	}
	return true;
}

int main()
{
	int n;
	cin >> n;
	int res = 0;
	for (int i = 0; i < n; i++){
		int a;
		cin >> a;
		if (check(a)) res++;
	}
	cout << res << endl;
}

Measured memory_bytes: 1160
#include<iostream>
#include<math.h>
#include <algorithm>
#include<float.h>
#include <limits>
#include <vector> 
#include <numeric>
#include <string.h>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define ll long long

using namespace::std;

int jo(ll int jxo, ll int jyo){
	ll int jhogeo = 1;
	rep(jinto,0,jyo) jhogeo=jhogeo*jxo;
	return jhogeo;
}
char tobig(char toxbig){
  return (toxbig-0x20);
}
char tolow(char toxlow){
  return (toxlow+0x20);
}
  


int main(){
  int a,b;
  cin>>a>>b;
  if(a<9&&b<9) cout<<"Yay!";
  else cout<<":(";
}
// int *p = new int[N];

//  vector<int> 変数名(要素数);
//  sort(変数名.begin(),変数名.end());//昇順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <stack>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define mkt make_tuple
#define no {cout << -1; return;}

void solve() {
    int q, add = 0, sum = 0;
    bool flag = 0;
    multiset <int> lef, rig;
    cin >> q;
    loop(i, q) {
        int e; cin >> e;
        if (e == 1) {
            int a, b;
            cin >> a >> b;
            a *= -1;
            add += b;
            flag = !flag;
            if (rig.empty() || lef.empty() || (!lef.empty() && *lef.rbegin() < a)) {
                rig.insert(a); sum += a;
            }
            else {
                lef.insert(a); sum -= a;
            }
            if (rig.size() > lef.size())
                while ((!flag ? lef.size() != rig.size() : lef.size() + 1 != rig.size())) {
                    lef.insert(*rig.begin());
                    sum -= 2 * (*rig.begin());
                    rig.erase(rig.begin());
                }
            else if (rig.size() < lef.size())
                while ((!flag ? lef.size() != rig.size() : lef.size() + 1 != rig.size())) {
                    auto it = lef.end(); --it;
                    rig.insert(*it);
                    sum += 2 * (*it);
                    lef.erase(it);
                }

        }
        else {
            auto it = rig.begin();
            int x = -(*it);
            cout << x <<  " " << sum + add + x * flag << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

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

int main()
{
    int k,c,i;
    char t[10000];
   scanf("%d",&k);
   scanf("%s",t);
   c=strlen(t);
   if(c<=k)
   {

        printf("%s",t);
   }
   else
   {
       for(i=0;i<k;i++)
       {
           printf("%c",t[i]);
       }
       printf("...\n");
   }
}

Measured memory_bytes: 1732
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	string s;
	cin>>s;
	cout<<s.substr(0, s.size()-8)<<endl;
	return 0;
}


Measured memory_bytes: 768
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r#"29"# => "Yes",
r#"24"# => "No",
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        n: chars,
    }

    if n.into_iter().filter(|&x| x == '9').count() > 0 { "Yes" } else { "No" }.to_string()
}

Measured memory_bytes: 4352
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

struct P
{
	int w, s; 
	string name;
};

int main()
{
    for(int n; cin >> n && n;)
	{
		vector<P> v(n);
		
		rep(i, n) cin >> v[i].name >> v[i].w >> v[i].s;
		
		vint p(n), ans;
		rep(i, n) p[i] = i;
		
		double suit = 100000;
		
		do 
		{
			double sum = 0;
			double num = 0;
			
			for(int i = n - 1; 0 <= i; i--)
			{
				P &e = v[p[i]];
				
				if(e.s < sum) break;
				
				sum += e.w;
				num += (i + 1) * e.w;
				
				if(i == 0)
				{
					double sub = num / sum;
					
					if(sub < suit)
					{
						ans = p;
						suit = sub;
					}
				}
			}
		}
		while(next_permutation(ALL(p)));
		
		rep(i, n) cout << v[ans[i]].name << endl;
	}
}

Measured memory_bytes: 916
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;
 
void solve(){
 
}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n){
        int m;
        cin >> m;
        a[i] = m;
    }
    ll money = 1000;
    rep(i,n-1){
        if(a[i]<a[i+1]){
            ll q = money/a[i];
            money += q*(a[i+1]-a[i]);
        }
    }
    cout << money << endl;
    return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  
  for(int i=0; i<W+1; i++) {
    cout << "#";
  }
  cout << "#" << endl;
  
  for(int i=0; i<H; i++) {
    cout << "#";
    for(int j=0; j<W; j++) {
      char a;
      cin >> a;
      cout << a;
    }
    cout << "#" << endl;
  }
  
  for(int i=0; i<W+1; i++) {
    cout << "#";
  }
  cout << "#" << endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
vector<ll> pw2(51,1);vector<ll> pw10(19,1);
ll N,K;
vector<ll> zero_size(42,0);

ll rec(ll rem,ll now){
    if(rem>=pw2[now+1]-1){
        ll ret=0;
        rep(i,now+1){
            ret += max(zero_size[i],N-zero_size[i]) * pw2[i];
        }
        return ret;
    }
    else if(rem>=pw2[now]){
        return max(rec(rem-pw2[now], now-1)+pw2[now]*zero_size[now], rec(rem,now-1)+pw2[now]*(N-zero_size[now]));
    }
    else{
        return rec(rem,now-1)+pw2[now]*(N-zero_size[now]);
    }
}
int main(){
    {rep1(i,50) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    cin>>N>>K;
    ll ans=0;
    vector<ll> A(N,0);
    rep(i,N){
        cin>>A[i];
        rep(j,42){
            if((A[i]&pw2[j])==0) zero_size[j]++;
        }
    }
    
    cout<<rec(K,41)<<endl;
}



Measured memory_bytes: 4052
#include <stdio.h>

int main(){
   int a,b,c;
 
   scanf("%d %d %d",&a,&b,&c);
   if (((a==b) && a!=c) || ((b==c) && a!=b) || ((a==c) && a!=b))
      puts("Yes");
   else
      puts("No");
   return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    int d[8][2] = { {1,0}, {-1,0}, {0,1}, {0,-1}, {1,1}, {-1,-1}, {1,-1}, {-1,1} };
    int H,W;
    cin >> H >> W;
    vector<string> S(H);
    vector<string> ans(H);
    for ( int i = 0; i < H; i++ ) {
        cin >> S[i];
    }
    
    for ( int i = 0; i < H; i++ ) {
        
        for ( int j = 0; j < W; j++ ) {
            
            if ( S[i][j] == '#' ) { ans[i] += '#'; continue; }
            
            int count = 0;
            for ( int k = 0; k < 8; k++ ) {
                int x = i+d[k][0];
                int y = j+d[k][1];
                if ( x >= 0 && y >= 0 && x < H && y < W && S[x][y] == '#' ) { count++; }
            }
            ans[i] += to_string(count);
            
        }
        
    }
    
    for ( int i = 0; i < H; i++ ) {
        cout << ans[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(str(input()))
B = list(str(input()))
C = list(str(input()))
count = 0
for i in range(N):
    if A[i] == B[i] and B[i] == C[i]:
        pass
    elif A[i] == B[i] or B[i] == C[i] or C[i] == A[i]:
        count+=1
    else:
        count+=2
print(count)

Measured memory_bytes: 3064
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<ll, ll>;
const int maxn = 4079, mlg = 17, mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[10], b[10], c[10];
int fmin(int n) {
	iota(a, a+n, 0);
	iota(b, b+n, n);
	iota(c, c+n, 2*n);
	int cnt = 0, ans = 1<<30;
	do {
		int cuR = 0;
		do {
			int cur = -(1<<30);
			for(int i = 0; i < n; i++)
				cur = max(cur, a[i] + b[i] - c[i]);
			if(cur == -((n+1)/2)) {
				cout << "Answer " << n << ":\n";
				for(int i = 0; i < n; i++)
					cout << (b[i]&1) << " ";
				for(int i = 0; i < n; i++)
					cout << (b[i]&1) << " ";cout << '\n';
				for(int i = 0; i < n; i++)
					cout << (b[i]) << " ";
				for(int i = 0; i < n; i++)
					cout << (b[i]) << " ";cout << '\n';
			}
			ans = min(ans, cur);
		} while(next_permutation(c, c+n));
		cnt += cuR > 0;
	} while(next_permutation(b, b+n));
	cout << cnt << "\n";
	return ans;
}
void solve() {
	int n, k;
	cin >> n >> k;
	vi a(n), b(n), C(n);
	iota(all(a), 0);
	set<int> c;
	for(int i = 2*n; i < 3*n; i++) c.insert(i);
	int ans = -((n+1)/2);
	if(k+ans>0) cout << "-1", exit(0);
	for(int x = 2*n - 1, i = 0; i < n; i++) {
		b[i] = x;
		auto it = c.lower_bound(a[i]+b[i]-ans);
		if(it == c.end()) exit(-1);
		C[i] = *it;
		c.erase(it);
		x -= 2;
		if(x < n) x = 2*n - 2;
	}
	for(int i = 0; i < n; i++) cout << k+a[i] << " " << k+b[i] << " " << k+C[i] << '\n';
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	solve();
}


Measured memory_bytes: 8192
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
#define N 500005
#define INF 0x3f3f3f3f
#define LL long long
int rd()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48); c=getchar();}
	return f*x;
}
priority_queue<int,vector<int>,greater<int> > Q;//小根堆 保证字典序最小 
int n,k,m;
int ind[N];
vector<int>G[N];
int q[N],ans[N];
int tree[N<<2];
//权值线段树 维护区间最小值(因为是从右到左 就是离他最近 
void PushUp(int i)
{
	tree[i]=min(tree[i<<1],tree[i<<1|1]);
}
void Update(int i,int l,int r,int pos,int val)
{
	if(l==r)
	{
		tree[i]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) Update(i<<1,l,mid,pos,val);
	else Update(i<<1|1,mid+1,r,pos,val);
	PushUp(i);
}
int Query(int i,int l,int r,int ql,int qr)
{
	if(r<ql||qr<l) return INF;
	if(ql<=l&&qr>=r) return tree[i];
	int mid=(l+r)>>1;
	return min(Query(i<<1,l,mid,ql,qr),Query(i<<1|1,mid+1,r,ql,qr));
} 
void Topo()
{
	for(int i=1;i<=n;i++)
		if(!ind[i]) Q.push(i);
	while(!Q.empty())
	{
		int u=Q.top(); Q.pop();
		q[++m]=u;
		for(int i=0;i<G[u].size();i++)
		{
			int v=G[u][i];
			ind[v]--;
			if(!ind[v]) Q.push(v);
		}
	}
}
int main()
{
	memset(tree,INF,sizeof(tree));
	n=rd(),k=rd();
	for(int i=1;i<=n;i++)
		q[rd()]=i;
	for(int i=n;i>=1;i--)
	{
		int j=Query(1,1,n,q[i]+1,q[i]+k-1);//q[j]-q[i]<k
		if(j!=INF) ind[q[j]]++,G[q[i]].push_back(q[j]);
		j=Query(1,1,n,q[i]-k+1,q[i]-1);//q[i]-q[j]<k
		if(j!=INF) ind[q[j]]++,G[q[i]].push_back(q[j]);
		Update(1,1,n,q[i],i);
	}
	Topo();
	for(int i=1;i<=n;i++)
		ans[q[i]]=i;
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 44940
#include<stdio.h>
int main()
{
    int h,w,i,j,k;

    while(scanf("%d%d",&h,&w)){
        if(h==0 && w==0)
            break;

        k=1;
        for(i=1;i<=h;i++){
            for(j=1;j<=w;j++){
                if(k==1)
                    printf("#");
                else
                    printf(".");
                k=k*(-1);
            }

            if(w%2==0)
            k=k*(-1);

            printf("\n");

        }

    printf("\n");
    }

    return 0;

}



Measured memory_bytes: 2620
def BellmanFord(edges, num_v, source):
    #グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    #変の和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i == num_v - 1 and edge[1] == num_v:
                    return -1

    return dist

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

dist = BellmanFord(edges, num_v, 1)
if dist == -1:
    print("inf")
else:
    print(-dist[-1])


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

int main() {
  long long int q,h,s,d,n;
  cin >> q >> h >> s >> d >> n;
  h = min(h, 2*q);
  s = min(s, 2*h);
  if (2*s<=d) {
    cout << n*s << endl;
  }
  else {
    if (n%2==0) 
      cout << n/2 * d << endl;
    else
      cout << n/2 * d + s << endl;
  }
  return 0;
}
      


Measured memory_bytes: 256
n = int(input())
trains = [list(map(int, input().split())) for _ in range(n-1)]

for sta in range(n):
  current = 0
  for i in range(sta, n-1):
    if(trains[i][1] >= current):
      current = trains[i][1]
    else:
      if(current % trains[i][2] != 0):
        current += trains[i][2] - (current % trains[i][2])
    current += trains[i][0]
  print(current)

Measured memory_bytes: 3188
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<cassert>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++ )

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

class State{
    public:
    char G[5][5]; 
    int py, px, n;
    State(int n=0):n(n){}
    bool operator < ( const State &s) const{
	rep(i, n) rep(j, n){
	    if ( G[i][j] == s.G[i][j] ) continue;
	    return G[i][j] < s.G[i][j];
	}
	return false;
    }
    bool goal(){
	rep(i, n) rep(j, n) if ( G[i][j] == '#' ) return false;
	return true;
    }

    void activate(){
	char tmp[5][5];
	int nx, ny;
	rep(y, n) rep(x, n) tmp[y][x] = '.';
	rep(y, n) rep(x, n){
	    if ( G[y][x] == '@' ) {
		tmp[y][x] = '@';
		continue;
	    }
	    int cnt = 0;
	    rep(d, 8){
		ny = y + dy[d];
		nx = x + dx[d];
		if ( ny < 0 || nx < 0 || ny >= n || nx >= n ) continue;
		if ( G[ny][nx] == '#' || G[ny][nx] == '@' ) cnt++;
	    }
	    if ( G[y][x] == '#'){
		if ( cnt == 2 || cnt == 3 ) tmp[y][x] = '#';
	    } else {
		if ( cnt == 3 ) tmp[y][x] = '#';
	    }
	}
	rep(y, n) rep(x, n) G[y][x] = tmp[y][x];
    }
};

int bfs( int n, State source ){
    queue<State> Q;
    map<State, int> D;
    set<State> V;
    
    Q.push(source);
    D[source] = 0;
    V.insert(source);
    
    State u, v;
    int ny, nx;
    while(!Q.empty() ){
	u = Q.front(); Q.pop();
	if ( u.goal() ) return D[u];
	
	rep(d, 8){
	    ny = u.py + dy[d];
	    nx = u.px + dx[d];
	    if ( ny < 0 || nx < 0 || ny >= n || nx >= n ) continue;
	    if ( u.G[ny][nx] == '#' ) continue;
	    v = u;
	    v.G[u.py][u.px] = '.';
	    v.G[ny][nx] = '@'; v.py = ny; v.px = nx;
	    v.activate();
	    if ( V.insert(v).second ){
		V.insert(v);
		D[v] = D[u] + 1;
		Q.push(v);
	    }
	}
    }
    return -1;
}

main(){
    int n;
    State source;
    while( cin >> n && n ){
	source = State(n);
	rep(y, n) rep(x, n){
	    cin >> source.G[y][x];
	    if ( source.G[y][x] == '@' ){
		source.py = y;
		source.px = x;
	    }
	}
	cout <<  bfs(n, source) << endl;
    }
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
const ll INF = (1ll << 60);

int main() {
  ll M, D;
  cin >> M >> D;
  ll cnt = 0;
  for (ll m = 1; m <= M; m++) {
    for (ll d = 1; d <= D; d++) {
      ll a = d % 10;
      ll b = d / 10;
      if (b >= 2 && a >= 2 && a * b == m) {
        cnt += 1;
      }
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;
 
//最大公約数を求める
long long gcd(long long a, long long b){
  if(b == 0){
    return a;
  }
  return gcd(b, a%b);
}
 
//最小公倍数を求める
long long lcm(long long a, long long b){
  return a*b/gcd(b, a%b);
}
 
int main() {
  long long A, B;
  long long ans = 1;
 
  cin >> A >> B;
 
  long long maxKY = gcd(A,B); 
  long long lasti= 0;

	// vector<long long> x(sqrt((double)maxKY) + 1, 0);
	long long num = maxKY; // 素因数分解する変数num 
      // cout <<"maaxKY: "<< maxKY << endl;

  // cout << "num:" << num << endl;
	for (long long i = 2; i*i <= maxKY; i++) {
		while (num%i == 0) { // 素数で割り切れなくなるまで割っていく
      if(lasti == 0){
        ans++;
      }
			// x.at(i)++; //割った個数を配列に足す
      // cout << i << endl;
			num /= i;
      lasti=i;
		}
    lasti=0;
	}
  // cout << "num:" << num << endl;

  if(num != 1){
    ans++;
  }  

  cout << ans << endl;
}
 

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

using namespace std;

int main() {
    char S[105];
    cin >> S;
    for (int i = 0; ; ++i) {
        if (S[i] == 0) {
            cout << "Yes";
            return 0;
        }
        if (i & 1) {
            if (S[i] == 'R') break;
        }
        else if (S[i] == 'L') break;
    }
    cout << "No";
    return 0;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<long double> xs(n);
    for (auto& x : xs) {
        cin >> x;
    }
    sort(xs.begin(), xs.end());
    for (int i = 1; i < n; ++i) {
        xs[i] = (xs[i-1] + xs[i]) / 2;
    }
    cout << setprecision(30) << xs.back() << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(){
  int n;
  int h[101];
  int highest = 0;
  int sum = 0;

  scanf("%d", &n);

  for(int cnt = 0; cnt < n; cnt++){
    scanf("%d", &h[cnt]);
    if(h[cnt] >= highest){ 
      sum++;
      highest = h[cnt];
    }

  }

  printf("%d", sum);
  printf("\n");
  
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
 
struct block {
    int w, s, v;
};
 
bool cmp(const block &x, const block &y) {
    return x.w + x.s > y.w + y.s;
}
 
const int N = 2e4+10;
int memo[N];
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<block> arr(n);
    for(int i = 0; i < n; ++i) {
        cin >> arr[i].w >> arr[i].s >> arr[i].v;
    }
    sort(arr.begin(), arr.end(), cmp);
    int res = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < N; ++j) {
            /*
            if(j+1 < N) {
                memo[j] = max(memo[j], memo[j+1]);
            }
            */
            if(j-arr[i].w >= 0 && j-arr[i].w <= arr[i].s) {
                memo[j-arr[i].w] = max(memo[j-arr[i].w], arr[i].v + memo[j]);
                res = max(res, memo[j-arr[i].w]);
            }
        }
    }
    cout << res << '\n';
}
 
 
 
 
 

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)

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

const int INF = 1<<30;

int main(){
  string s;cin>>s;
  int n=(int)s.size();
  ll ans=0LL, bw=0LL, cw=0LL;
  ll M=ll(1e9+7);
  ll pre=1LL;
  rep(i, n){
  	switch(s[i]){
      case 'A':
        bw=(bw+pre)%M;
        break;
      case 'B':
        cw=(cw+bw)%M;
        break;
      case 'C':
        ans=(ans+cw)%M;
        break;
      default:
        ans=(ans*3+cw)%M;
        cw=(3*cw+bw)%M;
        bw=(3*bw+pre)%M;
        pre=(pre*3)%M;
        break;
    }
    // cout<<bw<<" "<<cw<<" "<<ans<<endl;
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 512