akhauriyash/Code-Regression huggingface dataset:
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] x1y1x2y2 = br.readLine().split(" ");
		int x1 = Integer.parseInt(x1y1x2y2[0]);
		int y1 = Integer.parseInt(x1y1x2y2[1]);
		int x2 = Integer.parseInt(x1y1x2y2[2]);
		int y2 = Integer.parseInt(x1y1x2y2[3]);
		Point p1 = new Point(x1, y1);
		Point p2 = new Point(x2, y2);
		Square ruinedSquare = new Square(p1, p2);
		Square recoveredSquare = ruinedSquare.recover();
		System.out.println(recoveredSquare);
	}

}
class Square{
	private Point p1, p2, p3, p4;
	public Square(Point p1, Point p2) {
		this.p1 = p1;
		this.p2 = p2;
	}
	public Square() {} // default constructor
	
	public Square(Point p1, Point p2, Point p3, Point p4) {
		this.p1 = p1;	this.p2 = p2;	this.p3 = p3;	this.p4 = p4;
	}
	private Point nextPointOf(Point a, Point b) {
		int x = b.x - a.x;	int y = b.y - a.y;
		return new Point(b.x - y, b.y + x);
	}
	public Square recover() {
		this.p3 = this.nextPointOf(this.p1, this.p2);
		this.p4 = this.nextPointOf(this.p2, this.p3);
		Square recoveredSquare = new Square(this.p1, this.p2, this.p3, this.p4);
		return recoveredSquare;
	}
	@Override public String toString() {
		String s = String.format("%d %d %d %d\n", this.p3.x, this.p3.y, this.p4.x, this.p4.y);
		return s;
	}
}


Measured memory_bytes: 22612
#include <iostream>
#include <cstring>

using namespace std;

int main(){
	char c[2000];
	int t = 0;
	while(cin >> c){
		int idx = 0;
		if(c[strlen(c)-1] == ',' || c[strlen(c)-1] == '.') c[strlen(c)-1] = 0;
int l = strlen(c);

		if(3 <= l && l <= 6){
			if(t) cout << " ";
			cout << c;
			++t;
		}
	}
	cout << endl;

}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
int main() {
    int N,K,ans=0;
    string S;
	cin >> N >> K >> S;
	for (int i=0; i<S.length()-1; i++)
        if (S[i] == S[i+1]) ans++;
	cout << min(N-1, ans+2*K) << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long
float a[100005];
long long b[100005];
ll freq[26];
int main()
{
	string s;
	cin>>s;
	for(ll i=0;i<s.size();i++)
	{
		freq[s[i]-'A']++;
	}

	ll count1=0;
	for(ll i=0;i<26;i++)
	{
		if(freq[i]==2)
		{
			count1++;
		}
	}
	if(count1==2)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
}

Measured memory_bytes: 256
def test():
    n = int(input())
    count = 0
    a = []
    for i in range(1,n+1):
        if i % 2 != 0:
            for j in range(1,i+1):
                if i % j == 0:
                    count += 1
        a.append(count)
        count = 0
    print(a.count(8))


if __name__ == "__main__":
    test()


Measured memory_bytes: 2940
//
//  A.swift
//  AtCoder
//
//  Created by NakaiKoheiSub on 2020/07/14.
//  Copyright © 2020 NakaiKoheiSub. All rights reserved.
//

import Foundation

func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}
func main() {
    let As = readInts()
    if As.reduce(0){$0+$1} < 22{
        print("win")
    }else{
        print("bust")
    }
    
}
main()


Measured memory_bytes: 13640
a,b,c=map(int,input().split())
k=int(input())
for i in range(k):
    if a>=b:
        b=b*2
    else:
        if b>=c:
            c=c*2
        else:
            break

if a<b<c:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,a,even=0;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a;
    if(a%2==0) even++;
  }
  cout << pow(3ll,n)-pow(2ll,even) << endl;
  return 0;
}


Measured memory_bytes: 640
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Stack, Queue, PriorityQueue, Set}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N = in.next().toInt
  val S = in.next()

  //
  var _R = Vector[Int]()
  var _G = Vector[Int]()
  var _B = Vector[Int]()

  for (i <- 0 until N) {
    S(i) match {
      case 'R' => _R :+= i
      case 'G' => _G :+= i
      case 'B' => _B :+= i
    }
  }

  val R = _R.toArray
  val G = _G.toArray
  val B = _B.toSet

  var ans = R.length.toLong * G.length * _B.length

  for (_ri <- R; _gi <- G) {
    var ri = _ri
    var gi = _gi

    if (ri > gi) {
      val tmp = ri
      ri = gi
      gi = tmp
    }

    val hoge = gi - ri

    if (B(ri - hoge))
      ans -= 1

    if (B(gi + hoge))
      ans -= 1

    if (hoge % 2 == 0)
      if (B(ri + hoge/2))
        ans -= 1
  }

  println(ans)
}


class InputReader(stream: InputStream) {
  private[this] val reader = new BufferedReader(new InputStreamReader(stream))
  private[this] var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 57664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1 << 29;
const int MOD = 1000000007;

long long calcGcd(long long a, long long b) {
    // a > bにする
    if (a < b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    /* ユークリッドの互除法*/
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

long long calcLcm(long long a, long long b) {
    return a * b / calcGcd(a, b);
}

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;

    // cまたはdで割り切れるものの個数を求め、それをa以上b以下の整数の個数から引く
    // cまたはdで割り切れるものの個数はベン図より
    // cで割り切れるものの個数+dで割り切れるものの個数 - cでもdでも割り切れるものの個数で求められる
    // 1からbまでの範囲の個数から1からaまでの範囲の個数を引けば求める範囲の個数となる

    // a以上b以下の整数の個数
    long long all = b - a + 1;

    // c, d, cとdで割り切れるものの個数
    long long divided_c, divided_d, divided_lcm;

    // b以下の個数 - a未満の個数
    divided_c = b / c - (a - 1) / c;
    divided_d = b / d - (a - 1) / d;
    divided_lcm = b / calcLcm(c, d) - (a - 1) / calcLcm(c, d);

    long long ans = all - (divided_c + divided_d - divided_lcm);

    cout << ans << endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int k;
    int a, b;
    cin >> k >> a >> b;
    for (int i = a; i <= b; i++)
    {
        if (i % k == 0)
        {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
ll ans = 0;
const ll mo = 998244353;
const int MAX = 510000;
const int MOD = 998244353;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++)
  {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
long long COM(int n, int k){
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
ll n , a , b , k  ;
cin >> n >> a >> b >> k ;
COMinit();
rep(i,n+1){
  if((k-a*i)%b==0&&(k-a*i)/b>=0){
    ll re=(k-a*i)/b;
    ll bl=i;
    ans+=COM(n,re)*COM(n,bl);
    ans%=mo;
  }
}

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


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

ll keta(ll n) {
    ll res = 0;
    ll p = 1;
    while(n >= p) {
        p *= 10;
        res++;
    }
    return res;
}

int main() {
    int s, w;
    cin >> s >> w;
    if(s <= w)
        cout << "unsafe" << endl;
    else
        cout << "safe" << endl;
}


Measured memory_bytes: 3600
#include<stdio.h>

#define WHITE 0
#define BLACK 1
#define N 100
#define INF 1000000

int d[N];
int color[N];
int w[N][N];
int pi[N];


void difkstra(int,int);

int main()
{
    int i,n,j,k,c,u,v;
    
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            w[i][j]=-1;
        }
    }
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&u,&k);
        for(j=0;j<k;j++)
        {
            scanf("%d%d",&v,&c);
            w[u][v]=c;
        }
    }
    difkstra(n,0);
    
    for(i=0;i<n;i++)
    {
        printf("%d %d\n",i,d[i]);
    }
    
    return 0;
}

void difkstra(int n,int s)
{
    int i,j,u,v;
    int mincost;
    for(v=0; v<n; v++)
    {
        d[v] = INF;
        pi[v]=-1;
        color[v]=WHITE;
    }
    d[s]=0;
    
    while(1)
    {
        mincost=INF;
        for(i=0;i<n;i++)
        {
            if(color[i]!=BLACK && d[i]<mincost)
            {
                mincost=d[i];
                u=i;
            }
        }
        if(mincost==INF)
            break;
        
        color[u]=BLACK;
        
        for(v=0;v<n;v++)
        {
            if(color[v]!=BLACK && w[u][v]+d[u]<d[v] && w[u][v]>=0)
            {
                pi[v]=u;
                d[v]=w[u][v]+d[u];
            }
        }
        
        
    }
    
}

Measured memory_bytes: 640
#include <iostream>
#include <unordered_set>

using namespace std;

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

    unordered_set<string> set;

    for (int i = 0; i < N; ++i) {
        string str;
        cin >> str;
        set.insert(str);
    }

    cout << set.size() << endl;
    
    return 0;
}

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

using namespace std;

int main() {
	int a, b, c, cnt;

	cnt = 0;
	cin >> a >> b >> c;
	for (int i = a; i <= b; ++i) {
		if (c%i == 0) {
			++cnt;
		}
	}
	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 3132
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    mae = 0
    for i in a:
        if mae > i:
            ans += (mae - i)
            i = mae
        mae = i
    print(ans)



    
if __name__ == "__main__":
    main()

Measured memory_bytes: 32172
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

S = input()

while True:
    S = S[:-2]
    half = len(S) // 2
    if S[:half] == S[half:]:
        ans = len(S)
        break

print(ans)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll n;
ll a[200010];
ll ans[200010];
int main(){
	scanf("%lld",&n);
	rep(i,0,n)scanf("%lld",a+i+1);
	for(int i=n;i>0;i--){
		int flag=0;
		repp(j,i,n+1,i)flag^=ans[j];
		ans[i]=flag^a[i];
	}
	int cnt=0;
	rep(i,1,n+1)cnt+=ans[i];
	printf("%d\n",cnt);
	rep(i,1,n+1)if(ans[i])printf("%lld ",i);
	
}

Measured memory_bytes: 3968
#include<stdio.h>
int main()
{
    int X;
    input:
    scanf("%d",&X);
    if(X>=1&&X<=9)
    {
    if(X==7||X==5||X==3)
        printf("YES\n");
    else
        printf("NO\n");
    }
    else
        goto input;


    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,a,b;cin>>n>>a>>b;
  cout<<min(a,b)<<" ";
  cout<<max(0LL,a+b-n)<<endl;

  return 0;

}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  if n%2!=0:
    return 0

  a=5
  ans=0
  while True:
    if a*2>n:
      return ans
    ans+=n//(a*2)
    a*=5

# main()
print(main())


Measured memory_bytes: 5680
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

struct UF {
	vector<int> data;
	UF(int size) : data(size, -1) { }
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool find(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

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

    int n,m;cin>>n>>m;
    vector<ll> a(n);
    UF uf(n);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++){
      int x,y;cin>>x>>y;
      uf.unite(x,y);
    }
    if(m==n-1){
      cout<<0<<endl;
      return 0;
    }
    vector<priority_queue<ll,vector<ll>,greater<ll>>> qs(n);
    for(int i=0;i<n;i++){
      int par=uf.root(i);
      qs[par].push(a[i]);
    }
    bool f=true;
    ll res=0,cnt=0;
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    for(int i=0;i<n;i++){
      if(qs[i].empty()) continue;
      cnt++;
      res += qs[i].top(); qs[i].pop();
      while(!qs[i].empty()){
        pq.push(qs[i].top()); qs[i].pop();
      }
    }
    for(int i=0;i<cnt-2;i++){
      if(pq.empty()){
        f=false;
        break;
      }
      res += pq.top();pq.pop();
    }
    if(!f){
      cout<<"Impossible"<<endl;
      return 0;
    }
    cout<<res<<endl;
}


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

void mini(int x, int y){
  cout << min(x, y) << " " << max(x, y) << endl;
}

int main(){
  int x, y;

  while(1){
    cin >> x >> y;
    if(x == 0 && y == 0)  break;
    mini(x, y);
  }
}

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

void print_vec(vector<int> vec)
{
  cout << "[";
  for (int i = 0; i < vec.size(); i++)
  {
    cout << vec.at(i);
    if (i < vec.size() - 1)
    {
      cout << ", ";
    }
  }
  cout << "] size: " << vec.size() << endl;
}

int main()
{
  vector<int> sciences(4);
  vector<int> societies(2);

  rep(i, 4)
  {
    int score;
    cin >> score;
    sciences.at(i) = score;
  }
  rep(i, 2)
  {
    int score;
    cin >> score;
    societies.at(i) = score;
  }

  sort(all(sciences));
  reverse(all(sciences));
  sort(all(societies));
  reverse(all(societies));

  int science_score = 0;
  int society_score = societies.at(0);

  rep(i, 3)
  {
    science_score += sciences.at(i);
  }

  printf("%d\n", science_score + society_score);
}



Measured memory_bytes: 3212
from collections import deque
def main():
    k=int(input())
    if k<=9:
        return k
    q=deque()
    for i in range(1,10):
        q.append(i)
    Ans=list(range(1,10))
    cnt=9
    while cnt<k:
        s=q.popleft()
        d=s%10
        s*=10
        if d==0:
            q.append(s)
            q.append(s+1)
            Ans.append(s)
            Ans.append(s+1)
            cnt+=2
        elif d==9:
            q.append(s+8)
            q.append(s+9)
            Ans.append(s+8)
            Ans.append(s+9)
            cnt+=2
        else:
            V=[d-1,d,d+1]
            for v in V:
                q.append(s+v)
                Ans.append(s+v)
            cnt+=3
    return Ans[k-1]
    
if __name__=='__main__':
    print(main())

Measured memory_bytes: 46576
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000007)
	sc.Split(bufio.ScanWords)
	n := intScanner()
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, 2)
		a[i][1] = intScanner()
		a[i][0] = i
	}
	sort.Slice(a, func(i, j int) bool { return a[i][1] > a[j][1] })
	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, n+1-i)
	}
	ans := 0
	for i := 1; i < n+1; i++ {
		for l := 0; l < i+1; l++ {
			r := i - l
			lv, rv := -1, -1
			if l > 0 {
				lv = dp[l-1][r] + abs(a[i-1][0]-l+1)*a[i-1][1]
			}
			if r > 0 {
				rv = dp[l][r-1] + abs(n-r-a[i-1][0])*a[i-1][1]
			}
			dp[l][r] = larger(lv, rv)
			ans = larger(dp[l][r], ans)
		}
	}
	fmt.Println(ans)
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}


Measured memory_bytes: 19492
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long 
const long long inf=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;
#define FORR(x,arr) for(auto& x:arr)
#define ZERO(a) memset(a,0,sizeof(a))





//3111111111111111111111111111111
	
	int dp[3100][3100];

	
	void solve(){


		while(1){
		ini(n);
		if(n == 0)return;

		FOR(i,0,n+1)FOR(i1,0,n+1)dp[i][i1] = 0;
		vi morty(n);
		FOR(i,0,n){
			in(morty[i]);
		}
		FOR(i,2,n+1){
			FOR(i1,0,n){
				int l = i1;
				int r = i1+i;
				if(r>n)continue;
				
				if(abs(morty[l]-morty[r-1])<=1 and r-l-2 == dp[l+1][r-1])dp[l][r] = dp[l+1][r-1]+2;

				else{
					FOR(x,l+1,r){
						dp[l][r] = max(dp[l][r],dp[l][x]+dp[x][r]);
					}
				}
			}
		}
		out(dp[0][n]);
		}
		

		


		
		
	}























int32_t main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall 
	oneforall

	solve();
	


	return 0;
}



Measured memory_bytes: 5028
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define MOD 998244353
#define MAX_N 1111

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef pair<ll,ll> pll;

int main() {
  int n, a, b, p;
  scanf("%d %d %d", &n, &a, &b);
  int score[] = {0, 0, 0};
  int ans = n;
  for(int i = 0; i < n; ++i) {
    int p;
    scanf("%d", &p);
    if(p <= a) ++score[0];
    if(a < p && p <= b) ++score[1];
    if(b < p) ++score[2];
  }
  ans = min(score[0], min(score[1], score[2]));
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
s=list(input())
m=0
if s[0]=="0":
    for i in range(1,len(s),2):
        if s[i]=="0":
            m+=1
    for i in range(2,len(s),2):
        if s[i]=="1":
            m+=1
if s[0]=="1":
    for i in range(1,len(s),2):
        if s[i]=="1":
            m+=1
    for i in range(2,len(s),2):
        if s[i]=="0":
            m+=1
print(m)


Measured memory_bytes: 49392
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
template<class T> inline bool chmax(T& a, T b) { if(a < b){ a=b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if(a > b){ a=b; return 1; } return 0;}

int main(){
	ll n,m;
	cin >> n >> m;
	vector<pair<ll,ll>> city(m);
	vector<vector<ll>> pref(n);
	REP(i,m){
		cin >> city[i].first >> city[i].second;
		pref[city[i].first-1].push_back(city[i].second);
	}
	map<ll,ll> order;
	REP(i,n){
		sort(pref[i].begin(),pref[i].end());
		REP(j,pref[i].size()){
			order.insert(make_pair(pref[i][j],j+1));
		}
	}
	REP(i,m){
		string number = to_string(city[i].first);
		int digit = 6-(int)number.size();
		cout << string(digit,'0') << number;
		number = to_string(order[city[i].second]);
		digit = 6-(int)number.size();
		cout << string(digit,'0') << number << endl;
	}
	
	return 0;
}

Measured memory_bytes: 16264
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int h1, m1, h2, m2, k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;

  int hdiff = h2 - h1;

  if (hdiff == 0) {
    cout << m2 - m1 - k << endl;
  }

  if (hdiff != 0) {
    cout << hdiff * 60 + (m2 - m1) - k << endl;
  }
}

Measured memory_bytes: 3632
import sys
input = sys.stdin.readline
A,B,Q=map(int,input().split())
s=[(-1)*float("inf")]
for i in range(A):
    s.append(int(input()))
s.append(float("inf"))
t=[(-1)*float("inf")]
for i in range(B):
    t.append(int(input()))
t.append(float("inf"))
#print(s)
#print(t)
x=[0]*Q
for i in range(Q):
    x[i]=int(input())
from bisect import bisect_left as bl
for i in range(Q):
    ans=float("inf")
    sx=bl(s,x[i])
    tx=bl(t,x[i])
    #print(sx,tx)
    if s[sx]>=t[tx] :
        ans=min(s[sx]-x[i],ans)
    if s[sx]<t[tx] :
        ans=min(t[tx]-x[i],ans)
    #print("1",ans)
    if s[sx-1]>=t[tx-1] :
        ans=min(x[i]-t[tx-1],ans)
    if s[sx-1]<t[tx-1] :
        ans=min(x[i]-s[sx-1],ans)
    #print("2",ans,sx,tx)
    """
    print(s[sx]-x[i]+2*(x[i]-t[tx-1]))
    print(t[tx]-x[i]+2*(x[i]-s[sx-1]))"""

    ans=min(t[tx]-x[i]+2*(x[i]-s[sx-1]),s[sx]-x[i]+2*(x[i]-t[tx-1]),ans)
    ans=min(2*(t[tx]-x[i])+x[i]-s[sx-1],2*(s[sx]-x[i])+x[i]-t[tx-1],ans)

    print(ans)


Measured memory_bytes: 132956
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

	int n; cin >> n;
	vector<ll> a(n),l;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	for (int i = 0; i < n-1; i++) {
		if (a[i] == a[i + 1]) {
			l.push_back(a[i]);
			i++;
		}
	}
	sort(l.rbegin(), l.rend());
	if (l.size() < 2) cout << 0 << endl;
	else {
		cout << l[0] * l[1] << endl;
	}

}


Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
	ll n;
	cin >> n;
	deque<ll> a(n);
	rep(i,n)cin >> a[i];
	sort(ALL(a));
	deque<ll> b=a,c=a;
	
	//minから
	ll minans = 0;
	ll r=b.front(),l=b.front();
	b.pop_front();
	while(!b.empty())
	{
		minans+=abs(r-b.back());
		r=b.back();
		b.pop_back();
		if(b.empty())break;
		minans+=abs(l-b.back());
		l=b.back();
		b.pop_back();
		if(b.empty())break;
		minans+=abs(r-b.front());
		r = b.front();
		b.pop_front();
		if(b.empty())break;
		minans+=abs(l-b.front());
		l = b.front();
		b.pop_front();
		if(b.empty())break;
	}
	ll maxans = 0;
	r = c.back();
	l = c.back();
	c.pop_back();
	while(!c.empty())
	{
		maxans+=abs(r-c.front());
		r = c.front();
		c.pop_front();
		if(c.empty())break;
		maxans+=abs(l-c.front());
		l = c.front();
		c.pop_front();
		if(c.empty())break;
		maxans+=abs(r-c.back());
		r=c.back();
		c.pop_back();
		if(c.empty())break;
		maxans+=abs(l-c.back());
		l=c.back();
		c.pop_back();
		if(c.empty())break;
	}
	cout<<max(maxans,minans)<<endl;


	return 0;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
using vi=vector<long long>;
using vvi=vector<vector<long long>>;
using vc=vector<char>;
using vvc=vector<vector<char>>;
const int inf=1000000009;
void chmin(auto &a,auto b){if(b<a)a=b;}
void chmax(auto &a,auto b){if(a<b)a=b;}

int main(){
  double n,k,ans=0;cin>>n>>k;
  for(int i=1;i<=n;i++){
    double a=i;
    double c=1;
    while(a<k){
      a*=2;
      c*=0.5;
    }
    ans+=c;
  }
  ans/=n;
  cout<<fixed<<setprecision(10);
  cout<<ans<<endl;
}


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


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


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

void YN(bool ans){
    if(ans)cout<<"YES"<<endl;
    else cout <<"NO"<<endl;
    return;
}
int main(){
    ll A,B,V,W;
    cin>>A>>V;
    cin>>B>>W;
    ll T;
    cin>>T;
    bool ans = true;
    if(abs(A-B) <= (V-W) * T)ans = true;
    else ans = false;
    if(V-W<=0)ans = false;
    YN(ans);

    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T&v)
{fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0; return gcd(a, b, x, y);}
ll modpow(lll a,lll n,ll m){if(a==0)return a;lll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 2000;
int n, k, cnt, mk, mki;
vi e[N];
bool y[N], z;

void dfs(int a, int d){
  if(d > mk){
    mk = d;
    mki = a;
  }
  cnt++;
  y[a] = z;
  if(d >= k) return;
  for(int i: e[a]) if(y[i] != z) dfs(i, d+1);
}

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  FOR(i, 0, n-1){
    int a, b;
    cin >> a >> b;
    a--; b--;
    e[a].pb(b);
    e[b].pb(a);
  }
  int ans = iinf;
  FOR(i, 0, n)for(int j: e[i]){
    memset(y, false, sizeof(y));
    z = true;
    y[j] = true;
    mk = 0;
    dfs(i, 1);
    z = false;
    cnt = 0;
    dfs(mki, 0);
    mins(ans, n-cnt);
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
    int N, K;
    cin >> N >> K;
    int A[N];
    for(int i = 0; i < N; i++) cin >> A[i];
    for(int i = 0; i < min(50, K); i++){
        int B[N + 1];
        fill(B, B + N + 1, 0);
        for(int j = 0; j < N; j++){
            B[max(0, j - A[j])]++;
            B[min(N - 1, j + A[j]) + 1]--;
        }
        for(int j = 0; j < N; j++){
            if(j) A[j] = A[j - 1] + B[j];
            else A[j] = B[j];
        }
    }
    for(int i = 0; i < N; i++){
        if(i) cout << " ";
        cout << A[i];
    }
    return 0;
}

Measured memory_bytes: 5136
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <complex>
#include <bitset>
#include <numeric>
#include <random>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define SE second
#define FI first
#define DBG(a) cerr<<(a)<<endl;
#define debug(a) cerr<<#a <<' '<< a <<endl;
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;  typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
typedef pair<int,int>PI; typedef vector<int> VI;
const LL LINF=334ll<<53; const int INF=15<<26; const LL MOD=1E9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    LL ans=0;
    cin >> n;
    vector<PI> a;
    REP(i,n) {
        int tmp;
        cin >> tmp;
        a.push_back(MP(tmp,i));
    }
    sort(ALL(a));
    REP(i,n){
        if((abs(a[i].SE-i))%2==1)  ++ans;
    }
    cout << ans/2 <<endl;



    return 0;
}


Measured memory_bytes: 1400
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    private static Map<Character, Integer> map = new HashMap<Character, Integer>() {
        {
            put('M', 0);
            put('A', 1);
            put('R', 2);
            put('C', 3);
            put('H', 4);
        }
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];
        long[] cnt = new long[5];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
            char c = s[i].charAt(0);
            if (!map.containsKey(c)) {
                continue;
            }
            cnt[map.get(c)]++;
        }
        long sum = 0;
        for (int i = 0; i < map.size(); i++) {
            for (int j = i + 1; j < map.size(); j++) {
                for (int k = j + 1; k < map.size(); k++) {
                    sum += cnt[i] * cnt[j] * cnt[k];
                }
            }
        }
        System.out.println(sum);
    }

}


Measured memory_bytes: 51472
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main() {
    string s;
    cin >> s;

    string A = s.substr(0, 2);
    string B = s.substr(2, 2);

    int a = stoi(A);
    int b = stoi(B);

    if( (1 <= a && a <= 12) && (1 <= b && b <= 12) ) {
        cout << "AMBIGUOUS";
    }
    else if( (a < 1 || 12 < a) && (1 <= b && b <= 12) ) {
        cout << "YYMM";
    }
    else if( (1 <= a && a <= 12) && (b < 1 || 12 < b) ) {
        cout << "MMYY";
    }
    else {
        cout << "NA";
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
K ,N = map(int, input().split())
A = list(map(int, input().split()))

maxdis = K - A[-1] + A[0]

for i in range(N-1):
    dis = A[i+1] - A[i]
    if maxdis < dis:
        maxdis = dis
        
print (K-maxdis)


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

//cmdで g++ test.cpp とするとコンパイルできる

#define MOD 1000000007
typedef pair<int,int> pii;

int main() {
    int N,K;
    cin>>N>>K;
    int ans=0;
    while(N){
        N/=K;
        ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n, d, x;
    cin >> n >> d >> x;
    int ans = n;
    for(int i = 0; i < n; i++){
        int a; 
        cin >> a;
        ans += (d - 1) / a;
    }
    ans += x;
    cout << ans  << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#define INF 1000000000
#define LLINF 2000000000000000
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
// #define int long long

signed main(){
	int n;
	int d;
	cin >> n >> d;
	d = d*2+1;
	cout << (n+d-1)/d << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;

//計算量はElogV
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int n) : par(n, -1) { }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool merge(int x, int y) {//xの木とyの木を結合する
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {//sizeの取得
        return -par[root(x)];
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

struct Edge{
    int a,b,cost;
    bool operator<(const Edge& o) const{
        return cost < o.cost;//costの大小で順序を定義
    }
};

struct Graph{
    int n;
    vector<Edge> es; //辺の集合

    //クラスカル法で無向最小全域木のコストの和を計算する
    //グラフが非連結の場合最小全域森のコストの和
    int kruskal(){
        sort(es.begin(),es.end());//コストが小さい順に採用
        UnionFind uf(n);
        int min_cost = 0;
        rep(ei,es.size()){
            Edge& e = es[ei];
            if(!uf.same(e.a,e.b)){//辺を追加して閉路が出来なければ辺を採用
                min_cost += e.cost;
                uf.merge(e.a,e.b);
            }
        }
        return min_cost;
    }


};

Graph input_graph(){
    Graph g;
    int m;
    cin >> g.n >> m;
    rep(i,m){
        Edge e;
        cin >> e.a >> e.b >> e.cost;
        g.es.push_back(e);
    }
    return g;
}

Graph input_matrix(){
    Graph g;
    cin >> g.n;
    vector<vector<int> > field(g.n,vector<int>(g.n));
    rep(i,g.n)rep(j,g.n)cin>>field[i][j];
    rep(i,g.n){
        rep(j,g.n){
            if(i<=j)continue;
            Edge e;
            e.a = i;
            e.b = j;
            e.cost = field[i][j];
            if(e.cost==-1)continue;
            g.es.push_back(e);
        }
    }
    return g;
}

int main(){
    Graph g;
    cin >> g.n;
    int n = g.n;
    vector<P>x(n),y(n);
    rep(i,n){
        ll a,b;
        cin >> a >> b;
        x[i] = {a,i};
        y[i] = {b,i};
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    rep(i,n-1){
        Edge e;
        e.a = x[i].second;
        e.b = x[i+1].second;
        e.cost = x[i+1].first - x[i].first;
        g.es.push_back(e);
    }
    rep(i,n-1){
        Edge e;
        e.a = y[i].second;
        e.b = y[i+1].second;
        e.cost = y[i+1].first - y[i].first;
        g.es.push_back(e);
    }
    cout << g.kruskal() << endl;
    return 0;
}

Measured memory_bytes: 8052
n, m = map(int, input().split())
mod = 10**9 + 7
def setfact(l, mod):
    global fact
    global ifact
    fact = [1]
    for i in range(1, l+1):
        fact.append(fact[-1]*i%mod)
    ifact = [0] * (l+1)
    ifact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(l, 0, -1):
        ifact[i-1] = ifact[i] * i %mod
def comb(n, m, mod):
    global fact
    global ifact
    return fact[n]*ifact[n-m]*ifact[m]%mod
def p(n, m, mod):
    global fact
    global ifact
    return fact[n]*ifact[n-m]%mod
ans = 0
setfact(m, mod)
for k in range(n+1):
    ans += p(m-k, n-k, mod)*comb(n, k, mod) * (-1)**k
    ans %= mod
    if ans < 0:
        ans += mod
ans *= p(m, n, mod)
ans %= mod
print(ans)

Measured memory_bytes: 122240
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

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

  if(a+b == c) {
    cout << "Yes" << endl;
    return 0;
  }
  if(b+c == a) {
    cout << "Yes" << endl;
    return 0;
  }
  if(c+a == b) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl; 
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 14 19:11:44 2018

@author: maezawa
"""
infinity = 2*10**9

n = int(input())
adj = [[] for _ in range(n)]

for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(2,2+2*k,2):
        adj[u].append([ain[i],ain[i+1]])
    #print(*adj[u])

color = [0]*n
d = [infinity for _ in range(n)]
p = [0]*n
p[0] = -1
d[0] = 0

def dyk(s):
    cnt = 1
    cur = s
    candidates = set() # remaining nodes
    while True:
        for i, w in adj[cur]:
            if color[i] == 2:
                continue
            if d[i] > d[cur] + w:
                d[i] = d[cur] + w
                color[i] = 1
            candidates.add(i)
        min_d = infinity
        for j in candidates:
            if min_d > d[j]:
                min_node = j
                min_d = d[j]
        candidates.remove(min_node)
        p[min_node] = cur
        color[cur] = 2
        cur = min_node
        cnt += 1
        #print(cur, d)
        #print(candidates)
        if cnt == n:
            break
    return

dyk(0)
for i in range(n):
    print(i, d[i])
    
#print(*p, sep = '\n')

                    
                    


Measured memory_bytes: 76600
import Data.List
import Data.Char
import Data.Maybe
import qualified Data.ByteString.Char8 as BS8

dig_impl 0 r = r
dig_impl n r = dig_impl (div n 10) (r + 1)
dig n = dig_impl n 0

main :: IO ()
main = do
    n <- fst . fromJust . BS8.readInteger <$> BS8.getLine

    print $ length [x | x <- [1..n], (dig x) `mod` 2 == 1]


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
int a[100005];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n-1;i++){
		if(a[i+1]>a[i])      
		    a[i+1]-=1;
	}
	int f=1;
	for(int i=0;i<n-1;i++){
		if(a[i]>a[i+1]){
	    	f=0;
		    break;
		}
	}
	if(f)
	    printf("Yes\n");
	else
	    printf("No\n");
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
int main(){
    int n,ans=0;
    string s;
    cin>>n>>s;
    int dp3[1000],dp1[10],dp2[100];
    for(int i=0;i<1000;i++)dp3[i]=false;
    for(int i=0;i<10;i++)dp1[i]=false;
    for(int i=0;i<100;i++)dp2[i]=false;

    for(int i=0;i<n;i++){
        int c=s[i]-'0';
        for(int j=0;j<100;j++){
            if(dp2[j])dp3[j*10+c]=true;
        }
        for(int j=0;j<10;j++){
            if(dp1[j])dp2[j*10+c]=true;
        }
        dp1[c]=true;
    }
    for(int i=0;i<1000;i++)ans+=dp3[i];
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define     __        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define     pi        acos(-1)
#define     ll        long long int
#define     fopen     freopen("input.txt","r",stdin)
#define     fwrite    freopen("output.txt","w",stdout)
#define     f0(n)     for(int i=0;i<n;i++)
#define     mem(a)    memset(a,0,sizeof(a))
#define     mems(a)   memset(a,-1,sizeof(a))

int main()
{
    __
    //fopen;
    //fwrite;
    int n=1111;
    string s;
    cin>>s;
    for(int i=0;i<s.size()-2;i++)
    {

          int a=(s[i]-48)*100 + ((s[i+1]-48)*10) + (s[i+2]-48);
           n=min(n,abs(753-a));
    }
    cout<<n;
    return 0;
}


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

#define pb push_back
#define eb emplace_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> tiii;

vector<tiii> v;
int n; 

ll memo[1007][10007];



ll solve(int p, int w) {
	if(w >= 10007) return 0;
	if(p == n) {
		return 0;
	}

	ll & st = memo[p][w];

	if(st == -1) {
		int we, s, x;
		tie(we, s, x) = v[p];
		st = max(
			s >= w? x + solve(p+1, w + we) : (ll) -1e15,
			solve(p+1, w)
		);
	}
	return st;
}

int main() {
	memset(memo, -1, sizeof memo);
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n;

	for(int i = 0; i < n; i++) {
		int w, s, x; cin >> w >> s >> x;
		v.eb(w, s, x);
	}

	sort(v.rbegin(), v.rend(), [&](tiii aux1, tiii aux2) {
		int w1, s1, x1; tie(w1, s1, x1) = aux1;
		int w2, s2, x2; tie(w2, s2, x2) = aux2;

		return w1 + s1 > w2 + s2;
	});	

	cout << solve(0, 0) << '\n';
}

Measured memory_bytes: 79104
a=[]
for i in input().split():
	if i=='+':
		a[len(a)-2]=int(a[len(a)-2])+int(a[len(a)-1])
		a.pop()
	elif i=='-':
		a[len(a)-2]=int(a[len(a)-2])-int(a[len(a)-1])
		a.pop()
	elif i=='*':
		a[len(a)-2]=int(a[len(a)-2])*int(a[len(a)-1])
		a.pop()
	else :
		a.append(i)

print(a[0])


Measured memory_bytes: 5604
#include<bits/stdc++.h>
typedef long long ll;
ll n;
std::vector<int>ans,A,B;int y=1;
void solve(ll x){
	if(x==1){A=B={1};return;}
	if(x&1)solve(x>>1),++y,A.push_back(y);
		else solve(x-1),++y,A.insert(A.begin(),y);B.push_back(y);
}
int main(){
	scanf("%lld",&n);
	solve(n);
	ans=A;ans.insert(ans.end(),B.begin(),B.end());
	printf("%d\n",ans.size());
	for(int i:ans)printf("%d ",i);puts("");
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a + b == c + d) {
      cout << "Balanced" << '\n';
    } else if (a + b > c + d) {
      cout << "Left" << '\n';
    } else {
      cout << "Right" << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) a.begin(), a.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
const int inf = 1000000005;

int main(){

    int Q;
    cin >> Q;

    ll ans = 0;
    multiset<int> lf, ri;
    lf.insert(-inf);
    lf.insert(-inf);
    ri.insert(inf);
    ri.insert(inf);

    rep(loop, Q){
        int q;
        cin >> q;
        if(q == 1){
            int a, b;
            cin >> a >> b;
            ans += b;
            if(*(--lf.end()) > a){
                lf.insert(a);
                lf.insert(a);
                int en = *(--lf.end());
                lf.erase(--lf.end(), lf.end());
                ri.insert(en);
                ans += *ri.begin() - a;
            } else if(a > *ri.begin()){
                ri.insert(a);
                ri.insert(a);
                int fi = *ri.begin();
                ri.erase(ri.begin(), ++ri.begin());
                lf.insert(fi);
                ans += a - *(--lf.end());
            } else {
                lf.insert(a);
                ri.insert(a);
            }
        } else {
            int x = *(--lf.end());
            cout << x << ' ' << ans << endl;
        }
    }
    
}

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

int main() {
    long n; cin >>n;
    map<int, int> p;

    while (n%2 == 0) {n/=2; p[2]+=1;}
    int i = 3;
    while (n!=1 || n>=i) {
        if (pow(n,0.5)<i) {p[n]++; break;}
        if (n%i == 0) {
            p[i]++;
            n/=i;
        }
        else {
            i += 2;
        }
    }

    int ans = 0;
    for (auto i: p) {
        int k = 1;
        while (i.second >= k) {
            ans++;
            i.second -= k;
            k++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4104
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int l[200010];
int main()
{
    int n,k;
    cin>>k>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<n;i++)  l[i]=a[i+1]-a[i];
	l[n]=k-a[n]+a[1];
	int maxx=-1;
	for(int i=1;i<=n;i++)
	{
		if(l[i]>maxx)   maxx=l[i];
	}
	cout<<k-maxx<<endl;
    return 0;
}

Measured memory_bytes: 5280