akhauriyash/Code-Regression huggingface dataset:
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	lineTop = input[0].split(" ");
	lineX = input[1].split(" ");
	lineY = input[2].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var n = parseInt(lineTop[0], 10);
	var m = parseInt(lineTop[1], 10);
	var x = parseInt(lineTop[2], 10);
	var y = parseInt(lineTop[3], 10);

	var maxX = x;
	var minY = y;

	for (var work of lineX) {
		if (parseInt(work) > parseInt(maxX)) {
			maxX = work;
		}
	}

	for (var work of lineY) {
		if (parseInt(work) < parseInt(minY)) {
			minY = work;
		}
	}

	if (parseInt(minY) <= parseInt(maxX)) {
		console.log('War');
	} else {
		console.log('No War');
	}
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main(){

	double x1,x2,y1,y2;
	cin >> x1 >> y1 >> x2 >> y2;

	double distance_x,distance_y;
	distance_x = x2 - x1;
	distance_y = y2 - y1;

	cout << fixed << sqrt(pow(distance_x,2)+pow(distance_y,2)) << endl;
	//printf("%f\n",sqrt(pow(distance_x,2)+pow(distance_y,2)));

	return 0;
}



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

int main(){
    int r;cin >> r;
    cout << fixed << setprecision(15) <<  2*acos(-1)*r << endl;
}


Measured memory_bytes: 3788
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <functional>
#include <math.h>
using namespace std;

#define ll long long
//#define int long long
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

#define dump(x)  cerr << #x << " = " << (x) << endl; 
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 


typedef pair<int, int> P;
struct Point{
	int x, y;
};
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = {1,0,-1,0};



int main(){

	int N;
	int x[101], y[101], h[101];

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> x[i] >> y[i] >> h[i];

	for (int cx = 0; cx <= 100; cx++)
		for (int cy = 0; cy <= 100; cy++){

			int *i = max_element(h, h + N);
			int height = abs(x[i - h] - cx) + abs(y[i - h] - cy) + *i;

			bool found = true;
			for (int j = 0; j < N; j++){
				if (max(height - abs(x[j] - cx) - abs(y[j] - cy), 0) != h[j]){
					found = false;
					break;
				}
			}
			if (found){
				cout << cx << " " << cy << " " << height << endl;
				return 0;
			}
		}


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <set>
#include <map>
#include <list>
#include <cstdlib>

using namespace std;

#define mod (1e9 + 7)
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()

typedef long long ll;

void solve1()
{
    ll n, h, w; cin >> n >> h >> w;
    vector<ll> a(n), b(n);
    rep(i, n) {
        cin >> a[i] >> b[i];
    }

    int cnt = 0;
    rep(i, n) {
        if(a[i] >= h && b[i] >= w) {
            cnt ++;
        }
    }

    cout << cnt << endl;

}

int main()
{
    solve1();
}


Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt();
		if (N % 2 != 0) {
			System.out.println("NA");
			return;
		}
		int[] X = new int[N];
		int[] Y = new int[N];
		int sx = 0;
		int sy = 0;
		for (int i = 0; i < N; ++i) {
			X[i] = sc.nextInt() * N;
			Y[i] = sc.nextInt() * N;
			sx += X[i];
			sy += Y[i];
		}
		sx /= N;
		sy /= N;
		for (int i = 0; i < N; ++i) {
			int dx = X[i] - sx;
			int dy = Y[i] - sy;
			if (X[(i + N / 2) % N] != sx - dx || Y[(i + N / 2) % N] != sy - dy) {
				System.out.println("NA");
				return;
			}
		}
		System.out.println((1.0 * sx / N) + " " + (1.0 * sy / N));
	}

}

Measured memory_bytes: 18380
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const int mod = 1000000007;
int n,k;
int a[200005];
ii A[200005];
ll ans = 1;
int take[200005];
bool allneg = true;
bool havezero = false;
int main(){
    cin >> n >> k;
    for (int i = 0; i <n ;i++) {
        cin >> a[i];
        if (a[i] >= 0) A[i] = ii(a[i],0);
        else A[i] = ii(-a[i],1);
        if (a[i] > 0) allneg = false;
        if (a[i] == 0) havezero = true;
    }
    if (allneg){
        if (k & 1){
            sort(a,a+n,greater<int>());
            for (int i = 0; i < n; i++) {
                if (a[i] == 0){
                    printf("0\n");
                    return 0;
                }
            }
        }
        else{
            sort(a,a+n);
        }
        for (int i = 0; i < k; i++) ans = (ans*a[i])%mod;
        ans = (ans+mod)%mod;
        printf("%lld",ans);
        return 0;
    }
    else if ( k== n){
        for (int i = 0; i < k; i++) ans = (ans*a[i])%mod;
        ans = (ans+mod)%mod;
        printf("%lld",ans);
        return 0;
    }
    sort(A,A+n,greater<ii>());
    int ct = 0;
    for (int i = 0; i < k; i++){
        ct += A[i].second;
        take[i] = 1;
    }
    if (ct & 1) {
        int P = -1,Q = -1,R = -1,S = -1;
        for (int i = k-1; i >= 0;i--){
            if (A[i].second && P == -1){
                P = i;
            }
            if (!A[i].second && Q == -1){
                Q = i;
            }
        }
        for (int i = k; i < n; i++){
            if (A[i].second && R == -1){
                R = i;
            }
            if (!A[i].second && S == -1){
                S = i;
            }
        }
        if (S == -1){
            ///force to remove pos, add neg
            take[R] = 1;
            take[Q] = 0;
        }
        else if (R == -1 || Q == -1){
            ///force to remove neg, add pos
            take[S] = 1;
            take[P] = 0;
        }
        else if ((ll)A[R].first*A[P].first > (ll)A[Q].first*A[S].first){
            ///better to take neg remove pos
            take[R] = 1;
            take[Q] = 0;
        }
        else{
            take[S] = 1;
            take[P] = 0;
        }
    }

    int taken = 0;
    for (int i = 0; i < n; i++){
        int x = A[i].first * (A[i].second?-1:1);
        //printf("%d %d\n",take[i],x);
        if (take[i]) {taken++; ans = (ans*x)%mod;}
    }
    if (ans < 0 && havezero) ans = 0;
    ans = (ans+mod)%mod;
    printf("%lld",ans);

}


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


int main(){
    string s;cin>>s;
    ll countb = 0;
    ll ans = 0;
    int n = s.size();
    rep(i,n){
        if(s[i]=='W') ans+=countb;
        else countb++;


    }
    cout<<ans<<endl;

}


Measured memory_bytes: 3724
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
 
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
      	int[] a=new int[n];
      
      for(int i=0;i<n;i++){
        a[i]=scan.nextInt();
      }
      
      int max=0;
      int count = 0;
      
      for(int i=0;i<n;i++){
        if(a[i]>=max){
          max=a[i];
          count=count+1;
        }
      }

        		System.out.println(count);
        
 
 
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional>
#define ll long long int
#define ld long double
#define pb push_back
#define pll pair<ll,ll>
#define pint pair<int,int>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define mod 1000000007
#define MAX 100000000
#define endl '\n'
#define mp make_pair
#define INF INT_MAX
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ff first
#define ss second
#define ps(x,y) fixed<<setprecision(y)<<x
#define setbits(x) __builtin_popcountll(x)            //counts no of ones in binary representation
#define w(t)     int t; cin>>t; while(t--)
#define pi 3.141592653589793238
#define sortt(v)  sort(v.begin(),v.end())
#define lb(v,x) std::lower_bound(v.begin(),v.end(),x)
#define ub(v,x) std::upper_bound(v.begin(),v.end(),x)

using namespace std;

int main(){
    fast;
    ll n,m,p,q,a,b,c,d;
    cin>>n;
    string s[n];
    forn(i,n)	cin>>s[i];
    int cnt0=0,cnt1=0,cnt2=0,cnt3=0;
    forn(i,n){
    	if(s[i]=="AC")	cnt0++;
    	else if(s[i]=="WA")	cnt1++;
    	else if(s[i]=="TLE")	cnt2++;
    	else	cnt3++;
	}
	cout<<"AC x "<<cnt0<<endl<<"WA x "<<cnt1<<endl<<"TLE x "<<cnt2<<endl<<"RE x "<<cnt3;
}

Measured memory_bytes: 6780
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main()
{
    int h,w;
    cin>>h>>w;
    char a[h+1][w+1];
    int dp[h+1][w+1];
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>a[i][j];
            dp[i][j]=0;
        }
    }
    
    int i=1;
    int j=1;
    
    // temp=a[i][j];
    while(a[i][j]!='#' && j<=w)
    {
       dp[i][j]=1;
       j++;
       
    }
    
    i=1;
     j=1;
    // temp=a[i][j];
    while(a[i][j]!='#' && i<=h)
    {
       dp[i][j]=1;
       i++;
       
    }
    
    for(int i=2;i<=h;i++)
    {
        for(int j=2;j<=w;j++)
        {
            if(a[i][j]=='.')
            dp[i][j]=((dp[i-1][j])%mod + (dp[i][j-1])%mod)%mod;
        }
    }
    
    cout<<((dp[h][w])%mod);
    
    
    
    
}

Measured memory_bytes: 5120
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();
                if (0 < a) {
                        System.out.println("Positive");
                } else {
                        if (0 < b) {
                                System.out.println("Zero");
                        } else {
                                if ((a - b) % 2 != 0 ) {
                                        System.out.println("Positive");
                                } else {
                                        System.out.println("Negative");
                                }
                        }
                }
        }
}

Measured memory_bytes: 10068
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
using namespace std;
typedef long long ll;
#define mod 2147493647
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b)
		cout << c << endl;
	else if (a == c) {
		cout << b << endl;
	}
	else
		cout << a << endl;
	return 0;
}

Measured memory_bytes: 256
# ABC109 C - Skip
n,k = map(int,input().split())
x = list(map(int,input().split()))
ans = 0
t = 0

def gcd(a,b):
  while b:
    a,b = b,a%b
  return abs(a)

for i in range(n):
    t = abs(x[i]-k)
    ans = gcd(ans,t)
print(ans)


Measured memory_bytes: 14224
#-*-coding:utf-8-*-

import math

def main():
    h = int(input())
    w = int(input())
    n = int(input())
    if w >= h:
        ans = math.ceil(n/w)
    else:
        ans = math.ceil(n/h)
    print(ans)

if __name__=="__main__":
    main()

Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>

int main( void )
{
    int n;
    int t, a;
    int x, y;
    int h[1000];
    double hd[1000];
    double min = 1e+14;
    double tmp;
    int min_idx = 0;
    scanf( "%d", &n );
    scanf( "%d%d", &t, &a );
    for ( int i = 0; i < n; i++ )
    {
        scanf( "%d", &h[i] );
    }
    for ( int i = 0; i < n; i++ )
    {
        tmp =   ( a - ( t - h[ i ] * 0.006 ) ) * ( a - ( t - h[ i ] * 0.006 ) ) ;
        if ( min > tmp)
        {
            min = tmp;
            min_idx = i;
        }
    }


    printf( "%d\n", min_idx + 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;
typedef long long ll;

int main() {
    int n;
    string s;
    int ans = 0;
    
    cin >> n >> s;
    
    rep(i, n-2) {
        if (s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C'){
            ans++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}




Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	final boolean DEBUG = false;
	final int INF = 100000000;
	final int MAX_N = 200;
	final int MAX_R = 1000;
	void run() {
		Scanner scan = new Scanner(System.in);
		while (true) {
			int n = scan.nextInt();
			int m = scan.nextInt();
			if (n + m == 0)
				return;

			int[][] land = new int[MAX_N + 1][MAX_N + 1];
			int[][] sea  = new int[MAX_N + 1][MAX_N + 1];
			for (int i = 0; i <= MAX_N; i++) {
				for (int j = 0; j <= MAX_N; j++)
					land[i][j] = sea[i][j] = INF;
			}
			for (int i = 0; i <= MAX_N; i++)
				land[i][i] = sea[i][i] = 0;

			for (int i = 0; i < m; i++) {
				int x = scan.nextInt();
				int y = scan.nextInt();
				int t = scan.nextInt();
				char sl = scan.next().charAt(0);
				if (sl == 'L')
					land[x][y] = land[y][x] = t;
				else
					sea[x][y] = sea[y][x] = t;
			}
		
			int r = scan.nextInt();
			int[] z = new int[MAX_R];
			for (int i = 0; i < r; i++)
				z[i] = scan.nextInt();
		
			for (int k = 1; k <= MAX_N; k++) for (int i = 1; i <= MAX_N; i++) for (int j = 1; j <= MAX_N; j++) {
				land[i][j] = Math.min(land[i][j], land[i][k] + land[k][j]);
				sea[i][j]  = Math.min(sea[i][j], sea[i][k] + sea[k][j]);
			}

			if (DEBUG) {
				System.out.println("land");
				for (int i = 1; i <= n; i++)
					for (int j = 1; j <= n; j++)
						System.out.print((land[i][j] == INF ? "X" : land[i][j]) + (j == n ? "\n" : " "));
				System.out.println("sea");
				for (int i = 1; i <= n; i++)
					for (int j = 1; j <= n; j++)
						System.out.print((sea[i][j] == INF ? "X" : sea[i][j]) + (j == n ? "\n" : " "));
			}

			int[][] dp = new int[MAX_R][MAX_N + 1];
			for (int i = 0; i < MAX_R; i++)
				for (int j = 0; j <= MAX_N; j++)
					dp[i][j] = INF;

			dp[0][z[0]] = 0;
			for (int i = 0; i < r - 1; i++) {
				for (int j = 1; j <= n; j++) {
					if (land[z[i]][z[i + 1]] != INF)
						dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + land[z[i]][z[i + 1]]);
					for (int k = 1; k <= n; k++)
						dp[i + 1][k] = Math.min(dp[i + 1][k], dp[i][j] + land[z[i]][j] + sea[j][k] + land[k][z[i + 1]]);
				}
			}

			if (DEBUG) {
				System.out.println("dp");
				for (int i = 0; i < r; i++)
					for (int j = 0; j <= n; j++)
						System.out.print((dp[i][j] == INF ? "X" : dp[i][j]) + (j == n ? "\n" : " "));
			}

			int ans = INF;
			for (int i = 0; i <= n; i++)
				ans = Math.min(ans, dp[r - 1][i]);
			System.out.println(ans);
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}
}



Measured memory_bytes: 68952
import bisect

s = input()
t = input()
n = len(s)
s += s

pos = [[] for _ in range(26)]

for i in range(len(s)):
    pos[ord(s[i]) - ord('a')].append(i)

ans = 0
now = -1
for i in range(len(t)):
    c = ord(t[i]) - ord('a')
    j = bisect.bisect_right(pos[c], now)

    if j == len(pos[c]):
        print(-1)
        exit()
    now = pos[c][j]

    if now >= n:
        now -= n
        ans += n
print(ans + now + 1)


Measured memory_bytes: 17980
N=int(input())
P=[]
for i in range(N):
	P.append(list(map(int,input().split())))
D=0
for i in range(N-1):
	for j in range(i+1,N):
		D+=(((P[i][0]-P[j][0])**2+(P[i][1]-P[j][1])**2)**(1/2))
print((D*2/N))

Measured memory_bytes: 3064
void main() {
	auto X = ri;
	int now;

	if(X % 105 == 0) {
		writeln(1);
		return;
	}

	auto tmp = X % 10;
	if(tmp % 5 == tmp || tmp == 5) now += 100 + tmp;
	else now += 200 + tmp;

	debug now.writeln;

	tmp = X % 100 / 10 * 10;
	now += tmp / 5 * 100;

	debug now.writeln;
	if(now > X) {
		writeln(0);
	} else writeln(1);
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
int main() {
	ll a, b,k,ans;
	cin >> a >> b>>k;
	for (int i = a; i <= min(b, a + k - 1); i++) {
		cout << i << endl;
	}
	for (int i = max(b - k + 1, a + k); i <= b; i++) {
		cout << i << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if 0 > x]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = MAP()
p = LIST()

tree = UnionFind(N)

for _ in range(M):
	x, y = MAP()
	tree.union(x-1, y-1)

ans = N
for i, x in enumerate(p):
	if not tree.same(x-1, i):
		ans -= 1

print(ans)


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

int main(){
  double a,b,c,m;
  cin>>a>>b;
  int tmp;
  tmp=(a+b)/2;
  c=tmp;
  m=(a+b)/2-c;
  
  if(m>=0.5){cout<<c+1<<endl;}
  else{cout<<c<<endl;}
  
  return 0;
}

Measured memory_bytes: 256
// B.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
	string s;
	cin >> s;
	int len = s.length();
	string ans(len, 'x');
	cout << ans << endl;
	return 0;
}


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

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

  if (N % 2 == 0)
    cout << N / 2 << endl;
  else
    cout << N / 2 + 1 << endl;

  return 0;
}

Measured memory_bytes: 256
#include<functional>
#include<algorithm>
#include<iterator>
#include<cstring>
#include<cstdio>
using namespace std;
int n;
int c[22222222];
char s[11111111],t[11111111];
long long werken(int cs,int ct)
{
	long long tmp=0;
	for(int i=0;i<n;++i)
	{
		++c[cs-ct+11111111];
		tmp+=cs-ct+11111111;
		if(s[i]!=s[i+1])++cs;
		if(t[i]!=t[i+1])++ct;
	}
	int cu=n,cd=0;
	long long res=1e18;
	for(int i=0;i<22222222;++i)
	{
		if((i&1)&&tmp<res)res=tmp;
		cu-=c[i];
		cd+=c[i];
		tmp-=cu;
		tmp+=cd;
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	scanf("%s%s",s,t);
	if(s[0]==t[0])printf("%lld",werken(0,0));
	else printf("%lld",werken(0,1));
	return 0;
}

Measured memory_bytes: 4224
import java.util.Scanner;

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

		for(int i=0; i<N; i++) {
			box[i]=sc.nextInt();
		}
		quick_sort(box,0,N-1);
		int[] sei=new int[N];
		int counter=0;
		int tmp1=-1;
		int ban=0;

		for(int i=0; i<N; i++) {
			if(tmp1!=box[i]) {
				tmp1=box[i];
				counter=1;
			}
			else {
				counter++;
				if(counter==2) {
					sei[ban]=tmp1;
					counter=0;
					ban++;
				}
			}
		}
		if(ban>=2) {
			long res=((long)sei[ban-1])*((long)sei[ban-2]);
			System.out.println(res);
		}
		else {
			System.out.println(0);
		}
	}

	static void quick_sort(int[] d, int left, int right) {
		if (left>=right) {
			return;
		}
		int p = d[(left+right)/2];
		int l = left, r = right, tmp;
		while(l<=r) {
			while(d[l] < p) { l++; }
			while(d[r] > p) { r--; }
			if (l<=r) {
				tmp = d[l]; d[l] = d[r]; d[r] = tmp;
				l++; r--;
			}
		}
		quick_sort(d, left, r);
		quick_sort(d, l, right);
	}
}

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

using namespace std;

#define maxn 100007
#define ll long long int
#define db(x) cout<<#x<<" -> "<<x<<" "<<endl
#define db2(x,y) cout<<#x<<"->"<<x<<", "<<#y<<" -> "<<y<<endl
#define db3(x,y,z) cout<<#x<<" -> "<<x<<" , "<<#y<<" -> "<<y<<" , "<<#z<<" -> "<<z<<endl
#define prt(x) for(auto it:x) { cout<<it<<" "; } cout<<endl
#define IN freopen("input.txt","r",stdin)

int main(){
    ios_base::sync_with_stdio(false) ;
    cin.tie(0);
//    IN ;
    int n,m;
    cin>>n>>m;
    vector< ll > V ;
    priority_queue < pair< ll , ll >  > pq;
    for(int i=1; i<=n; i++){
        ll x;
        cin>>x;
        V.push_back(x);
    }
    sort(V.begin(),V.end());
    for(int i=0; i<m; i++){
        ll a,b;
        cin>>a>>b;
        pq.push({b,a});
    }
    int idx = 0 ;
    ll ans = 0LL ;
    while( ! pq.empty() ){
        pair< ll , ll > T = pq.top() ;
        pq.pop() ;
        int c = T.first ;
        int amount = T.second  ;
        if( ( idx + amount ) < n ){
            if( V[ idx + amount ] < c ){ idx = idx+amount ; ans+=(1LL * c*amount) ; }
            else{
                int k = 0 ;
                int a = idx ;
                int i ;
                for(i=a; i < n; i++){
                    if(V[i] >=c ){ break ; }
                    idx++;
                }
                ans+=1LL * (idx-a) * c;
                break ;
            }
        }
        else{
            for(int i=idx ; i < n; i++){
                if( V[ i ] >= c){ break  ; }
                else{
                    ans+=(1LL  * c); idx++;
                }
            }
            break ;
        }
    }
    for(int i=idx; i <n; i++){
        ans+=V[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3188
house = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
n = int(input())
for i in range(n):
    b, f, r, v = map(int, input().split())
    house[b-1][f-1][r-1] += v

for i in range(4):
    for j in range(3):
        for k in range(10):
            print(" {}".format(house[i][j][k]), end='')
        print()
    if i != 4 - 1:
        print("#" * 20)



Measured memory_bytes: 5624
N = int(input())
if N == 1:
	print(int(input()) + int(input()))
	quit()
A = [list(map(int, input().split())) for i in range(2)]
dp = [[0] * N for i in range(N)]
for i in range(2):
	for j in range(N):
		dp[i][j] = A[i][j]
		if i > 0:
			dp[i][j] = max(dp[i][j], dp[i - 1][j] + A[i][j])
		if j > 0:
			dp[i][j] = max(dp[i][j], dp[i][j - 1] + A[i][j])
print(dp[1][N - 1])


Measured memory_bytes: 3064
x,n = gets.chomp.split(' ').map(&:to_i)
arr = gets.chomp.split(' ').map(&:to_i)
# point = x.clone
i = 0
min = 101
while true
  if !arr.include?(x-i)
    min = x-i
    break
  elsif !arr.include?(x+i)
    min = x+i
    break
  else
    i += 1
  end
end
p min

Measured memory_bytes: 14244
def delete_head_zeros(n):
	n = str(n)
	l = len(n)
	if "." in n:
		l = n.find(".")
	head_zeros = 0
	for i in range(l - 1):
		if n[i] == "0":
			head_zeros += 1
		else:
			break

	return n[head_zeros:]

# compare a, b
# a, b: int or string
def bigint_compare(a, b):
	a = delete_head_zeros(a)
	b = delete_head_zeros(b)
	if len(a) > len(b):
		return 1
	elif len(a) < len(b):
		return -1
	else:
		if a > b:
			return 1
		elif a < b:
			return -1
		else:
			return 0

# calculate a + b
# a, b: int or string
def bigint_plus(a, b):
	a = str(a)
	b = str(b)

	d = max([len(a), len(b)])
	a = '0' * (d - len(a)) + a
	b = '0' * (d - len(b)) + b

	ans = ""
	carry = 0
	for i in range(d):
		s = int(a[-i-1]) + int(b[-i-1]) + carry
		carry = s // 10
		ans = str(s % 10) + ans
	else:
		if carry:
			ans = str(carry) + ans

	return ans

# calculate a - b
# a, b: int or string
def bigint_minus(a, b): 
	a = str(a)
	b = str(b)
	M = []
	m = []
	sign = ""

	if len(a) > len(b) or (len(a) == len(b) and a >= b):
		[M, m] = [a, b]
	else:
		[M, m] = [b, a]
		sign = "-"
	m = '0' * (len(M) - len(m)) + m

	ans = ""
	borrow = 0
	for i in range(len(M)):
		s = int(M[-i-1]) - int(m[-i-1]) - borrow
		if s < 0:
			borrow = 1
			s += 10
		else:
			borrow = 0
		ans = str(s) + ans

	return sign + delete_head_zeros(ans)

# calculate a * b
# a, b: int or string
def bigint_multiply(a, b):
	a = str(a)
	b = str(b)

	md = []
	for j in range(len(b)):
		carry = 0
		mj = ""
		for i in range(len(a)):
			m = int(a[-i-1]) * int(b[-j-1]) + carry
			carry = m // 10
			mj = str(m % 10) + mj
		else:
			if carry:
				mj = str(carry) + mj
		md.append(mj)

	ans = 0
	for k in range(len(md)):
		ans = bigint_plus(md[k] + "0" * k, ans)

	return ans


# calculate a / b to d digits after decimal point
# a, b, d: int or string
def bigint_divide(a, b, d = 0):
	a = str(a)
	b = str(b)
	d = int(d)
	if d < 0:
		d = 0

	ans = ""
	r = ""
	for i in range(len(a) + d):
		q = 0
		if i < len(a):
			r += a[i]
		elif i == len(a):
			ans += "."
			r += "0"
		else:
			r += "0"

		if bigint_compare(r, b) == -1:
			ans += str(q)
		else:
			while bigint_compare(r, b) >= 0:
				r = bigint_minus(r, b)
				q += 1
			ans += str(q)

	return delete_head_zeros(ans)

def main():
	N = input()
	print(
		bigint_divide(
			bigint_multiply(N, bigint_minus(N, 1))
			,2
		)
	)

main()

Measured memory_bytes: 9288
#ifndef UTIL_INCLUDED
#define UTIL_INCLUDED

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
// #define DEBUGGING

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }

namespace __init {

struct InitIO {
    InitIO() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifndef DEBUG_FILE
#ifdef DEBUGGING
#include "../debug.cpp"
#else
#define DEBUG(...) 0
#endif
#endif

#endif

VV<ll> children;

ll calc(ll now) {
    V<ll> dv;
    for(ll c : children[now]) dv.push_back(calc(c));
    DEBUG(now, dv);
    sort(ALLR(dv));
    ll ret = 0;
    for(ll i = 0; i < dv.size(); i++) chmax(ret, dv[i] + i);
    return ret + 1;
}

int main() {
    ll N;
    cin >> N;
    children.resize(N);
    for(ll i = 1; i < N; i++) {
        ll a;
        cin >> a;
        a--;
        children[a].push_back(i);
    }
    DEBUG(children);
    cout << calc(0) - 1 << endl;
    return 0;
}


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

int main() {
  int N,koko;
  int count=0,ans;
  string S;
  cin >> N >> S;
  ans=N;
  vector<int> siro(N);
  vector<int> kuro(N);
  for(int i=N-1; i>=0 ; i--){
    if(S.at(i)=='.'){
      count=count+1;
      siro.at(i)=count;
    }
    else{
      siro.at(i)=count;
    }
  }
  count=0;
  for(int i=0;i<N;i++){
    if (S.at(i)=='#'){
      count=count+1;
      kuro.at(i)=count;
      ans=min(ans,siro.at(i)+kuro.at(i)-1);
    }
    else{
      kuro.at(i)=count;
    }
  }
  ans=min(count,ans);
  if (N==1){
    cout << 0 << endl;
  }
  else{
    
  if((count==1)&&(S.at(N-1)==',')){
    cout << 1 << endl;
  }
  else{
    cout << ans << endl;
  }
    
  }
}

Measured memory_bytes: 2180
#include <stdio.h>
     
    int n,tmp,ans=10000 ;
     
    int main(void){
        
        scanf ("%d",&n) ;
        
        for (int i=0; i<=n; i++) {
            
            tmp = 0 ;
            int j = i ;
            int k = n-j ;
            
            while (j>=1) {
                
                tmp += j%6 ;
                j /= 6 ;
                
            }    
            
            while (k>=1) {
                
                tmp += k%9 ;
                k /= 9 ;
                
            }
            
            if (ans>tmp) {
                
                ans = tmp ;
                
            }
            
        }
     
        printf ("%d\n",ans) ;
        
        return 0 ;
        
    }

Measured memory_bytes: 128
n=int(input())
b=list(map(int, input().split()))

a=[]
ans=0
for i in range(n):
    if i ==0:
        a.append(b[i])
        
    elif i == n-1:
        a.append(b[n-2])

    elif 1 <= i and i < n-1:
            if b[i-1]>b[i]:
                a.append(b[i])
            elif b[i-1] <= b[i]:
                a.append(b[i-1])

print(sum(a))

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
  int R[MAX], n;

  cin >> n;
  for (int i = 0; i < n; i++) cin >> R[i];

  int margin = -2000000000;
  int min_R = R[0];

  for (int i = 1; i < n; i++) {
    margin = max(margin, R[i] - min_R);
    min_R = min(min_R, R[i]);
  }

  cout << margin << endl;

  return 0;
}


Measured memory_bytes: 3880
// inputに入力データ全体が入る
function Main(input) {
    // 1行目がinput[0], 2行目がinput[1], …に入る
    input = input.split("\n");
    tmp0 = input[0].split(" ");
    N = Number(tmp0[0]);
    ans=1110-N;
    console.log(ans);
     }        

    
  //*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
  Main(require("fs").readFileSync("/dev/stdin", "utf8"));
//   

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

 
int main() {
  string S,T,U;
  int A=0,B=0;
  cin >> S >> T >> A >> B >> U;
  if(U==S){
    cout << A-1 << " " << B << endl;
  }
  else if(U==T){
    cout << A << " " << B-1 << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mod7 1000000007
using namespace std;

void myfunc() {
    string s;
    cin >> s;
    if(*(s.end()-1)=='s')
    cout << s << "es" << endl;
    else
    cout << s << "s" << endl;
}

int main() {
    long t;
    t=1;
    //cin >> t;
    while(t--)
    myfunc();
    return 0;
}


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

using namespace std;

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

    y /= 1000;
    for (int i = 0; 10 * i <= y; i++) {
        for (int j = 0; 10 * i + 5 * j <= y; j++) {
            int k = n - i - j;
            if (k >= 0 && 10 * i + 5 * j + k == y) {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1" << endl;
    return 0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int, input().split()))
NO=0
ans=1

if 0 in A:
    print(0)
else:
    for i in range(N):
        ans*=A[i]
        if ans>10**18:
            NO=1
            print(-1)
            break

    if NO==0:
        print(ans)

Measured memory_bytes: 21640
def main():
    num, koware_num = map(int, input().split())
    data = set([int(input()) for i in range(koware_num)])
    dp = [0 for i in range(num + 1)]
    dp[0] = 1
    if 1 not in data:
        dp[1] = 1

    mod = 10 ** 9 + 7

    for i in range(2, num + 1):
        if i in data:
            continue
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod

    print(dp[num])



if __name__ == '__main__':
    main()

Measured memory_bytes: 59476
#include<stdio.h>
#include<math.h>

const double pi = 3.141592653589793;

int main()
{
	double hourlong,minutelong,hour,minute;
	scanf("%lf %lf %lf %lf",&hourlong,&minutelong,&hour,&minute);
	double hourangle,minuteangle;
	hourangle = hour*30 + minute/2;
	minuteangle = minute * 6;
	double delta;
	delta = abs(hourangle - minuteangle);
	if(delta > 180)
	{
		delta = 360 - delta;
	}
	//printf("%.10lf",delta);
	double result;
	result = sqrt(hourlong*hourlong + minutelong* minutelong - 2 * hourlong * minutelong * cos(pi*2*(delta/360)));
	printf("%.11f",result);
	return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>S;
	FORR(c,S) {
		FOR(i,N) {
			c++;
			if(c>'Z') c='A';
		}
	}
	cout<<S<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main()
{
    int a,b;
    cin >> a;
    cin >> b;
    if(a>b)
    {
        for(int i=0; i<a; i++)
        {
            cout << b;
        }
    }
    else if (a==b)
    {
        for(int i=0; i<a; i++)
        {
            cout << b;
        }
    }
    else
    {
        for(int i=0; i<b; i++)
        {
            cout << a; 
        }
    }
    return 0;
}


Measured memory_bytes: 256
from itertools import*
n,c=map(int,input().split())
cost=[list(map(int,input().split()))for i in range(c)]
d=[[0]*c for i in range(3)]
for i in range(n):
    for j,v in enumerate(map(int,input().split())):
        d[(i+j)%3][v-1]+=1
print(min(sum(cost[j][cmb[i]]*d[i][j]for j in range(c)for i in range(3))for cmb in permutations(range(c),3)))

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<iomanip>
#include <math.h>
using namespace std;

int main(){
    int x,y;
    cin>>x>>y;
    if((y-2*x)%2==0&&(y-2*x)/2>=0&&(4*x-y)%2==0&&(4*x-y)/2>=0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3588
#include <cstdio>

int main(){
    int n;
    scanf("%d",&n);
    int d[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&d[i]);
    }
    int count = 0;
    bool e[n];
    for(int i = 0; i < n; i++){
        e[i] = true;
    }
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(e[i] == true && e[j] == true && d[i] == d[j]){
                count++;
                e[j] = false;
            }
        }
    }
    printf("%d\n",n - count);

    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())

l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
p=list(map(int,input().split()))

ans=0

def dfs(i,f):
    global ans
    if i==n-1:
        a=0
        for j in range(len(l)):
            sw=p[j]+1
            x=l[j][1:]
            for k in x:
                if f[k-1]=="1":
                    sw+=1
            #print(sw)
            if sw%2:
               a+=1
        #print(a)
        if a==len(p):
            ans+=1
        return 0
    else:
        dfs(i+1,f+"0")
        dfs(i+1,f+"1")

dfs(0,"0")
dfs(0,"1")
print(ans)

Measured memory_bytes: 3188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC133B
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int D = int.Parse(input[1]);
            int[][] x = new int[N][];
            for (int i = 0; i < N; i++)
            {
                x[i] = Console.ReadLine().Split().Select(a => int.Parse(a)).ToArray();
            }

            double[,] dp = new double[N + 1, N + 1];

            List<double> ans = new List<double>();

            for (int i = 0; i < N; i++)
            {
                for (int j = i+1; j < N; j++)
                {
                    for (int k = 0; k < D; k++)
                    {
                    dp[i, j] += Math.Pow(x[i][k] - x[j][k],2);
                    }
                    ans.Add(dp[i, j]);
                }
            }
            ans.Sort();
            int count = 0;
            double max = ans.Max();
            int max2 = (int)Math.Sqrt(max)+1;
            foreach (var item in ans)
            {
                for (int i = 1; i < max2; i++)
                {
                    if (i* i == (int)item)
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13652
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	string S;
	ll K;
	char ans;

	cin >> S >> K;

	rep(i, (int)S.length()) {
		if (S[i] == '1') {
			if (i + 1 == K) {
				ans = '1';
				break;
			}
		}
		else {
			ans = S[i];
			break;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace Aojx
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string s;
            while ((s = Console.ReadLine()) != null)
            {
                var r = s.Split(',').Select(e => double.Parse(e)).ToList();
                double x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3],
                xq = r[4], yq = r[5];

                if (x1 != x2)
                {
                    var la = (y2 - y1) / (x2 - x1);
                    var lb = y1 - la * x1;

                    var y = (2 * la * xq - (1 - Math.Pow(la, 2)) * yq + 2 * lb) /
                            (1 + Math.Pow(la, 2));
                    var x = xq + la * yq - la * y;

                    Console.WriteLine("{0:F6} {1:F6}", x, y);
                }
                else
                {
                    var y = yq;
                    var x = 2 * x1 - xq;

                    Console.WriteLine("{0:F6} {1:F6}", x, y);
                }
            }
        }
    }
}

Measured memory_bytes: 6112
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<functional>
using  namespace std;
typedef long long ll;
#define sc(x) scanf("%d",&x)
#define pd(x) printf("%d\n",x)
const int INF=1e9+10;
const int MOD=1e9+7;
const double eps=1e-5;
const double pi=acos(-1.0);
const int N=2e5+5;
ll p,a[N],sum[N],s[N];
int n;
int lowbit(int i)
{
    return i&(-i);
}
void update(int i)
{
    while(i<=n)
    {
        sum[i]+=1;
        i+=lowbit(i);
    }
}
ll get_sum(ll i)
{
    ll ans=0;
    while(i)
    {
        ans+=sum[i];
        i-=lowbit(i);
    }
    return ans;
}
int main()
{
    while(~scanf("%d%lld",&n,&p))
    {
        memset(sum,0,sizeof(sum));
        memset(s,0,sizeof(s));
        ll ans=0,Ans=0;
        a[0]=0;
        s[0]=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
            a[i]-=p;
            a[i]+=a[i-1];
            s[i]=a[i];
        }
        n++;
        sort(s,s+n);
        int k=unique(s,s+n)-s;
        for(int i=n; i>=1; i--) a[i]=a[i-1];
        for(int i=1; i<=n; i++) a[i]=(lower_bound(s,s+k,a[i])-s)+1;
        for(int i=1; i<=n; i++)
        {
            update(a[i]);
            ll tmp=get_sum(a[i]);
            ans+=tmp-1;//i前面小于等于a[i]的数个数
            Ans=i-tmp;
//        printf("i==%d a[i]==%lld tmp==%lld  ans==%lld\n",i,a[i],tmp,i-tmp);
        }
        printf("%lld\n",ans);
//        printf("%lld\n",Ans);//求逆序数
    }
    return 0;
}


Measured memory_bytes: 4992
# 解説通りに組んでみた
H, W = gets.split.map(&:to_i)
# ＃で埋めた配列を作る
b = Array.new(H + 2){Array.new(W + 2){"#"}}
# 入力された文字列を挿入する
H.times do |i|
    a = gets.chomp.split("")
    b[i + 1][1..W] = a
end
# 配列を展開して出力
b.each do |s|
    puts s.join
end


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

using namespace std;

const int N = 5678;
const long long llinf = 1e18;

int n, a, b, p[N];
long long dp[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> a >> b;
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
  }
  ++n;
  p[n] = n;
  fill(dp + 1, dp + n + 1, llinf);
  for (int i = 0; i < n; ++i) {
    int foo = n + 1;
    long long cost = 0;
    for (int j = i + 1; j <= n; ++j) {
      if (p[j] > p[i]) {
        if (p[j] < foo) {
          dp[j] = min(dp[j], dp[i] + cost);
        }
        foo = min(foo, p[j]);
      }
      if (p[j] < p[i]) {
        cost += b;
      } else {
        cost += a;
      }
    }
  }
  cout << dp[n] << '\n';
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

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

using namespace std;

int main() {
  while(1){
    int n,m;
    cin>>n>>m;
    if(!n)break;
    vector<tuple<int,int>> v;
    REP(i,n){
      int d,p;
      cin>>d>>p;
      v.emplace_back(-p,d);
    }
    sort(begin(v),end(v));
    int sum=0;
    REP(i,n){
      int d,p;
      tie(p,d)=v[i];
      if(d <= m){
        m-=d;
      }else{
        sum += -p * (d-m);
        m=0;
      }
    }
    cout<<sum<<endl;
  }
  return 0;
}

Measured memory_bytes: 1328
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 1000000007
#define bitcnt(a) (ll) __builtin_popcount((a))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main() {
  string s;
  ll a;
  cin >> s >> a;
  string b;
  for (int i = 0; i < s.size(); i += a) {
    b += s[i];
  }
  cout << b << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;

 ll n,m,k,p;
 vector<vector<mp> > g;

 vector<ll> daikus(ll s){
  priority_queue<mp,vector<mp>,greater<mp> > q;
  vector<ll> res(n,inf);
  q.push( mp(0,s) );
  while(!q.empty() ){
   mp now = q.top();
   q.pop();
   ll nn = now.second;
   ll cost = now.first;
   if( res[nn] != inf) continue;
   res[nn] = cost;
   for(ll i=0;i<g[nn].size();i++){
    ll next = g[nn][i].second;
    ll nec = cost + g[nn][i].first;
    if( res[next] != inf ) continue;
    q.push( mp( nec , next ) );
   }
  }

  return res;

 }

int main(){
 cin>>n>>m>>k>>p;
 p--;
 g = vector< vector<mp> > (n);
 for(ll i=0;i<m;i++){
  ll x,y,w;
  cin>>x>>y>>w;
  x--,y--;
  g[x].push_back( mp(w,y) );
  g[y].push_back( mp(w,x) );
 }

 vector<ll> s(k),t(k);
 for(ll i=0;i<k;i++){
  ll ss,tt;
  cin>>ss>>tt;
  ss--,tt--;
  s[i] = ss;
  t[i] = tt;
 }

 vector<ll> st = daikus( p );
 vector<vector<ll> > dp( 1<<(2*k) , vector<ll>(2*k,inf) );
 for(ll i=0;i<k;i++){
  dp[ (1<<i) ][i] = st[ s[i] ];
 // cout<<st[s[i]]<<endl;
 }

 /*
 for(ll i=0;i<(1<<(2*k));i++){
  for(ll j=0;j<2*k;j++)cout<<dp[i][j]<<' ';
  cout<<endl;
 }*/
 for(ll i=0;i<k;i++) s.push_back( t[i] );
 
 vector<vector<ll> > gg(2*k,vector<ll>(2*k) );
 
 for(ll i=0;i<2*k;i++){
  st = daikus( s[i] );
  for(ll j=0;j<2*k;j++) gg[i][j] = st[ s[j] ];
 }

 for(ll i=0;i<(1<<(2*k) );i++){
  for(ll j=0;j<2*k;j++){
   if( dp[i][j] == inf ) continue;
   
   for(ll l=0;l<k;l++){
    if( (i>>l)& 1 ){
    }else{
   //  cout<<"go"<<j<<' '<<l<<endl;
     dp[i | (1<<l)][l]  = min( dp[ i | (1<<l)][l] , dp[i][j] + gg[j][l] );
    }
   }

   for(ll l=0;l<k;l++){
    if( (i>>l)&1 ){
     if( (i>>(l+k) )&1 ){
     }else{
 //     cout<<"go"<<j<<' '<<l+k<<endl;
      dp[i | (1<<(l+k) )][l+k] = min( dp[i | (1<<(l+k) ) ][l+k] , dp[i][j] + gg[j][l+k] );
     }
    }
   }

  }
 }

 ll ans = inf;
 for(ll i=k;i<2*k;i++) ans = min( ans , dp[ (1<<(2*k) )-1][i] );
 if( ans == inf) cout<<"Cannot deliver"<<endl;
 else cout<<ans<<endl;
 
 /*
 for(ll i=0;i<2*k;i++){
  for(ll j=0;j<2*k;j++){
   cout<<gg[i][j]<<' ';
  }
  cout<<endl;
 }
 
 for(ll i=0;i<(1<<(2*k));i++){
  cout<<i<<' ';
  for(ll j=0;j<2*k;j++)cout<<dp[i][j]<<' ';
  cout<<endl;
 }*/

  return 0;
}



Measured memory_bytes: 3680
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

N,M=map(int,input().split())

class UnionFind():
	def __init__(self, n):
		self.parents = np.array([-1]*n)

	def find(self, x):
		if self.parents[x] < 0:
			return x

		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)

		if x == y:
			return

		if self.parents[x] > self.parents[y]:
			x, y = y, x

		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return abs(self.parents[self.find(x)])
      
      
uf=UnionFind(N)
for i in range(M):
  A,B=map(int,input().split())
  uf.union(A-1,B-1)
  
print(len(uf.parents[uf.parents<0])-1)

Measured memory_bytes: 28340
// Last Change: 02/16/2019 21:09:01.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

int main() {
  int N, M, K;
  cin >> N >> M;
  vector<int> A(M, 0);
  for (int i = 0; i < N; ++i) {
    cin >> K;
    for (int j = 0; j < K; ++j) {
      int input;
      cin >> input;
      --input;
      ++A[input];
    }
  }
  int count = 0;
  for (int i = 0; i < M; ++i) {
    if (A[i] == N) {
      ++count;
    }
  }
  cout << count << endl;

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 256