akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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; }

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

void dfs(int v, vvi &G, vb &seen){
  if(seen[v]) return;
  seen[v] = true;
  for(auto nv : G[v]) {
    dfs(nv, G, seen);
  }
}

int main(){
  int n,m; cin >> n >> m;
  vector<tuple<int,int,ll>> edges;
  vvi G(n),rG(n);
  rep(i,m) {
    int a,b; ll c; cin >> a >> b >> c;
    a--; b--;
    c = -c;
    edges.emplace_back(a,b,c);
    G[a].pb(b);
    rG[b].pb(a);
  }

  vb seen1(n,false),seen2(n,false),ok(n);
  dfs(0, G, seen1);
  dfs(n-1, rG, seen2);
  rep(i,n) ok[i] = seen1[i]&seen2[i];

  vl d(n,INF);
  d[0] = 0;
  int step = 0;
  for(bool upd = true; upd; step++) {
    upd = false;
    rep(i,m) {
      int a,b,c;
      tie(a,b,c) = edges[i];
      if(!ok[a] || !ok[b]) continue;
      if(chmin(d[b], d[a] + c)) upd = true;
      if(step > n){
        cout << "inf" << endl;
        return 0;
      }
    }
  }
  cout << -d[n-1] << endl;
}


Measured memory_bytes: 384
//g++ -std=c++14 test.cpp -o test.out

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (LL)(1e18)+1;
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

LL N;
vector<set<LL>> red;//x座標がiであるような赤い点の集合をred[i]とおく
vector<set<LL>> blue;//blue[a]内の要素が降順になるよう設定
 
LL ans = 0;

void solve(){
	//条件のきついものからみる
	for(int blue_x=0;blue_x<=2*N-1;blue_x++){//青い点のx座標が0<=blue_x<=2*N-1まで調べる
		//青い点のx座標がblue_xのもののうち、y座標が小さいものから見ていく
		for(auto blue_y_iter=blue[blue_x].begin();blue_y_iter!=blue[blue_x].end();blue_y_iter++){
			LL blue_y = *(blue_y_iter);
			//x座標がblue_x未満の赤い点を,x座標の大きいものから調べ、
			//その中で最もy座標が大きいものを採用
			pair<LL,LL> selected_red(-1,-1);
			for(int red_x=blue_x-1;red_x>=0;red_x--){
				//ギリギリy座標がblue_y未満になるものを選んでくる
				auto iter = red[red_x].lower_bound(blue_y);
				if(iter==red[red_x].begin()) continue;
				iter--;
				LL red_y = *iter;
				if(selected_red.second<red_y){
					selected_red = pair<LL,LL>(red_x,red_y);
				}
			}
			if(selected_red.first==-1) continue;
			//printf("red(%d,%d)とblue(%d,%d)をペアに\n",selected_red.first,selected_red.second,blue_x,blue_y);
			red[selected_red.first].erase(selected_red.second);
			ans++;
		}
	}
}

int main(){
    cin >> N;
    red = vector<set<LL>>(2*N);
    blue = vector<set<LL>>(2*N);
    for(int i=0;i<N;i++){
    	LL a,b;cin >> a >> b;
    	red[a].insert(b);
    }
    for(int i=0;i<N;i++){
    	LL a,b;cin >> a >> b;
    	blue[a].insert(b);
    }
 
    solve();

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

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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	int N;
	cin >>N;
	vector<vector<vector<int>>> X(N+1);
	for (int i=1; i<=N; i++) {
		int A;
		cin >>A;
		for (int j=0; j<A; j++) {
			int x, y;
			cin >>x >>y;
			X.at(i).push_back({x, y});
		}
	}
	int S=0;
	int C=pow(2, N);
	for (int i=0; i<C; i++) {
		vector<int> T(N+1, 0);
		for (int j=1, J=i; j<=N; j++) {
			if (1==J%2)
				T.at(j)=1;
			J /=2;
		}
		bool OK=true;
		for (int j=1; j<=N; j++)
			if (1==T.at(j))
				for (int k=0; k<X.at(j).size(); k++) {
					int T0=X.at(j).at(k).at(0);
					int T1=X.at(j).at(k).at(1);
					if (T1!=T.at(T0))
						OK=false;
				}
		if (OK) {
			int SS=0;
			for (int j=1; j<=N; j++)
				SS +=T.at(j);
			S=max(S, SS);
		}
	}
	cout <<S <<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
#define ll long long
#define pr(x) cerr << #x << ' ' << x << ' '
#define prln(x) cerr << #x << ' ' << x << endl
char a[3];

int main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif // LOCAL
    scanf("%c %c %c", &a[0], &a[1], &a[2]);
    sort(a, a + 3);
    int aa = (a[2] - '0') * 10 + (a[1] - '0');
    int b = a[0] - '0';
    cout << aa + b << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    n, m, d = map(int, input().split())
    if d==0:
        K = n
    elif n>=2*d:
        K = 2*d + 2*(n-2*d)
    else:
        K = 2*(n-d)
    K/=n**2
    K*=m-1
    print(K)

if __name__ == '__main__':
    main()

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

#define REP(i,n) for(int i=0;i<(n);++i)
#define ll long long
const long long INF = 1LL<<60;
const long long mod = 1e9 + 7;

int main(){
    int N, M;
    priority_queue<int> X;
    cin >> N >> M;
    REP(i,N){
        int a;
        cin >> a;
        X.push(a);
    }
    REP(i,M){
        int a = X.top();
        X.pop();
        a /= 2;
        X.push(a);
    }
    ll ans = 0;
    while(X.size() > 0){
        int a = X.top();
        X.pop();
        ans += a;
    }
    cout << ans << endl;
}

Measured memory_bytes: 892
import java.util.*;
 class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        double t=sc.nextDouble()+0.5;
        
        int k=0;
        int s=a;
        while((double)s<t)
        {
            k=k+b;
            s=s+a;
        }
        System.out.println(k);
    }
}


Measured memory_bytes: 23124
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = sc.nextInt();
		long k = sc.nextLong();
		TreeMap<Long, Long> tm = new TreeMap<>();
		long a, b;
		for (int i = 0; i < n; i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			if (tm.containsKey(a)) {
				tm.put(a, tm.get(a) + b);
			} else {
				tm.put(a, b);
			}
		}
		for (long i : tm.keySet()) {
			k = k - tm.get(i);
			if (k <= 0) {
				System.out.println(i);
				break;
			}
		}
	}
}


Measured memory_bytes: 94840
var c,h:char;
    ans:integer;
begin
read(c,h);
if c='M' then ans:=6;
if c='W' then ans:=4;
if c='F' then ans:=2;
if c='S' then 
 if h='U' then ans:=7
 else ans:=1;
if c='T' then 
 if h='U' then ans:=5
 else ans:=3;
write(ans)
end.

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

int main(){
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    for(int i = 0, x; i < N; ++i, X = max(x, X))cin >> x;
    for(int i = 0, y; i < M; ++i, Y = min(y, Y))cin >> y;
    puts(X < Y ? "No War" : "War");
    return 0;
}

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

int main() {
  int n;
  int m;
  cin >> n >> m;
  int ans = 0;

  set<int> divisors;
  
  for(int i=1;i<=sqrt(m);i++) {
    if(m % i == 0) {
      divisors.emplace(i);
      divisors.emplace(m / i);
    }
  }

  auto it = divisors.lower_bound(n);

  cout << m / (*it) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f//3f3f3f3f
#define ll long long
#define ull unsigned long long
#define lowbit(a) ((a)&(-(a)))
using namespace std;
struct number{
    int cnt;
    int c[10];
    bool operator < (const number &b)const{
        if(cnt == b.cnt){
            for(int i = 9;i>=1;i++){
                if(c[i] == b.c[i])continue;
                return c[i] < b.c[i];
            }
            return false;
        }else{
            return cnt < b.cnt;
        }
    }
    void add(int x){
        c[x] ++, cnt ++;
    }
    void sub(int x){
        c[x] --, cnt --;
    }
    void init(){
        cnt = 0; memset(c,0,sizeof c);
    }
    void println(){
        for(int i = 9;i>=1;i--)
            for(int j = 0;j < c[i];j++)putchar((char)i+'0');
        putchar('\n');
    }
};
int n,m,u[10] = {0,2,5,5,4,5,6,3,7,6}, a[10], d[10];
vector<int> v;
number ans, now;
void dfs(int cnt, int k){
    if(now < ans && cnt > 50)return;
    if(cnt == 0){
        if(ans < now)ans = now;
        return;
    }
    for(int i = k;i<=7;i++){
        if(i > cnt)return;
        if(d[i] == 0)continue;
        now.add(d[i]);
        dfs(cnt - i,i);
        now.sub(d[i]);
    }
}
int main() {
    while(~scanf("%d %d",&n,&m)){
        memset(d,0,sizeof d);
        v.clear();
        for(int i = 1;i<=m;i++)scanf("%d",&a[i]), d[u[a[i]]] = max(a[i], d[u[a[i]]]);
        ans.init(); now.init();
        dfs(n,2);
        ans.println();
    }
    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
int main()
{
  int a, b, c, X, Y;
  int D, G;
  char s[101][101]={};
  char sv[101]={};
  char ss[101]={};
//  char s_temp[101]={};
  char t[101]={};
//  char s[10000000000000000001]={};
//  char s[101]={};
  int len=0;
  int N, M;
  int A[20000]={};
  int B[20000]={};
  int C[20000]={};
  int i,j,k;
  int flag=0;
  int tmp=0;
  int min=101;
  int cnt=0;
  int max=0;
  int ans=0;

//  long cnt =0;
  long long A_temp;
//    int k=0;

  scanf("%d %d", &a, &b);
//  printf("%d %d\n",D,G);

  if(a==2 || b==2)    printf("No\n");
//  else if(b==2)    printf("No\n");
  else     printf("Yes\n");
   
//   printf("%d\n",a-b+1);
  
return 0;
}


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

const int INF = 2e9;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    ll ans = INF;
    for(int i = -100;i <= 100;i++){
        ll sum = 0;
        rep(j,n){
            sum += (a[j] - i) * (a[j] - i);
        }
        ans = min(ans,sum);
    }
    cout << ans << endl;
}

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

int main() {
    int N, M;
    cin >> N >> M;

    map<int, int> mp;
    rep(i, M) {
        int a, b;
        cin >> a >> b;

        if (!mp.count(a)) mp[a]=1;
        else mp[a]++;

        if (!mp.count(b)) mp[b]=1;
        else mp[b]++;
    }

    bool flag=true;
    for (auto m : mp) {
        if (m.second%2) {
            flag = false;
            break;
        }
    }

    cout << (flag ? "YES" : "NO") << endl;
}


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

int dis[90010];

int main()
{
	int h, w, d, q;
	int l, r;

	cin >> h >> w >> d;

	int a;
	int dx[90010], dy[90010];
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			cin >> a;
			dx[a] = j, dy[a] = i;
		}
	}

	for (int i = d + 1; i <= h * w; i++)
	{
		dis[i] = dis[i - d] + abs(dx[i] - dx[i - d]) + abs(dy[i] - dy[i - d]);
	}

	cin >> q;

	for (int i = 1; i <= q; i++)
	{
		cin >> l >> r;
		cout << dis[r] - dis[l] << endl;
	}
}

Measured memory_bytes: 2176
import math

def main():
    # input
    a, b, x = map(int, input().split())

    # calc
    if x <= a*a*b/2:
        ans = math.degrees(math.atan(2*x/a/b/b))
        print(90-ans)

    else:
        y = a*a*b - x
        ans = math.degrees(math.atan(2*y/a**3))
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int a,b=0;
    cin>>a;
    int n[a];
    for(int i=0;i<a;i++){
        cin>>n[i];
    }
    sort(n,n+a);
    for(int i=0;i<a;i++){
        if(n[i]!=n[i+1]){
            b=b+1;
        }
    }
    cout<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <math.h>
typedef long long ll;
using namespace std;

int main() {
	ll a,b,ans=1;
	cin>>a>>b;
	for(int i=0;i<a-1;i++){
		ans*=(b-1);
	}
	cout << ans*b<<endl;
 	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) throws Exception{    
        Scanner sc = new Scanner(System.in);
        
       String w = sc.next();
       
       int[] x = new int[26];
       
       for(int i=0; i<w.length(); i++){
    	   x[(int)w.charAt(i) - 97]++;
       }
       
       String ans = "Yes";
       for(int i=0; i<26; i++){
    	   if(x[i]%2 == 1){
    		   ans = "No";
    		   break;
    	   }
       }
       
       System.out.println(ans);
        
       sc.close();
    }
 
}

Measured memory_bytes: 9684
object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val N, M = ni()
    val cities = Array.ofDim[(Int, Int, Int)](M)
    rep(M) { i =>
      cities(i) = (ni() - 1, ni(), i)
    }
    Sorting.quickSort(cities)(Ordering.by(_._2))
    val cnt = Array.ofDim[Int](N)
    val num = Array.ofDim[Int](M)
    val pref = Array.ofDim[Int](M)
    rep(M) { i =>
      val p = cities(i)._1
      val c = cities(i)._3
      val id = cnt(p)
      num(c) = id
      pref(c) = p
      cnt(p) += 1
    }

    rep(M) { i =>
      val p = pref(i)
      val c = num(i)
      out.println(f"${p+1}%06d${c+1}%06d")
    }
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int): Array[Int] = map(n)(_ => ni())
  def na2(n: Int, offset: Int = 0): (Array[Int], Array[Int]) = {
    val A1, A2 = Array.ofDim[Int](n)
    rep(n) { i =>
      A1(i) = ni() + offset
      A2(i) = ni() + offset
    }
    (A1, A2)
  }
  def nm(n: Int, m: Int): Array[Array[Int]] = {
    val A = Array.ofDim[Int](n, m)
    rep(n) { i =>
      rep(m) { j =>
        A(i)(j) = ni()
      }
    }
    A
  }
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm_c(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def rep(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def rep_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i))
    res
  }

  def sumL(as: Array[Int]): Long = {
    var s = 0L
    rep(as.length)(i => s += as(i))
    s
  }

  def cumSum(as: Array[Int]) = {
    val cum = Array.ofDim[Int](as.length + 1)
    rep(as.length) { i =>
      cum(i + 1) = cum(i) + as(i)
    }
    cum
  }
}

Measured memory_bytes: 131420
n = int(input())
a_ls = list(map(int, input().split()))
b_ls = list(map(int, input().split()))
before = sum(a_ls)

for i in range(n):
    target = a_ls[i:i+2]
    power = b_ls[i]
    if target[0] - power < 0:
        power -= target[0]
        target[0] = 0
        target[1] = max(0, target[1] - power)
    else:
        target[0] -= power
    a_ls[i:i+2] = target

after = sum(a_ls)
print(before - after)

Measured memory_bytes: 18380
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

#define mod 1000000007
#define ll long long int
#define pb(x) push_back(x)
#define MP(x,y) make_pair(x,y)

using namespace std;

ll power(ll a, ll b, ll m)
{
	if (b == 0)
		return(1);
	ll sol = power(a, b / 2, m);
	sol = (sol * sol) % m;
	if (b % 2 == 1)
		sol = (sol * a) % m;
	return(sol);
}
ll gcd(ll a, ll b)
{
	if (a % b == 0)
		return b;
	else
	{
		return gcd(b, a % b);
	}
}
void solve()
{
	ll a, b, c, n,sol=0;
	cin >> a >> b >> c >> n;
	for (int i = 0; i <= n; i++)
	{
		int x = n - i * a;
		if (x < 0)
			continue;
		for (int j = 0; j <= n; j++)
		{
			int y = x - j * b;
			if (y < 0)
				continue;
			if (y % c == 0)
				sol++;
		}
	}
	cout << sol;
}
int main()
{
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return(0);
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <unordered_map>
#include <math.h>
#define MOD 1000000007

using namespace std;

ifstream fin("../data.txt");

int x;

unordered_map<int, long long> factorization(int x) {
  unordered_map<int, long long> factors;
  while(x % 2 == 0) {
    factors[2]++;
    x /= 2;
  }

  for (int i = 3; i <= sqrt(x); i++) {
    while(x % i == 0) {
      factors[i]++;
      x /= i;
    }
  }

  if (x != 1) factors[x]++;
  // for (auto aux : factors) {
  //   cout << "(" <<  aux.first << ", " << aux.second << ") ";
  // }
  // cout << "\n";
  return factors;
}

int main() {

  cin >> x;
  unordered_map<int, long long> factors;
  for (int n = 2; n <= x; n++) {
    unordered_map<int, long long> currFactors = factorization(n);
    for (auto aux : currFactors) {
      factors[aux.first] += aux.second;
    }
  }

  long long ans = 1;
  for (auto aux : factors) {
    ans *= (aux.second + 1LL);
    ans %= MOD;
  }


  cout << ans;

  return 0;
}


Measured memory_bytes: 3696
#include <iostream>
#include <queue>
#include <map>
#include <string.h>
#include <cstdio>
#define INF 1000000
using namespace std;
typedef pair<int,int>P;
char G[1001][1001];
int s_x,s_y,g_x,g_y;
int h,w,n;
int d[1001][1001];
int dx[] = {0,0,-1,1},dy[] = {1,-1,0,0};
int sum;
int bfs(int px,int py,int life){

  for(int i = 0 ; i < h ; i++ ){
    for(int j = 0 ; j < w ; j++ ){
      d[j][i] = INF;
      if(G[j][i]-'0' == life){
	g_x = j;
	g_y = i;
      }
    }
  }

  queue<P>que;
  que.push(P(px,py));
  d[px][py] = 0;

  while(!que.empty()){
    P p = que.front();
    que.pop();
    if(p.first == g_x && p.second == g_y)break;
    for(int i = 0 ; i < 4 ; i++ ){
      int nx = p.first + dx[i],ny = p.second + dy[i];
      if(0<= nx && nx < w && 0 <= ny && ny < h && G[nx][ny] != 'X'&&d[nx][ny] == INF){
	que.push(P(nx,ny));
	d[nx][ny] = d[p.first][p.second] + 1;
      }
    }
  }
  sum += d[g_x][g_y]; 
  if(life != n)bfs(g_x,g_y,life+1);
  return sum;
}

int main(){

  cin >> h >> w >> n;
  for(int i = 0 ; i < h ; i++ ) {
    for(int j = 0 ; j < w ; j++ ) {
      cin >> G[j][i];
      if(G[j][i] == 'S'){
	s_x = j;
	s_y = i;
      }
    }
  }
  sum = 0;
  int ret =  bfs(s_x , s_y , 1);
  cout << ret << endl;
}

Measured memory_bytes: 6112
#include<bits/stdc++.h>
using namespace std;
// #define int long long


int p[300001],sizes[300001],mini[300001],maxx[300001];
int get(int x){
    return p[x]=((x==p[x])?x:get(p[x]));
}

void unionn(int a,int b){
    a=get(a);
    b=get(b);
    // if(sizes[a]>sizes[b])
    // swap(a,b);
    p[b]=a;
    mini[a]=min(mini[a],b);
    maxx[a]=max(maxx[a],b);
    sizes[a]+=sizes[b];
}

signed main()
{
    int x;
    cin>>x;
    cout<<1-x<<endl;
    
}

Measured memory_bytes: 3588
#include <cstdio>

int W, H;
char tile[21][21];

int search(int y, int x) {
  if (tile[y][x] == '#') return 0;
  int cnt = 1;
  tile[y][x] = '#';
  if (y > 0)   cnt += search(y-1, x);
  if (y < H-1) cnt += search(y+1, x);
  if (x > 0)   cnt += search(y, x-1);
  if (x < W-1) cnt += search(y, x+1);
  return cnt;
}

int main() {
  while (true) {
    scanf("%d %d", &W, &H);
    if (W == 0 && H == 0) break;
    for (int i=0;i<H;i++) scanf("%s", tile[i]);
    int cnt = 0;
    for (int i=0;i<H;i++) {
      for (int j=0;j<W;j++) {
        if (tile[i][j] == '@') {
          cnt = search(i, j);
          break;
        }
      }
    }
    printf("%d\n", cnt);
  }
  return 0;
}

Measured memory_bytes: 2604
#include<iostream>
using namespace std;
 
struct Dice {
    int top;
    int north;
    int east;
    int south;
    int west;
    int bottom;
};
 
void rotn(void);
void rote(void);
void rots(void);
void rotw(void);
 
Dice d;
int tmp;
 
int main() {
    int i, q, t, f, r;
    cin >> d.top >> d.south >> d.east >> d.west >> d.north >> d.bottom;
    cin >> q;
    for (i = 0; i < q; i++) {
        cin >> t >> f;
        if (t == d.north)rots();
        else if (t == d.east)rotw();
        else if (t == d.south)rotn();
        else if (t == d.west)rote();
        else if (t == d.bottom) {
            rotn(); rotn();
        }
        if (f == d.north)r = d.west;
        else if (f == d.east)r = d.north;
        else if (f == d.south)r = d.east;
        else if (f == d.west)r = d.south;
        cout << r << endl;
    }
    return 0;
}
 
void rotn(void) {
    tmp = d.top;
    d.top = d.south;
    d.south = d.bottom;
    d.bottom = d.north;
    d.north = tmp;
}
 
void rote(void) {
    tmp = d.top;
    d.top = d.west;
    d.west = d.bottom;
    d.bottom = d.east;
    d.east = tmp;
}
 
void rots(void) {
    tmp = d.top;
    d.top = d.north;
    d.north = d.bottom;
    d.bottom = d.south;
    d.south = tmp;
}
void rotw(void) {
    tmp = d.top;
    d.top = d.east;
    d.east = d.bottom;
    d.bottom = d.west;
    d.west = tmp;
}

Measured memory_bytes: 3092
import java.util.Scanner;
 
public class Main {

	public static final MyScanner in = new MyScanner();

	public static void main(String[] args) {

		int N = in.nextInt();

		int left = 1;
		int right = 50001;
		while(left < right) {
			int mid = (left+right) / 2;
			int taxIn = taxIn(mid);
			if (taxIn == N) {
				System.out.println(mid);
				return;
			}
			else if (taxIn > N) right = mid;
			else if (taxIn < N) left = mid+1;
		}

		System.out.println(":(");

	}

	public static int taxIn(int X) {
		return (int)(X * 1.08);
	}

	public static class MyScanner{
		Scanner sc = new Scanner(System.in);
		String nextLine() {return sc.nextLine();}
		String next() {return sc.next();}
		int nextInt() {return Integer.valueOf(sc.next());}
		long nextLong() { return Long.valueOf(sc.next());}
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; //575;

int main()
{
    vector<int> d;
    int n;
    int a;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        d.push_back(a);
    }

    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());

    cout << d.size() << endl;
}


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

using namespace std;
typedef long long ll;

const ll mod=998244353;

ll fpow(ll b,ll e)
{
    ll res=1;
    while(e)
    {
        if(e&1) res=(res*b)%mod;
        b=(b*b)%mod;
        e/=2;
    }
    return res;
}

int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    vector<ll> f(n+1,1);
    for(ll i=1;i<=n;i++) f[i]=(f[i-1]*i)%mod;
    vector<ll> finv(n+1,0);
    finv[n]=fpow(f[n],mod-2);
    for(ll i=n-1;i>=0;i--) finv[i]=(finv[i+1]*(i+1))%mod;
    vector<ll> p(n+1,1);
    for(int i=1;i<=n;i++) p[i]=(p[i-1]*(m-1))%mod;
    ll res=0;
    auto c=[&](ll a,ll b)->ll
    {
        ll x=f[a];
        x=(x*finv[b])%mod;
        x=(x*finv[a-b])%mod;
        return x;
    };
    for(int x=0;x<=k;x++)
    {
        ll now=c(n-1,x);
        now=(now*m)%mod;
        now=(now*p[n-1-x])%mod;
        res=(res+now)%mod;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 7944
#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <algorithm>

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

typedef long long ll;

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

    vector<vector<int>> to(n);
    REP(i, m)
    {
        int s, t;
        cin >> s;
        cin >> t;
        s--;
        t--;
        to[s].push_back(t);
    }

    vector<double> dp(n);
    for (int v = n - 2; v >= 0; --v)
    {
        double now = 0;
        for (int u : to[v])
        {
            now += dp[u];
        }
        now /= to[v].size();
        now += 1;
        dp[v] = now;
    }

    double ans = dp[0];
    for (int nv = 0; nv < n - 1; nv++)
    {
        if (to[nv].size() == 1)
            continue;
        int nu = to[nv][0];
        for (int u : to[nv])
        {
            if (dp[nu] < dp[u])
                nu = u;
        }

        double now = [&] {
            vector<double> dp(n);

            for (int v = n - 2; v >= 0; --v)
            {
                double now = 0;
                for (int u : to[v])
                {
                    if (v == nv && u == nu)
                        continue;
                    now += dp[u];
                }

                int deg = to[v].size();
                if (v == nv)
                    deg--;

                now /= deg;
                now += 1;
                dp[v] = now;
            }
            return dp[0];
        }();

        ans = min(ans, now);
    }
    printf("%.10f\n", ans);
    return 0;
}

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

int main() {
    int N, M; cin >> N >> M;
    vector<int> P(M), Y(M);
    for (int i = 0; i < M; i++) cin >> P[i] >> Y[i];
    vector<int> ord[100100];
    for (int i = 0; i < M; i++) ord[P[i]].push_back(Y[i]);
    for (int i = 1; i <= N; i++) sort(ord[i].begin(), ord[i].end());
    for (int i = 0; i < M; i++) {
        int n = lower_bound(ord[P[i]].begin(), ord[P[i]].end(), Y[i]) - ord[P[i]].begin() + 1;
        printf("%06d%06d\n", P[i], n);
    }
    return 0;
}

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

int main() {
	int n,t;
	cin >> n;
	int max = 0;
	for (int i = 1; i <= n; i++)
	{
		t = i * i;
		if(t <= n){
			max = t;
		}else{
			break;
		
		}
	}
	cout << max << endl;

}


Measured memory_bytes: 384
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int N = Integer.parseInt(sc.next());
    int M = Integer.parseInt(sc.next());
    int X = Integer.parseInt(sc.next());
    int Y = Integer.parseInt(sc.next());
    int[] x = new int[N];
    int[] y = new int[M];
    for (int i = 0; i < N; i++) x[i] = Integer.parseInt(sc.next());
    for (int i = 0; i < M; i++) y[i] = Integer.parseInt(sc.next());
    
    int maxX = X;
    for (int i = 0; i < N; i++) {
      maxX = Math.max(maxX, x[i]);
    }
    
    int minY = Y;
    for (int i = 0; i < M; i++) {
      minY = Math.min(minY, y[i]);
    }
    
    if (maxX < minY) {
      System.out.println("No War");
    }
    else {
      System.out.println("War");
    }
    
  }
}

Measured memory_bytes: 21844
# -*- coding: utf-8 -*-
"""
Created on Tue Mar  5 17:48:45 2019

@author: yuta
"""
import math
N = int(input())

def main(n):
    sqrt_n = math.sqrt(n)
    min_keta = len(str(n))
    for i in range(1,int(sqrt_n)+1):
        if n % i == 0:
            j = int(n/i)
            max_num = max(i,j)
            c = len(str(max_num))
            if c < min_keta:
                min_keta = c
    print(min_keta)
main(N)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <deque>

using namespace std;

int ctoi(char c){
    switch(c){
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default : return -1;
    }
}

int main(int argc, char const *argv[])
{
	int n,a,b;
	int res = 0;
	vector<int> v;

	cin >> n >> a >> b;

	for (int i = 0; i < n; ++i)
	{
		int sum_digit = 0;
		string digit = to_string(i+1);
		//cout << digit << endl;
		
		for (int j = 0; j < digit.size(); ++j)
		{
			int tmp = ctoi(digit[j]);
			sum_digit += tmp;
		}

		if(a <= sum_digit && sum_digit <= b){
			res += i+1;
		}
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include <atcoder/all>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define LL long long

int n,m;

int main() {
    cin>>n>>m;
    vector<LL> a(n),b(m);
    REP(i,n)cin>>a[i];
    REP(i,m)cin>>b[i];
    auto c = atcoder::convolution<998244353>(a,b);
    REP(i,c.size())cout<<c[i]<<" ";
    cout<<endl;
}

Measured memory_bytes: 27292
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const double PI = acos(-1);

int main(void){
	ll n, k;
	cin >> n >> k;
	Vec a(n);
	rep(i, n) cin >> a[i];

	ll ans = LINF;
	rep(bit, pow2(n)) {
		ll cnt = 0;
		rep(i, n) cnt += bit >> i & 1;
		if (cnt != k) continue;
		ll h = 0, sum = 0;
		rep(i, n) {
			if (bit >> i & 1) {
				if (h < a[i]) {
					h = a[i];
				} else {
					sum += h + 1 - a[i];
					h++;
				}
			}else
				chmax(h, a[i]);
		}
		chmin(ans, sum);
	}
	co(ans);

	return 0;
}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "cycle"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

char s[MAXN];

void solve(){
	ll ans = 0;
	scanf("%s", &s[0]);
	int n = strlen(s);
	REP(i, 0, n){
		ll v = 0;
		REP(j, i, n){
			v = v * 10ll + (s[j] - '0');
			ans += v * (1 << (max(0, i - 1) + max(0, n - 2 - j)));
		}
	}
	printf("%lld\n", ans);
}	

int main(){

	//freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();	
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

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

using namespace std;

int main() {
	string trans = "XYZABCDEFGHIJKLMNOPQRSTUVW";
	string str;
	cin >> str;

	rep(i, 0, str.length()) {
		cout << trans[str[i] - 'A'];
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 1184
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

int main(){
  int N;
  int A[200000];
  map<int, ll> mii;
  cin >> N;
  
  int tmp;
  for (int i = 0; i < N; i++) {
	  cin >> tmp;
	  A[i] = tmp;
	  ++mii[tmp];
  }

  ll miiSum = 0;
  auto end = mii.end();
  for (auto itr = mii.begin(); itr != end; itr++) {
	  miiSum += itr->second * (itr->second - 1) / 2;
  }

  for (int i = 0; i < N; i++) {
	  ll selNumCnt = mii[A[i]];
	  ll ans = miiSum;
	  ans -= selNumCnt * (selNumCnt-1) / 2;
	  ans += (selNumCnt-1) * (selNumCnt-2) / 2;
	  cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
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; }
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int n,l;
vector<string> s;

void input(){
    cin >> n >> l;
  	s.resize(n);
  	for(int i=0;i<n;i++) cin >> s[i];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
  	sort(s.begin(), s.end());
  	for(int i=0;i<n;i++) cout << s[i];
  	cout << endl;
}

Measured memory_bytes: 256
from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    line2 = "#" + line + "#"
    num_blacks += line.count(".")
    field.append(line)

cost = [[-1]*(W) for _ in range(H)]

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)




Measured memory_bytes: 3316
# coding: utf-8
# Your code here!
H,W=map(int,input().split())

l=[]
for _ in range(H):
    l.append(list(input()))

def dfs(h,w):
    l[h][w]="!"
    #print(l)
    #print(h,w,l[h][w])
    if h==H-1 and w==W-1:
        for item in l:
            if "#" in item:
                print("Impossible")
                exit()
        print("Possible")
        exit()
    elif (l[h-1][w]=="#" if h>0 else False) or (l[h][w-1]=="#" if w>0 else False):
        print("Impossible")
        exit()
    if h<H-1:
        if l[h+1][w]=="#":
            dfs(h+1,w)
    if w<W-1:
        if l[h][w+1]=="#":
            dfs(h,w+1)
    l[h][w]="#"
    
    return "Impossible"

print(dfs(0,0))


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

#define ll long long 

using namespace std;

const int N = 2e5+5,mod=1e9+7;

int main() {
	int n;
	cin>>n;
	ll ans=0,sum=0;
	vector<int> v;
	for (ll i = 0; i < n; ++i)
	{
		ll x;
		cin>>x;
		sum+=x;
		if(x==0){
			ans+=sum/2;
			sum=0;
		}
	}
	ans+=sum/2;
	cout<<ans;
}

Measured memory_bytes: 3560
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

t,x = LI()
print(t/x)

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
int main(){
    string s, t;
    cin >> s >> t;
    pair<ll, ll> po[s.size() + 1] = {}, yo[t.size() + 1] = {};
    for(ll i = 0; i < s.size(); i++) po[i + 1] = pair<ll, ll>(po[i].first + (s[i] == 'A'), po[i].second + (s[i] == 'B'));
    for(ll i = 0; i < t.size(); i++) yo[i + 1] = pair<ll, ll>(yo[i].first + (t[i] == 'A'), yo[i].second + (t[i] == 'B'));
    ll q;
    cin >> q;
    for(ll i = 0; i < q; i++){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        ll poa = po[b].first - po[a - 1].first, pob = po[b].second - po[a - 1].second;
        ll yoa = yo[d].first - yo[c - 1].first, yob = yo[d].second - yo[c - 1].second;
        ll saa = max<ll>(0, yoa - poa), sab = max<ll>(0, yob - pob);
        poa += max(saa, sab);
        pob += max(saa, sab);
        if(((poa - yoa) + 2 * (pob - yob)) % 3 == 0 && ((poa - yoa) * 2 + (pob - yob)) % 3 == 0) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Measured memory_bytes: 5888
#include<stdio.h>

int main(){
    
    int N;
    int i,j,k,v;
    int flag,count=0;
    
    scanf("%d",&N);
    
    int a[N];
    
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    
    flag=1;
    while(flag){
        flag=0;
        for(j=N-1;j>0;j--){
            if(a[j]<a[j-1]){
                v=a[j-1];
                a[j-1]=a[j];
                a[j]=v;
                flag=1;
                count++;
            }
        }
    }
       
    for(k=0;k<N-1;k++){
        printf("%d ",a[k]);
    }
    printf("%d\n",a[N-1]);
    
    printf("%d\n",count);
       
    return 0;
}

Measured memory_bytes: 600
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; 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;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

ll X, K, D;
long double eps = 1e-9;

int main() {
  //
  cin >> X >> K >> D;

  X = abs(X);

  if (K <= X / D) {
    cout << X - K * D;
    return 0;
  } else {
    ll times = X / D;
    ll rest = K - times;
    if (rest % 2 == 0) {
      cout << X - D * times;
      return 0;
    } else {
      cout << abs(X - D * times - D);
      return 0;
    }
  }
}


Measured memory_bytes: 3636
tile = input()

head = tile[0]
tile = tile[1:]
tmp = head

counter = 0

for i in tile:
    if i == tmp and i == "1":
        i = "0"
        tmp = i
        counter += 1
    elif i == tmp and i == "0":
        i = "1"
        tmp = i
        counter += 1
    else:
        tmp = i

print(counter)


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


int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int x = a-b;
    if(c-x>=0)
    {
        cout<<c-x<<endl;
    }
    else
    {
        cout<<0<<endl;
    }
    
    return 0;
}

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

using namespace std;

typedef long long ll;

ll a[1000000];
ll N;

ll func(ll x){
  ll sum = 0;
  for(int i=1;i<=N;i++) sum += abs(a[i] - x);
  return sum;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cin >> N;
  for(int i=1;i<=N;i++) cin >> a[i];
  for(int i=1;i<=N;i++) a[i] = a[i] - i;
  ll left = -1e9-10, right=1e9+10;
  for(int i=0;i<=50;i++){
    if(func((left*2 + right)/3) > func((left + right*2)/3)){
      left = (left*2 + right)/3;
    }else{
      right = (left + right*2)/3;
    }
  }
  cout << min(func((left+right*2)/3), func((right+left*2)/3)) << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////

pair<int,int>ar[1002];
int dp[1002][10002];
int DP(int i,int h){
    if(h <= 0)return 0;
    if(i == 0)return 100000000;
    int &ret = dp[i][h];

    if(ret != -1)return ret;
    ret = 100000000;

    ret = min(ret, ar[i].y + DP(i, h-ar[i].x));
    ret = min(ret, DP(i-1, h));
    return ret;

}
int main(){
    int h,n;
    I2(h,n);
    for(int i = 1;i<=n;i++)I2(ar[i].x,ar[i].y);
    SETR(dp);
    cout<<DP(n,h)<<endl;

    return 0;
}

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

using namespace std;

int N, M, A, B;
long long ans;
// Store only the payout since we'll make sure it finishes before
priority_queue<int> highestPayingJobs; 
// Days it takes and payout
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> jobs;

int main() {
    cin >> N >> M;
	for(int i = 0; i < N; i++) {
		cin >> A >> B;
		jobs.push(make_pair(A, B));
	}
	
	for(int daysBefore = 1; daysBefore <= M; daysBefore++) {
		while (!jobs.empty() && jobs.top().first <= daysBefore) {
			highestPayingJobs.push(jobs.top().second);
			jobs.pop();
		}
		
		if (!highestPayingJobs.empty()) {
			ans += highestPayingJobs.top();
			highestPayingJobs.pop();
		}
	}
	
	cout << ans;
}


Measured memory_bytes: 1908
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]
 
total = sum(sum(c) for c in C)
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
    D = [0] * len(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)
   
print(answer)

Measured memory_bytes: 3564
#include <iostream>
#include <string.h>
#include <string>
#include <vector>

using namespace std;

void solve()
{
	int n;
	while(cin >> n, n)
	{
		int used[86401];
		memset(used, 0, sizeof(used));
		for(int i = 0; i < n; ++i)
		{
			string start, end;
			cin >> start >> end;
			int s = (start[0] - '0') * 10 * 3600 + (start[1] - '0') * 3600 + (start[3] - '0') * 10 * 60 + (start[4] - '0') * 60 + (start[6] - '0') * 10 + (start[7] - '0');
			int t = (end[0] - '0') * 10 * 3600 + (end[1] - '0') * 3600 + (end[3] - '0') * 10 * 60 + (end[4] - '0') * 60 + (end[6] - '0') * 10 + (end[7] - '0');
			for(int j = s; j < t; ++j)
			{
				++used[j];
			}
		}
		int max_val = 0;
		for(int i = 0; i < 86401; ++i)
		{
			max_val = max(max_val, used[i]);
		}
		cout << max_val << endl;
	}
}

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

Measured memory_bytes: 1552
#include <iostream>
#include <math.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    for (int n = 1; n <= N; n++) {
        int ans = 0;
        for (int i = 2; i*i < 2*n; i++) {
            for (int j = 2; (i*i + j*j) < 2*n; j++) {
                int k = sqrt(2*n - i*i - j*j);
                if (i*i + j*j + k*k == 2*n && i+j-k >= 2 && i+k-j >= 2 && k+j-i >= 2) ans++;
            }
        }
        cout << ans << endl;
    }
}

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

int main() {
    int A, B;
    cin >> A >> B;
    for(int i=1; i<=3; i++){
        if(A*B*i%2 ==1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


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

using namespace std;

#define ll long long int
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define MOD 1000000007

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

    int n;
    cin>>n;
    int h[n+1];
    int dp[n+1];
    for(int i = 1; i<=n; i++){
        cin>>h[i];
    }
    dp[1] = 0;
    
    for(int i = 2; i<=n; i++){
        dp[i] = INT_MAX;
        if(i - 1 > 0){
            dp[i] = min(dp[i],abs(h[i-1] - h[i]) + dp[i-1]);
        }
        if(i - 2 > 0){
            dp[i] = min(dp[i],abs(h[i-2] - h[i]) + dp[i-2]);
        }
    }
    cout<<dp[n]<<"\n";
}

Measured memory_bytes: 1024