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

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

  vector<bool> a(n, false);
  for (int i = 0; i < k; i++)
  {
    int d;
    cin >> d;
    for (int j = 0; j < d; j++)
    {
      int tmp;
      cin >> tmp;
      a[tmp - 1] = true;
    }
  }

  int r = 0;
  for (int i = 0; i < n; i++)
  {
    if (!a[i])
    {
      r++;
    }
  }
  cout << r << endl;
}


Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {

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

		if (n.indexOf("9") != -1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

		sc.close();
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
    #define intt long long
    #define in(a) scanf("%d",&a)
    #define out(a) printf("%d\n",a)

    using namespace std;

    int main()
    {
        long double n , m , d;
        cin>>n>>m>>d;
        if (d == 0)cout<<fixed<<setprecision(15)<<(m - 1) / n<<endl;
        else cout<<fixed<<setprecision(15)<<(m - 1) / n * 2 * (n - d) / n<<endl;
        return 0;
    }

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

int main(){
    double a,b,c;
    cin >> a >> b >> c;
    double PI = acos(-1);
    c = c*PI/180;
    double S = a*b*sin(c)/2;
    double L = sqrt(a*a + b*b -2*a*b*cos(c)) + a + b;
    double h = S / a * 2;
    printf("%lf\n%lf\n%lf\n", S, L, h);
    return 0;
}


Measured memory_bytes: 3504
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>
#include <map>
#include <numeric>
#include <functional>
#include <utility>

using namespace std;

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

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

  bool rev = false;
  for (int i = 0; i < q; ++i) {
    int t;
    cin >> t;
    if (t == 1) {
      rev = rev ? false : true;
    }
    else if (t == 2) {
      int f;
      char c;
      cin >> f >> c;

      if (rev) {
        f = (f == 1 ? 2 : 1);
      }

      if (f == 1) {
        string ss;
        ss.push_back(c);
        s.insert(0, ss);
      }
      else if (f == 2) {
        s.push_back(c);
      }
    }
  }

  if (rev) {
    reverse(s.begin(), s.end());
  }

  cout << s << endl;

  return 0;
}


Measured memory_bytes: 900
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}

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


  val N = in.next().toInt
  val A = new Array[Int](N+1)
  val B = new Array[Int](N+1)
  for (i <- 1 to N) {
    val a, b = in.next().toInt
    A(i) = a; B(i) = b
  }


  //
  val X = new Array[(Int, Int)](N)
  for (i <- 0 until N) {
    X(i) = (Math.abs(A(i+1) + B(i+1)), i+1)
  }

  val Y = X.sorted.reverse

  var a = 0L
  var b = 0L
  for (i <- 0 until N) {
    val (_, ind) = Y(i)
    if(i % 2 == 0)
      a += A(ind)
    else
      b += B(ind)
  }

  println(a - b)
}


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



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

int main(){
  string w;
  cin >> w;
  int n = w.size();

  map<char,int> mp;
  for (int i = 0; i < n; i++)
  {
    mp[w[i]]++;
  }

  bool flg = true;
  for(auto p:mp){
    if(p.second%2==1) flg = false;
  }
  if(flg) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
N = int(input())
Ss = []
d = 97
for i in range(N):
    Ss.append(input())
from collections import Counter
counter = [float('inf') for i in range(26)]
for S in Ss:
    D = Counter(S)
    for key in range(d,d+26):
        counter[key-d] = min(D[chr(key)],counter[key-d])
ans = ''
for i,e in enumerate(counter):
    if e == float('inf'):
        continue
    for j in range(e):
        ans += chr(i+d)
print(ans)

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

int N, M;
vector<vector<int> > adj;
queue<int> q;
vector<int> vis;

int main() {
    scanf("%d %d", &N, &M);

    adj.resize(N + M);
    for(int i = 0; i < N; i++) {
        int K; scanf("%d", &K);
        for(int j = 0; j < K; j++) {
            int L; scanf("%d", &L);
            L--;
            adj[i].push_back(N + L);
            adj[N + L].push_back(i);
        }
    }
    vis = vector<int>(N + M, 0);
    q.push(0);
    vis[0] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if(!vis[v]) {
                q.push(v);
                vis[v] = 1;
            }
        }
    }

    for(int i = 0; i < N; i++) if(!vis[i]) {
        cout << "NO";
        return 0;
    }
    cout << "YES";
}


Measured memory_bytes: 9592
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var s = input.ReadLine();
        var n = s.Length;
        
        if(n == 1) {
            return s[0];
        }

        long y = (n-1) * 9 + (s[0]-'0')-1;

        long y2 = s.ToCharArray().Sum(x=>(long)(x-'0'));

        return Math.Max(y, y2);
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }

}


Measured memory_bytes: 26216
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
	static int n;
	static int m;
	static int[] cs;
	static int[] minCounts;

	static void Main(string[] args)
	{
		string[] first = Console.ReadLine().Split();

		n = int.Parse(first[0]);
		m = int.Parse(first[1]);

		cs = Console.ReadLine().Split().Select(str => int.Parse(str)).ToArray();

		minCounts = new int[50001];

		// コイン1枚で実現できる金額には枚数1を入れておく
		for (int ci = 0; ci < m; ci++)
		{
			minCounts[cs[ci]] = 1;
		}

		// 1から順番に辿る
		for (int i = 1; i <= n; i++)
		{
			minCounts[i] = GetMinCounts(i);
		}
		System.Console.WriteLine(minCounts[n]);
	}

	// Kを実現する最小コイン枚数を返す
	static int GetMinCounts(int k)
	{
		// 記録済み
		if (minCounts[k] > 0) return minCounts[k];

		// 頭と後ろからの組み合わせで最小値を計算
		int min = k;
		for (int j = 1; j < k; j++)
		{
			if (k - j < j) return min;
			int current = minCounts[k - j] + minCounts[j];
			if (current < min) min = current;
		}
		return min;
	}
}



Measured memory_bytes: 9780
import java.util.Scanner;

class Node {
	int i, id, left, right, parent = -1, sibling = -1, degree = 0, depth = 0, height = 0;

	public Node(int Id, int l, int r) {
		id = Id;
		left = l;
		right = r;
	}
}

public class Main {
	static Node[] node = new Node[100000];

	public static void preorder(int i) {
		System.out.print(" " + node[i].id);
		if (node[i].left != -1) {
			preorder(node[i].left);
		}
		if (node[i].right != -1) {
			preorder(node[i].right);
		}
	}

	public static void inorder(int i) {
		if (node[i].left != -1) {
			inorder(node[i].left);
			}
		System.out.print(" " + node[i].id);
		if (node[i].right != -1) {
			inorder(node[i].right);
		}
	}

	public static void postorder(int i) {
		if (node[i].left != -1) {
			postorder(node[i].left);
			}
		if (node[i].right != -1) {
			postorder(node[i].right);
		}
		System.out.print(" "+node[i].id);
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int i, n, id, l, r;
		n = scan.nextInt();
		for (i = 0; i < n; i++) {
			id = scan.nextInt();
			l = scan.nextInt();
			r = scan.nextInt();
			node[id] = new Node(id, l, r);
		}
		for (i = 0; i < n; i++) {
			if (node[i].left != -1) {
				node[node[i].left].parent = node[i].id;
				node[node[i].left].sibling = node[i].right;
			}
			if (node[i].right != -1) {
				node[node[i].right].parent = node[i].id;
				node[node[i].right].sibling = node[i].left;
			}
		}
		for (i = 0; i < n; i++) {
			if (node[i].parent == -1) {
				System.out.println("Preorder");
				preorder(i);
				System.out.println("\nInorder");
				inorder(i);
				System.out.println("\nPostorder");
				postorder(i);
				System.out.println("");
				break;
			}
		}
		scan.close();
	}
}


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

int main(){
	int n; cin>>n;
	vector<int> v;
	rep(i,n){
		int a; cin>>a;
		if(a%2==0) v.push_back(a);
	}
	if(v.size()==0){cout<<0<<endl; return 0;}
	int ans=0;
	for(int i=0; i<v.size(); i++){
		int cnt=0;
		while(v[i]%2!=1){
			v[i]/=2;
			cnt++;
		}
		ans+=cnt;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3740
function PriorityQueue( comp )
{
  this.list = [];
  this.comp = comp;
}

PriorityQueue.prototype.enq = function( x )
{
  this.list.push( x );
  var i = this.list.length-1;

  while( i > 0 )
  {
    var p = Math.floor((i-1)/2);
    
    if( this.comp( this.list[p], x ) <= 0 )
      break;

    this.list[i] = this.list[p];
    i = p;
  }

  if( this.list.length > 0 )
    this.list[i] = x;
};

PriorityQueue.prototype.deq = function() {
  var min = this.peek();
  var root = this.list[this.list.length-1];
  this.list.splice( this.list.length-1, 1 );

  var i = 0;

  while( i*2+1 < this.list.length )
  {
    var a = i*2+1, b = i*2+2, c = b < this.list.length && this.comp(this.list[b], this.list[a]) < 0 ? b : a;

    if( this.comp( this.list[c], root ) >= 0 )
      break;

    this.list[i] = this.list[c];
    i = c;
  }

  if( this.list.length > 0 )
    this.list[i] = root;

  return min;
};

PriorityQueue.prototype.peek = function() {
  return this.list.length == 0 ? undefined : this.list[0];
};

PriorityQueue.prototype.size = function() {
  return this.list.length;
};

PriorityQueue.prototype.isEmpty = function() {
  return this.size() == 0;
};

const MAX_V = 100000;
const INF = Number.POSITIVE_INFINITY/4;
var V, E, r;
var G;
var d;

function dijkstra( s )
{
  var pque = new PriorityQueue(function(a,b) { 
    if( a.dist != b.dist )
      return a.dist-b.dist;

    return a.v-b.v;
  });
  d[s] = 0;
  pque.enq( { dist: 0, v: s } );

  while( !pque.isEmpty() )
  {
    var p = pque.deq();

    if( d[p.v] < p.dist )
      continue;

    for( var i = 0; i < G[p.v].length; ++i )
    {
      var e = G[p.v][i];

      if( d[e.to] > d[p.v] + e.cost )
      {
        d[e.to] = d[p.v] + e.cost;
        pque.enq( { dist: d[e.to], v: e.to } );
      }
    }
  }
}

(function main( input )
{
  var lines = input.trim().split('\n');
  var fst = true;

  for( var j = 0; j < lines.length; ++j )
  {
    if( lines[j] == '' )
      break;
    
    var words = lines[j].trim().split(' ').map(Number);

    if( fst )
    {
      V = words[0];
      E = words[1];
      r = words[2];

      G = [];
      d = [];

      for( var i = 0; i < V; ++i )
        G[i] = [], d[i] = INF;
    }
    else
      G[words[0]].push( { to: words[1], cost: words[2] } );

    fst = false;
  }

  dijkstra( r );

  d.forEach( function(v) { console.log( v == INF ? "INF" : v ) } );
})( require('fs').readFileSync( '/dev/stdin', 'utf8' ) );

Measured memory_bytes: 150564
#include <cstdio>

int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    
    if((a+b)%2 == 0)
    {
        printf("%d",(a+b)/2);
    }
    else if((a+b)%2 != 0)
    {
        printf("%d",((a+b)/2)+1);
    }
}

Measured memory_bytes: 1732
N, A = list(map(int,input().split()))
x = list(map(int,input().split()))
dp = [[0 for k in range(1+50*N)] for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
  for j in range(i, -1, -1):
    for k in range(1+50*j):
      dp[j+1][k+x[i]] += dp[j][k]
print(sum([dp[j][A*j] for j in range(1, N+1)]))

Measured memory_bytes: 4724
s = input()
t = input()
s_li = list(s)
t_li = list(t)

if not len(s_li) == len(t_li) :
    print("No")
    exit()

buf = s_li

for i in range(len(s_li)):
    s_join = "".join(s_li)
    buf = []
    if t == s_join:
        print("Yes")
        exit()
    for j in range(len(s_li)):
        if j == 0 :
            buf.append(s_li[len(s_li) - 1])
        else :
            buf.append(s_li[j - 1])
    s_li = buf

print("No")

Measured memory_bytes: 3188
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeSet;

class ball implements Comparable<ball>{
	int num, id;
	public ball(int n, int i) {
		num = n; id = i;
	}
	public int compareTo(ball o) {
		if(num == o.num) return id - o.id;
		return num - o.num;
	}
}
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K = sc.nextInt();
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i = 0; i < N; i++) {
			int A = sc.nextInt();
			if(map.containsKey(A)) map.put(A, map.get(A) + 1);
			else map.put(A, 1);
		}
		/* 本質 */
		int ans = 0;
		TreeSet<ball> balls = new TreeSet<ball>();
		for(Entry<Integer, Integer> e : map.entrySet()) {
			balls.add(new ball(e.getValue(), e.getKey()));
		}
		while(balls.size() > K) {
			ans += balls.pollFirst().num;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 102988
n=int(input())
t,x,y=0,0,0
ans='Yes'
for i in range(n):
    s,a,b=map(int,input().split())
    if abs(x-a)+abs(y-b)<=s-t and (a-x+y-b-s+t)%2==0:
        0
    else:
        ans='No'
        break
    t,x,y=s,a,b

print(ans)

Measured memory_bytes: 45928
n,k = map(int,input().split())
p = input().split(' ')
# print(p)
ans = 0

start,end = 0,k - 1
cur = 0
for i in range(k):
    cur += (int(p[i]) + 1)/2
ans = max(ans,cur)
for i in range (k,n):
    cur += ((int(p[i]) + 1)/2)
    cur -= ((int(p[i - k]) + 1)/2)
    ans = max(ans,cur)
print(ans)

Measured memory_bytes: 17316
import heapq

def dijkstra(s, G):
    inf = 1145141919810893
    dist = [inf] * n
    dist[s] = 0
    c = [0] * n
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

n, m, s, t = map(int, input().split())
yen = 10 ** 15
G = [[] for _ in range(n)]
H = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, a])
    G[v].append([u, a])
    H[u].append([v, b])
    H[v].append([u, b])
dist1 = dijkstra(s - 1, G)
dist2 = dijkstra(t - 1, H)
ans = [0] * n
ans[n - 1] = yen - (dist1[n - 1] + dist2[n - 1])
for i in range(n - 2, -1, -1):
    ans[i] = max(ans[i + 1], yen - (dist1[i] + dist2[i]))
for i in ans:
    print(i)

Measured memory_bytes: 127264
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

signed main(){
	int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
	printf("%d\n",max(0,min(b,d)-max(a,c)));
}


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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()
#define sortAl(v) sort(all(v))
#define sortAlr(v)          \
  sort(v.begin(), v.end()); \
  reverse(v.begin(), v.end())

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T &a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T &a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
#define INF LLONG_MAX

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

  string s;
  cin >> s;

  ll n = s.size();

  for (int i = 1; i < n; i += 2) {
    if (s[i] == '0') {
      s[i] = '1';
    } else {
      s[i] = '0';
    }
  }

  REP(i, s.size()) {
    if (s[i - 1] == s[i]) {
      s.erase(s.begin() + i - 1, s.begin() + i + 1);
      i -= 2;
      if (i < 0) {
        i = 0;
      }
    }
  }

  cout << n - s.size() << endl;

  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	string str;
	cin>>str;
	if(str.length()==2){
		cout<<str<<endl;
	}else{
		reverse(str.begin(),str.end());
		cout<<str<<endl;
	}
}

Measured memory_bytes: 256
package main

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

// fmt.Scan is high cost
func main() {
	var sc = bufio.NewScanner(os.Stdin)
	buf := make([]byte, 1024)
	sc.Buffer(buf, 200001)
	var s string
	sc.Scan()
	s = sc.Text()
	a, z := -1, -1
	for i := 0; i < len(s); i++ {
		if a == -1 && s[i] == 'A' {
			a = i
		}
		if s[i] == 'Z' {
			z = i
		}
	}
	fmt.Println(z - a + 1)
}


Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <math.h>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)

typedef long long ll;
typedef long long int lli;

char op1 = '+';
char op2 = '-';
string equal7 = "=7";

int calc(int A, int B, int C, int D) {
    if (A + B + C + D == 7) {
        cout << A << op1 << B << op1 << C << op1 << D<< equal7 << endl;
    } else if (A - B + C + D == 7) {
        cout << A << op2 << B << op1 << C << op1 << D<< equal7 << endl;
    } else if (A - B - C + D == 7) {
        cout << A << op2 << B << op2 << C << op1 << D<< equal7 << endl;
    } else if (A - B - C - D == 7) {
        cout << A << op2 << B << op2 << C << op2 << D<< equal7 << endl;
    } else if (A + B - C + D == 7) {
        cout << A << op1 << B << op2 << C << op1 << D<< equal7 << endl;
    } else if (A + B - C - D == 7) {
        cout << A << op1 << B << op2 << C << op2 << D<< equal7 << endl;
    } else if (A + B + C - D == 7) {
        cout << A << op1 << B << op1 << C << op2 << D<< equal7 << endl;
    } else if (A - B + C - D == 7) {
        cout << A << op2 << B << op1 << C << op2 << D<< equal7 << endl;
    }
    return 0;
}

int main() {
    int N;
    cin >> N;
    char op1 = '+';
    char op2 = '-';
    int A = N/1000;
    N = N - A*1000;
    int B = N/100;
    N = N - B*100;
    int C = N/10;
    N = N - C*10;
    int D = N;

    calc(A,B,C,D);
    

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip> //setprecision()
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
using ll = long long;
using namespace std;

double Mcos(double k){return cos(k*atan(1.0)*4/180);}

void monmo(){
    
}

int main() {
    int n;
    string s;
    cin>>n;
    if(n>=30){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
}


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

using namespace std;

int main(void)
{
  int n,m; cin>>n>>m;
  vector<int> a(n);
  int sum=0;
  int count=0;
  for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; }
  
  double tmp=sum*(1.0/(4.0*m));
  
  for(int i=0;i<n;i++){
    double buf=a[i];
    if(buf>=tmp){count++;}
  }
    
  if(count>=m){puts("Yes");}
  else{puts("No");}

  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
 
   int N = sc.nextInt();
   int M = sc.nextInt();
   int[] a = new int[M+1];
   for(int i=0;i<M;i++) a[i] = sc.nextInt();
   long[] dp = new long[N+1];
   int count =0;
   if(N==1) System.out.println(1);
   else
   {

   dp[1]=1;
   if(a[count]==1)
   {
     dp[1]=0;
     count++;
   }
   dp[2]=1+dp[1];
   if(a[count]==2)
   {
     dp[2]=0;
     count++;
   }
   for(int i=3;i<=N;i++)
   {
     if(a[count]==i) 
     {
       dp[i]=0;
       count++;
     }
     else dp[i]=(dp[i-1]+dp[i-2])%1000000007;
   }
   System.out.println(dp[N]);
   }
 }
}

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

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

struct int_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash {
    size_t operator()(pair<int, int> x) const {
        return int_hash{}(x.first) ^ (int_hash{}(x.second) << 16);
    }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e7;
const int MX = 100001; //check the limits, dummy

pair<int, int> getMLSB(int x) {
    int lsb = x % 10;
    int msb = 0;
    while(x) {
        msb = x % 10;
        x /= 10;
    }
    return {msb, lsb};
}

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

    int n; cin >> n;
    vector<vector<ll>> v(10, vector<ll>(10, 0));
    for(int i = 1; i <= n; i++) {
        pair<int, int> p = getMLSB(i);
        v[p.first][p.second]++;
    }

    ll ans = 0;
    for(int i = 1; i < 10; i++)
        for(int j = 0; j < 10; j++)
            ans += v[i][j] * v[j][i];

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
    os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m;

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    cin >> n;
    vi d(n);
    REP(i, n) cin >> d[i];
    ll l = 0, r = 0, sum = 0, ans = 0;
    while(r < n) {
        while (sum & d[r]) sum ^= d[l ++];
        sum ^= d[r ++];
        ans += r - l;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, a, b) for(int i=int(a); i<=int(b); ++i)
#define irep(i, a, b) for(int i=int(a); i>=int(b); --i)
#define replr(i, a, b) rep(i, a, (b)-1)
#define reprl(i, a, b) irep(i, (b)-1, a)
#define repn(i, n) rep(i, 0, (n)-1)
#define irepn(i, n) irep(i, (n)-1, 0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<string> VS;
template<class T, class S> ostream& operator<<(ostream& os, const pair<T, S>& v) { return os<<"("<<v.first<<", "<<v.second<<")"; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"["; repn(i, sz(v)) { if(i) os<<", "; os<<v[i]; } return os<<"]"; }
template<class T> bool setmax(T &_a, T _b) { if(_b>_a) { _a=_b; return true; } return false; }
template<class T> bool setmin(T &_a, T _b) { if(_b<_a) { _a=_b; return true; } return false; }
template<class T> T gcd(T _a, T _b) { return _b==0?_a:gcd(_b,_a%_b); }

int main() {
    int n, m; scanf("%d%d", &n,&m);
    VPI a;
    repn(i, n+m) {
        int x; scanf("%d", &x);
        a.pb(mp(x, i<n?0:1));
    }
    sort(all(a));
    LL ans=0;
    for(const auto& p: a) {
        if(p.se==0) {
            ans+=LL(p.fi)*LL(m+1);
            --n;
        } else {
            ans+=LL(p.fi)*LL(n+1);
            --m;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2420
<?php
fscanf(STDIN, "%d", $N);
$H = explode(" ", trim(fgets(STDIN)));
$mmax = 0;
$ans = 0;
for ($i = 0; $i < $N; $i++) {
    if ($mmax <= $H[$i]) {
        $mmax = $H[$i];
        $ans++;
    }
}
echo $ans;


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

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

using LL = long long int;
using LD = long double;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }

bool solve(int a, int b, int c) {
	for (int i = 1; i < 10000; i++) {
		if ((a * i) % b == c) {
			return true;
		}
	}
	return false;
}

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

	int a, b, c;
	cin >> a >> b >> c;

	cout << (solve(a, b, c) ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
grid = []
for i in range(3):
	array = list(map(int,input().strip().split()))
	grid.append(array)
point = [[0,0],[0,1],[1,0],[1,1]]

#左上＝右上+左下-右下の関係性がいずれも成り立つか否か
for i,j in point:
	if grid[i][j] != grid[i][j+1] + grid[i+1][j] - grid[i+1][j+1] :
		print('No')
		sys.exit()	
print('Yes')


Measured memory_bytes: 3060
#include <stdio.h>

int search(int A[], int n, int key) {
    int i = 0;
    A[n] = key;
    while (A[i] != key) {
        i++;
    }
    return i != n;
}

int main() {
    int i, n, A[10000 + 1], q, key, sum = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &q);
    for(i=0;i<q;i++){
        scanf("%d",&key);
        if (search(A, n, key)) sum++;
    }

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


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

int main() {
	int n;
	long long m,sn,a,ans;

	cin >> n ;
	cin >> a ;
	m=1e9+7;
	sn=a;
	ans=0;
	rep(i, n-1){
		cin >> a ;
		ans+=sn*a;
		ans%=m;
		sn+=a;
		sn%=m;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3576
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[100005], b[100005], c[100005];
ll dp[100005][5];
int main() {
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];

	for (int i = 1; i < n; i++) {
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2])+a[i];
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2])+b[i];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1])+c[i];
	}
	int max = -1e5;
	for (int i = 0; i < n; i++) {
		if (dp[n - 1][i] > max) {
			max = dp[n - 1][i];
		}
	}
	cout << max << endl;
	return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<cstdio>
using namespace std;
int __gcd(int x,int y){return y==0?x:__gcd(y,x%y);}
int a,sum;
int main()
{
	cin>>a;
	for(int i=1;i<=a;i++)
		for(int j=1;j<=a;j++)
			for(int k=1;k<=a;k++)
				sum+=__gcd(__gcd(i,j),__gcd(j,k));
	cout<<sum;
}

Measured memory_bytes: 3632
N, K = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

D = 40

#dp[i][j] = 上位からibit目までの数を確定させたときに得たスコアの最大値
#j=1:上位ibitがKと一致， j=0:それ以外
dp = Array.new(D+1){Array.new(2, -1)}

dp[0][1] = 0

#dp[i][.]からdp[i+1][.]を計算する
0.upto(D-1) do |i|
  mask = 1 << (D-i-1)

  #A1,...ANの(i+1)bit目に1が何個あるか
  num = 0
  N.times do |j|
    num +=1 if mask & a[j] > 0
  end

  #i+1bit目を0,1にしたときに得るスコアを計算
  c = [num*mask, (N-num)*mask]

  #i+1bit目がKと一致するとき
  dp[i+1][1] = dp[i][1] + ((K & mask >0)? c[1] : c[0] )

  #i+1bit目がKと一致しないとき
  #(1) ibit目がKと一致する場合
  if K & mask > 0
    dp[i+1][0] = dp[i][1] + c[0]
  end

  #(2) ibit目がKと一致しない場合
  if dp[i][0] != -1
    dp[i+1][0] = [
        dp[i+1][0],
        dp[i][0] + [c[0],c[1]].max
      ].max
  end
end

puts [dp[D][0],dp[D][1]].max


Measured memory_bytes: 8980
#include<bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    int a[N];
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    int alice = 0;
    int bob = 0;

    sort(a, a + N, greater<int>());
    bool count = true;
    for (int i = 0; i < N; i++) {
        if (count == true){
            alice += a[i];
            count = false;
        }else{
            bob += a[i];
            count = true;
        }
    }

    cout << alice - bob << endl;
}

Measured memory_bytes: 3592
#include<stdio.h>
#include<stdlib.h>

#define VMAX 10000

int main(){
  unsigned short *A,*B;
  int C[VMAX+1];
  int n,i,j;

  scanf("%d",&n);
  A=malloc(n*sizeof(short)+1);
  B=malloc(n*sizeof(short)+1);
  

  for(i=0;i<=VMAX;i++){
    C[i]=0;
  }
  
  for(i=0;i<n;i++){
    scanf("%hu",&A[i+1]);
    C[A[i+1]]++;
  }
  
  for(i=1;i<=VMAX;i++){
    C[i]=C[i]+C[i-1];
  }
  for(j=1;j<=n;j++){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
  
  for(i=1;i<=n;i++){
    if(i>1)printf(" ");
    printf("%d",B[i]);
    }
  printf("\n");
  
  free(A);
  free(B);
 
  return 0;
}




Measured memory_bytes: 9192
#include <bits/stdc++.h>
 
#define int long long
 
// loop
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 	// a ~ b-1	(ascending)
#define REP(i, n) FOR(i, 0, n)							// 0 ~ n-1
#define NREP(i, n) FOR(i, 1, n + 1)						// 1 ~ n
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)	// a ~ b	(descending)
#define RREP(i, n) RFOR(i, n, 0)						// n ~ 0
#define RNREP(i, n) RFOR(i, n, 1)						// n ~ 1
 
// container operation
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define ASORT(c) std::sort((c).begin(), (c).end())
#define DSORT(c) std::sort((c).begin(), (c).end(), std::greater<typeof((c).front())>())
#define SIZE(x) ((int)(x).size())
 
// debug
#define check(x) std::cout << #x << " = " << x << '\n'
 
// print
#define cout(x) std::cout << x << '\n'
 
// typedef
typedef std::vector<int> VI;
typedef std::vector<VI> VII;
typedef std::vector<bool> VB;
typedef std::vector<VB> VBB;
typedef std::vector<std::string> VS;

std::string yes = "Yes\n";
std::string no = "No\n";

void solve();

signed main() {
  solve();
  return 0;
}

void solve() {
  int h, n;
  std::cin >> h >> n;

  int inf = 1000000000;
  VI dp(h+1, inf);
  dp.at(0) = 0;

  int a, b;
  REP(i, n) {
    std::cin >> a >> b;
    REP(j, h+1) {
      int nj = std::min(j+a, h);
      dp.at(nj) = std::min(dp.at(nj), dp.at(j)+b);
    }
  }
  cout(dp.at(h));
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define MAX_V 1000
#define INF 1e9
using namespace std;

//????????¨????§???????(???????????????????????????)
struct edge{int to,cap,rev;};
vector<edge> G[MAX_V]; //??°???????????£??\???????????¨???
int level[MAX_V];      //s??????????????¢
int iter[MAX_V];       //???????????§??????????????£??????

//from??????to??????????????????cap???????????°??????????????????
void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

//s????????????????????¢???BFS??§?¨??????????
void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  level[s] = 0;
  que.push(s);
  while(!que.empty()){
    int v = que.front(); que.pop();
    for(int i=0; i<G[v].size(); i++){
      edge &e = G[v][i];
      if(e.cap > 0 && level[e.to] < 0){
	level[e.to] = level[v] + 1;
	que.push(e.to);
      }
    }
  }
}

//?¢?????????????DFS??§??¢??????
int dfs(int v,int t,int f){
  if(v==t) return f;
  for(int &i= iter[v]; i<G[v].size(); i++){
    edge &e = G[v][i];
    if(e.cap > 0 && level[v] < level[e.to]){
      int d = dfs(e.to, t, min(f, e.cap));
      if(d > 0){
	e.cap -= d;
	G[e.to][e.rev].cap += d;
	return d;
      }
    }
  }
  return 0;
}

//s??????t???????????§???????±???????
int max_flow(int s,int t){
  int flow=0;
  for(;;){
    bfs(s);
    if(level[t] < 0) return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s ,t ,INF)) > 0 ) flow += f;
  }
}

int main(){
  int V,E;
  cin>>V>>E;

  for(int i=0;i<E;i++){
    int u,v,c;
    cin>>u>>v>>c;
    add_edge(u,v,c);
  }
  cout <<max_flow(0,V-1)<<endl;
}

Measured memory_bytes: 3236
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(a+b < c) puts("NA");
    else cout << max(c-a, 0) << "\n";
    return 0;
}


Measured memory_bytes: 3084
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int 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; }

int cost1[30], cost2[30], cost3[30];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, C;
    cin >> n >> C;
    vector<vector<int>> D(C, vector<int>(C)), c(n, vector<int>(n));
    rep(i,C)rep(j,C) cin >> D[i][j];
    rep(i,n)rep(j,n){
        cin >> c[i][j];
        --c[i][j];
    }
    rep(i,C){
        rep(j,n)rep(k,n){
            if((j+k)%3 == 0) cost1[i] += D[c[j][k]][i];
            if((j+k)%3 == 1) cost2[i] += D[c[j][k]][i];
            if((j+k)%3 == 2) cost3[i] += D[c[j][k]][i];
        }
    }
    int ans = 1e9;
    for(int i = 0; i < C; ++i){
        for(int j = 0; j < C; ++j){
            if(i == j) continue;
            for(int k = 0; k < C; ++k){
                if(j == k || i == k) continue;
                chmin(ans, cost1[i] + cost2[j] + cost3[k]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4228
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;
 
#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
char a[101][101];
int b[101];
int c[101];
static int gcd (int a, int b) {
	int temp;
	while((temp = a%b)!=0) {
		a = b;
		b = temp;
	}
	return b;
}

int main() {
  int n , x;
  cin >> n >> x;
  vector<int> v;
  v.push_back(x);
  int t;
  rep(i,n){
    cin >>t;
    v.push_back(t);
  }
  sort(v.begin(), v.end());
  if(n == 1){
    cout << (v[1] - v[0]) << endl;
    return 0;
  }
  vector<int> u;
  reps(i,n){
      u.push_back(v[i]-v[i-1]);
  }
  int f = u[0];
  int ans = 1 << 30;
  reps(i, u.size()-1){
    int mn = min(f, u[i]);
    int mx = max(f, u[i]);
    int t = gcd(mx, mn);
    f = u[i];
    ans = min(t, ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const ll INF = 1e18;

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

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	ll T[N];
	rep(i, 0, N) cin >> T[i];
	if(N == 1) {
		cout << T[0] << endl;
		return 0;
	}
	ll rsl = lcm(T[0], T[1]);

	rep(i, 2, N) {
		rsl = lcm(rsl, T[i]);
	}
	cout << rsl << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++){
    if (int(i * 1.08) == n){
      cout << i << endl;
      return 0;
    }
  }
  cout << ":(" << endl;
}

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

A=0
B=0

while True:
    A=0
    while A**5<=X+B**5:
        if A**5==X+B**5:
            print(A,B)
            exit()
        elif A**5==X-B**5:
            print(A,-1*B)
            exit()
        A+=1
    B+=1




Measured memory_bytes: 9116
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF LLONG_MAX - 100
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define sec second
#define fir first
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
typedef vector<int> Vec;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};



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

	int n;
	cin >> n;
	Vec a(n);
	int sum = 0;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
	}
	int t = sum / n;
	int t2 = mod(sum, n);
	int ans1 = 0, ans2 = 0;
	rep(i, n) {
		ans1 += (t - a[i]) * (t - a[i]);
		ans2 += (t2 - a[i]) * (t2 - a[i]);
	}
	cout << min(ans1, ans2) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long

using namespace std;
using P = pair<int,int>;

int main(){

  int N;
  string s, t;
  cin >> N >> s >> t;

  for (int i = 0; i < N; i++) {
    string ss = s;
    ss = ss.substr(i,s.size());

    string tt = t;
    tt = tt.substr(0,s.size()-i);

    if(ss == tt){
      cout << N*2 - ss.size() << endl;
      return 0;
    }
  }

  cout << s.size()+t.size() << endl;

  return 0;
}

Measured memory_bytes: 3576
from heapq import heappop, heappush

n,m = map(int,input().split())
byte = {}
for i in range(n):
    a,b = map(int,input().split())
    if a > m:
        continue
    if a not in byte:
        byte[a] = []
    heappush(byte[a], -b)

ans = 0
res = []
for i in range(1, m+1):
    if i in byte:
        while byte[i]:
            heappush(res, heappop(byte[i]))
    if res:
        ans -= heappop(res)
print(ans)

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

int main() {
	int n;
	cin >> n;
	int ans = 1e9;
	

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		int cnt = 0;
		while (a % 2 == 0) {
			a /= 2;
			cnt++;
		}
		ans = min(ans, cnt);
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e2+20;
const ll mod=1e9+7;
ll n,c,a[N],b[N];
ll dp[N][N];
ll p[N][N],pre[N][N];
int main()
{
	p[0][0]=1;//i^j
	for(ll i=1;i<=400;i++)
	{
		p[i][0]=1;
		pre[i][0]=1;
		for(ll j=1;j<=400;j++)
		{
			p[i][j]=(p[i][j-1]*i)%mod;		
		}
	}
	//pre[i][j]  1^j+...i^j
	for(ll i=1;i<=400;i++)
		for(ll j=0;j<=400;j++)
			pre[i][j]=(pre[i-1][j]+p[i][j])%mod;
	while(cin>>n>>c)
	{
		for(int i=1;i<=n;i++)
			scanf("%I64d",&a[i]);
		for(int i=1;i<=n;i++)
			scanf("%I64d",&b[i]);
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=c;j++)
			{
				for(int x=0;x<=j;x++)
				{
					ll t=(pre[b[i]][x]-pre[a[i]-1][x]+mod)%mod;
					dp[i][j]=(dp[i][j]+dp[i-1][j-x]*t)%mod;
				}
			}
		}
		cout<<dp[n][c]<<endl;	
	}
	
	
	return 0;
}

Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],n,ans=0;
int dooo(int x)
{
    int cnt=0;
    while(x%2==0)
    {
    x/=2;cnt++;
    }
return cnt;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];ans+=dooo(a[i]);
}
    cout<<ans;
return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	private static int n;

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		int MAX = 0;

		int[] A = new int[n+1];
		for (int i = 1; i < n+1; i++) {
			A[i] = sc.nextInt();
			MAX = Math.max(MAX, A[i]);
		}
		int[] B = new int[n+1];

		CountingSort(A, B, MAX);
		
		StringBuilder str = new StringBuilder();

		//for (int i = 1; i < n; i++) {
		//	System.out.print(B[i] + " ");
		//}
		//System.out.println(B[n]);
		
		str.append(B[1]);
		for (int i = 2; i <= n; i++) {
		str.append(" "+B[i]);
		}
		System.out.println(str);

	}

	public static void CountingSort(int[] A, int[] B, int MAX) {
		int[] C = new int[MAX+1];
		for (int i = 1; i <= n; i++) {
			C[A[i]]++;
		}

		for (int i = 1; i < MAX+1; i++) {
			C[i] += C[i - 1];
		}

		for (int i = n; i > 0; i--) {
			B[C[A[i]]] = A[i];
			C[A[i]]--;
		}
	}
}

Measured memory_bytes: 549128
function main(input) {
    input = input.split(" ").map(e=>String(e))
    const a = input[0]
    const b= input[1]
    const checkSqrtFunc = (a,b)=>{
        const tmp = Number(a+b)
        const result = Number.isInteger(Math.sqrt(tmp)) ?true : false 
        return result
    }
    const flagSqrt = checkSqrtFunc(a,b)
    const mes = flagSqrt ? "Yes" : "No"
    console.log(mes);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

using namespace std;

typedef long long ll;

ll dp[51][2501][51];

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

    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 2500; k >= 0; k--) {
                if (!dp[i][k][j]) continue;
                dp[i+1][k][j] += dp[i][k][j];
                if (k + x[i] <= 2500) {
                    dp[i+1][k+x[i]][j+1] += dp[i][k][j];
                }
            }
        }
    }
    
    ll res = 0;
    for (int i = 1; i <= 2500; i++) {
        for (int j = 1; j <= N; j++) {
            if (dp[N][i][j] && i % j == 0 && i / j == A) {
                res += dp[N][i][j];
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 51200
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back

typedef long long LL; 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int MAX_N = 22;
const int MAX_M = 22;

int A[MAX_N][MAX_M];

//ここから書き始める
int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);	
    int N,M,C; cin >> N >> M >> C;
    VI B(M);
    REP(i,M) cin >> B[i];
    REP(i,N)
    {
        REP(j,M)
        {
            int tmp; cin >> tmp;
            A[i][j] = tmp;
        }
    }

    int ans = 0;
    REP(i,N)
    {
        int func = 0;
        REP(j,M)
        {
            func += B[j] * A[i][j];
            dump(B[i])
            dump(A[i][j])

        }
        dump(func + C)
        if((func + C) > 0) ans++;
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>

int main() {
    int x = 0;
    int y = 0;
    
    int n = 0;
    std::cin >> n;
    
    for(int i = 1; i <= n; i++) {
        x += 800;
        if(i%15==0) {
            y += 200;
        }
    }
    
    std::cout << x-y << std::endl;
}

Measured memory_bytes: 256