akhauriyash/Code-Regression huggingface dataset:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

H,N = myinput()
AB = mylistinput(N)

AB_sorted = mysort(AB,0,True)
# pprint(AB_sorted)
maxA = AB[0][0]
# print(maxA)
HA = H+maxA

# dp[i]: 敵の体力をiだけ減らすとしたときの，消耗魔力累計値の最小値
dp = [float("inf")]*(H+1)
dp[0] = 0

for i in range(1,H+1):
    for j in range(N):
        a = AB[j][0]
        b = AB[j][1]
        if i<a:
            dp[i] = min( dp[i], dp[0]+b )
        else:
            dp[i] = min( dp[i], dp[i-a]+b )
# print(dp)
ans = dp[H]
print(ans)

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vi a(n),b(n),c(n);
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    rep(i,n) cin>>c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    vll cnt(n+1);
    rep(i,n){
        cnt[i] = c.end()-upper_bound(all(c),b[i]);
    }
    rep(i,n) cnt[n-i-1]+=cnt[n-i];
    ll ans=0;
    rep(i,n){
        int idx = upper_bound(all(b),a[i])-b.begin();
        ans+=cnt[idx];
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 2176
#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>;

int main() {
  string a;
  int q;
  cin >> a >> q;
  int rcount = 0;
  string tmp1 = "", tmp2 = "";
  vector<string> cs(2, "");
  string &front = cs[0];
  string &back = cs[1];
  rep(i,q){
    int t;
    cin >> t;
    if(t == 1){
      rcount++;
      auto tmp = front;
      front = back;
      back = tmp;
    }
    else{
      int f;
      string c;
      cin >> f >> c;
      if(f == 1){
        front += c;
      }
      else{
        back += c;
      }
    }
  }
  reverse(front.begin(), front.end());
  if(rcount%2){
    reverse(a.begin(), a.end());
  }
  cout << front + a + back << endl;
  return 0;
}


Measured memory_bytes: 1348
#include <iostream>

using namespace std;

int main()
{
	string S, T;

	cin >> S >> T;

	int N = S.size();
	int ans = 0;

	for (int i = 0; i < N; i++)
	{
		if(S[i] != T[i])
			ans++;
	}

	cout << ans << endl;

}

Measured memory_bytes: 3468
# https://atcoder.jp/contests/abc051/tasks/abc051_c
# C - Back and Forth

sx, sy, tx, ty = list(map(int, input().split()))

done_list = []
route_list = []

# 1回目
route_list += ['R'] * abs(sx - tx)
route_list += ['U'] * abs(sy - ty)
route_list += ['L'] * abs(sx - tx)
route_list += ['D'] * abs(sy - ty)

# 2回目（ひとつ大回り）
route_list += ['L']
route_list += ['U'] * (abs(sy - ty) + 1)
route_list += ['R'] * (abs(sx - tx) + 1)
route_list += ['D']
route_list += ['R']
route_list += ['D'] * (abs(sy - ty) + 1)
route_list += ['L'] * (abs(sx - tx) + 1)
route_list += ['U']

ans = ''.join(route_list)
print(ans)


Measured memory_bytes: 3188
lines = readlines.map{|line| line.split(' ').map(&:to_i)}
a=lines[0][0]
b=lines[1]
d=[]
for i in 1..100
  c=0
  for j in b
   c=c+(j-i)**2
  end
  d.push(c)
end
puts d.min

Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<list>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 28;
const double EPS = 1e-10;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

map<int, int> mp;

int func(int n)
{
	if (n % 2) return 3 * n + 1;
	else return n / 2;
}

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

	int ans = 1;
	mp.insert(make_pair(s, 1));

	while (1) {
		// << s << endl;

		int new_s = func(s);
		if (mp.find(new_s) != mp.end()) {
			break;
		}
		else {
			mp.insert(make_pair(new_s, 1));
		}
		ans++;
		s = new_s;
	}

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


Measured memory_bytes: 256
#python3

def main():
    n = int(input())
    g = [[-1 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            g[i][x-1] = y


    ans = -1
    for i in range(1<<n):
        honest = [0 for _ in range(n)]
        for j in range(n):
            if (i>>j) & 1:
                honest[j] = 1 
        
        flag = True 
        for j in range(n):
            if honest[j] == 1:
                for k in range(n):
                    if g[j][k] == -1:
                        continue
                    if g[j][k] != honest[k]:
                        flag = False
        if flag:
            ans = max(ans, honest.count(1))

    print(ans)

main()

Measured memory_bytes: 3188
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
 
s = S()
t = S()

result = "Yes"
for i in range(len(s)):
    if(s[i] != t[i]):
        result = "No"

print(result)

Measured memory_bytes: 9128
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f80 = __float80;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define pb push_back
#define rng(a) a.begin(),a.end()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define sz(x) (i64)(x).size()
#define bit(n) (1LL<<(n))
#define fi first
#define se second
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
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;}

i64 pow_mod(i64 n, i64 k, i64 m){
  i64 r = 1;
  for(;k;k>>=1){
    if(k&1) r=(r*n)%m;
    n=(n*n)%m;
  }
  return r;
}

i64 cal(vvi g, i64 n, i64 x){
  i64 ret = -1;
  vi visit(n,0);

  queue<i64> que;
  que.push(x);
  visit[x] = 1;

  while(!que.empty()){
    i64 cur = que.front();
    que.pop();
    for(auto nxt : g[cur]){
      if(visit[nxt]==0){
        que.push(nxt);
        visit[nxt] = visit[cur]+1;
        ret = visit[nxt];
      }else if(visit[nxt]==visit[cur])
        return -1;
    }
  }
  return ret;
}

void Main()
{
  i64 n;
  cin >> n;

  vvi g(n);

  rep(i,n) rep(j,n){
    char c;
    cin >> c;
    if(c=='1'){
      g[i].pb(j);
      g[j].pb(i);
    }
  }

  i64 ans = -1;

  rep(i,n){
    chmax(ans,cal(g,n,i));
  }
  cout << ans << endl;
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}


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

int kansu(int a){
  int i=0;
  int k=0;
  while(k+i+1<=a){
    i++;
    k+=i;
  }
  return i;
}

int main(){
  ll n;
  cin >> n;
  ll ans=0;
  
  ll x=n;
  for(ll i=2;i<=sqrt(n);i++){
    int k=0;
    while(x%i==0){
      x/=i;
      k++;
    }
    ans+=kansu(k);
  }
  if(x!=1) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 3652
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>

#define rep(i,N) for(int (i)=0;(i)<(N);(i)++)
#define MOD 1000000007

using namespace std;

int main(){
	int N, i;
	scanf("%d %d", &N, &i);
	printf("%d", N - i + 1);
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cassert>
#include<iostream>
#include<vector>
using namespace std;
typedef long long lint;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

const int N=4000;
typedef bitset<N> bs;
const lint MOD=998244353;

bs read(){
  string s;
  cin>>s;
  int l=s.length();
  bs ret;
  rep(i,l)ret[i]=s[l-i-1]=='1';
  return ret;
}

// a%b
bs rem(bs a,bs b){
  int hi=-1;
  rep(i,N)
    if(b[i])hi=i;
  assert(hi>=0);
  for(int i=N-hi-1;i>=0;--i)
    if(a[i+hi])a^=b<<i;
  return a;
}

bs gcd(bs a,bs b){
  while(b.count()!=0){
    a=rem(a,b);
    swap(a,b);
  }
  return a;
}

int main(){
  int n;
  cin>>n;
  bs x=read();
  vector<bs> s(n);
  rep(i,n)s[i]=read();
  bs g=s[n-1];
  rep(i,n-1)g=gcd(s[i],g);
  lint ans=0;
  lint cur=1;
  int hi=-1;
  rep(i,N)
    if(g[i])hi=i;
  rep(i,N-hi){
    if(x[i+hi])ans=(ans+cur)%MOD;
    cur=cur*2%MOD;
  }
  bs y=x^rem(x,g);
  bool lt=false; //x<y?
  for(int i=N-1;i>=0;--i){
    if(x[i]!=y[i]){
      lt=x[i]<y[i];
      break;
    }
  }
  if(!lt)ans=(ans+1)%MOD; // y<=x; counts y
  cout<<ans<<endl;
}


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

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

int ceildiv(int a, int b) {
    return (a + b - 1) / b;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << ceildiv(b - 1, a - 1) << endl;
    return 0;
}


Measured memory_bytes: 888
import numpy as np

n,k=map(int,input().split())
a=[int(x) for x in input().split()]
f=[int(x) for x in input().split()]

a.sort()
f.sort(reverse=True)

A=np.array(a)
F=np.array(f)
S=sum(a)

l,u=-1,f[0]*a[-1]
while l+1<u:
  m=(l+u)//2
  s=0
  if S-np.minimum(A,m//F).sum()<=k:
    u=m
  else:
    l=m

print(u)

Measured memory_bytes: 43644
import math
X = int(input())
N = int(math.sqrt(X))
Ans = 1
for i in range(1, N + 1):
    for j in range(2, int(math.log2(X))):
        if i ** j > X:
            break
        elif i ** j > Ans:
            Ans = i ** j
print(Ans)


Measured memory_bytes: 3444
n = int(input())
h = list(map(int, input().split()))
ans = 0

def hidarihasi(h):
    for i,j in enumerate(h):
        if j!=0:
            return i
def zero(h, start):
    for i,j in enumerate(h[start:]):
        if j==0:
            return i+start
    else:
        return len(h)

def mizuyari(h):
    global ans
    for i in range(hidarihasi(h), zero(h, hidarihasi(h))):
        h[i] = h[i] -1
    ans = ans + 1
    
    
while sum(h)!=0:
    mizuyari(h)
print(ans)


Measured memory_bytes: 3064
h, w = map(int, input().split())
mat = []
mat_1 = []
mat_2 = []
mat_3 = []
mat_4 = []

for i in range(h):
    line = list(input())
    mat.append(line)
# print(mat)

# すべて白の行を削除
for i in range(h):
    line = mat[i]
    if line.count(".") != w:
        mat_1.append(line)

# print(mat_1)

# 転置
for line in zip(*mat_1):
    mat_2.append(list(line))

# print(mat_2, len(mat_2))
# すべて白の行を削除
for i in range(len(mat_2)):
    line = mat_2[i]
    if line.count(".") != len(mat_2[0]):
        mat_3.append(line)

# print(mat_3)

# 転置
for line in zip(*mat_3):
    mat_4.append(list(line))

# 出力
for line in mat_4:
    print(*line, sep="")


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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        int N, M; cin >> N >> M;
        vector<vector<int>> G(N, vector<int>(N));
        rep(i, M) {
            int a, b; cin >> a >> b;
            a--; b--;
            G[a][b] = 1;
            G[b][a] = 1;
        }
        rep(i, N) rep(j, N) {
            if(i != j) G[i][j] = 1 - G[i][j];
        }
        vector<int> color(N);
        function<pii(int, int)> coloring = [&] (int now, int c) {
            pii res = make_pair(0, 0);
            color[now] = c;
            (c == 1 ? res.first : res.second) += 1;
            rep(i, N) if(G[now][i]) {
                if(not color[i]) {
                    pii tmp = coloring(i, c == 1 ? 2 : 1);
                    if(tmp.first < 0) return make_pair(-1, -1);
                    res.first += tmp.first;
                    res.second += tmp.second;
                } else if(color[i] == c) return make_pair(-1, -1);
            }
            return res;
        };
        vector<pii> group;
        rep(i, N) {
            if(not color[i]) {
                group.push_back(coloring(i, 1));
                if(group.back().first < 0) {
                    cout << -1 << endl;
                    exit(0);
                }
            }
        }

        vector<vector<int>> dp(group.size() + 1, vector<int>(N + 1));
        dp[0][0] = 1;
        rep(i, group.size()) {
            rep(j, N) {
                if(not dp[i][j]) continue;
                if(j + group[i].first <= N) dp[i + 1][j + group[i].first] = 1;
                if(j + group[i].second <= N) dp[i + 1][j + group[i].second] = 1;
            }
        }
        int ans = INF;
        rep(i, N + 1) {
            if(dp[group.size()][i]) set_min(ans, i * (i - 1) / 2 + (N - i) * (N - i - 1) / 2);
        }
        cout << ans << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        int n; cin>>n;
        vi b(n-1);
        rep(i,n-1)cin>>b[i];
        vi a(n);
        
        rep(i,n)
        {
                if(i==0)a[i]=b[i];
                else if(i==n-1)a[i]=b[n-2];
                else a[i]=min(b[i],b[i-1]);
        }
        int ans=0;
        each(it,a)ans+=it;
        cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	char pos='A';
	string in;
	while(cin>>in){
		if(in[0]==pos){
			pos=in[2];
		}else if(in[2]==pos){
			pos=in[0];
		}
	}
	cout<<pos<<endl;
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int A, B;
    cin >> A >> B;
    string S;
    cin >> S;
    bool iscan = true;
    for (int i=0; i<A; i++) {
        if (S[i] < '0' || S[i] > '9') {
            iscan = false;
        }
    }

    if (S[A] != '-') {
        iscan = false;
    }

    for (int i=A+1; i<=A+B; i++) {
        if (S[i] < '0' || S[i] > '9') {
            iscan = false;
        }
    }

    if (iscan) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3608
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: usize,
    }

    match n - (n / 10) * 10 {
        3 => {
            println!("bon");
        },
        0|1|6|8 => {
            println!("pon");
        }
        _ => {
            println!("hon");
        }
    }
}


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

ll n;
vector<ll>x,y;
vector<char>u;

void Rotate(){
    rep(i,n){
        //方向変換
        char nu;
        if(u[i]=='U')nu='R';
        if(u[i]=='R')nu='D';
        if(u[i]=='D')nu='L';
        if(u[i]=='L')nu='U';
        //座標変換
        ll nx = y[i];
        ll ny = 200000-x[i];
        y[i]=ny;x[i]=nx;u[i]=nu;
    }
    return;
}

ll solve1(){
    ll res = INF;
    vector<vector<P> >v1(200010);
    rep(i,n){
        ll now = x[i];
        v1[now].push_back({y[i],u[i]});
    }
    rep(i,200010){
        ll l = v1[i].size();
        if(l<=1)continue;
        sort(v1[i].begin(),v1[i].end());
        rep(j,l-1){
            if(v1[i][j].second=='U'&&v1[i][j+1].second=='D'){
                if(v1[i][j].first<v1[i][j+1].first){
                    chmin(res,(v1[i][j+1].first-v1[i][j].first)*5);
                }
            }
        }
    }
    return res;
}

ll solve2(){
    ll res = INF;
    vector<vector<P> >v2(400010);
    rep(i,n){
        ll now = x[i]+y[i];
        v2[now].push_back({y[i],u[i]});
    }
    rep(i,400010){
        ll l = v2[i].size();
        if(l<=1)continue;
        sort(v2[i].begin(),v2[i].end());
        rep(j,l-1){
            if(v2[i][j].second=='U'&&v2[i][j+1].second=='R'){
                if(v2[i][j].first<v2[i][j+1].first){
                    chmin(res,(v2[i][j+1].first-v2[i][j].first)*10);
                }
            }
        }
    }
    return res;
}

int main(){
    cin >> n;
    x.resize(n);
    y.resize(n);
    u.resize(n);
    rep(i,n)cin>>x[i]>>y[i]>>u[i];
    ll ans = INF;
    rep(t,4){
        ll val1 = solve1();chmin(ans,val1);
        ll val2 = solve2();chmin(ans,val2);
        Rotate();
    }
    if(ans==INF)cout<<"SAFE"<<endl;
    else cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 31600
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] t = new int[n];
        int[] x = new int[n];
        int[] y = new int[n];

        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }

        boolean canTravel = true;
        for (int i = 0; i < n; i++) {
            int time = 0;
            int distance = 0;
            if (i-1 < 0) {
                time = t[i];
                distance = Math.abs(x[i]) + Math.abs(y[i]);
            } else {
                time = t[i] - t[i-1];
                distance = Math.abs(x[i] - x[i-1]) + Math.abs(y[i] - y[i-1]);
            }


            if (time < distance) {// 移動する時間が足りない
                canTravel = false;
                break;
            }

            if (time % 2 != distance % 2) {
                canTravel = false;
                break;
            }
        }

        System.out.println(canTravel ? "Yes" : "No");
    }
}


Measured memory_bytes: 93204
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        private const long M = 1000000007;       // 素数(int範囲)

        static int N;
        static int K;

        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            N = int.Parse(s[0]);
            K = int.Parse(s[1]);

            int[] v = new int[N];
            s = Console.ReadLine().Split(' ');
            for (int i = 0; i < N; i++)
            {
                v[i] = int.Parse(s[i]);
            }

            int left = 0;
            int right = 0;
            for (int i = 0; i < N; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    if (v[i] < v[j])
                    {
                        left++;
                    }
                    else if(v[i] > v[j])
                    {
                        right++;
                    }
                }
            }

            long ans;

            checked
            {
                long m = K;
                m *= (K + 1);
                m /= 2;
                m %= M;

                long m0 = (K - 1);
                m0 *= K;
                m0 /= 2;
                m0 %= M;

                ans = right * m;
                ans %= M;

                ans += left * m0;
                ans %= M;
            }

            Console.WriteLine(ans);
        }
    }
}



Measured memory_bytes: 13140
from collections import deque
K = int(input())
Q = deque([i for i in range(1,10)])

for _ in range(K-1):
  q = Q.popleft()
  if q%10 != 0:
    Q.append(q*10+q%10-1)
  Q.append(q*10+q%10)
  if q%10 != 9:
    Q.append(q*10+q%10+1)
print(Q.popleft())

Measured memory_bytes: 11908
#include<iostream>
#include<string>
using namespace std;
int main() {
	int n;
	const int sp[] = { 5,7,5,7,7 };
	while (cin >> n, n){
		int a[41];
		for (int i = 0; i < n; i++) {
			string s; cin >> s;
			a[i] = s.size();
		}
		for (int i = 0; i < n; i++) {
			int cnt = 0, k = 0;
			for (int j = 0;; j++) {
				cnt += a[i + j];
				if (cnt == sp[k]) {
					k++;
					if (k == 5) {
						cout << i + 1 << endl;
						goto end;
					}
					cnt = 0;
				}
				else if (cnt > sp[k])break;
			}
		}
	end:;
	}
}

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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define LEN (1<<8)

using namespace std;

int G[7][5],dp[7][LEN];
int tmp_G[7][5];

inline int getCost(int x){ return ((x==3)?80:((x==2)?70:((x==1)?60:0))); }

inline bool isValid(int x,int y){ return ( 0 <= x && x < 5 && 1 <= y && y < 6); }

inline void push(int x,int y,int cnt){
  if( isValid(x  ,y  ) ) ( tmp_G[y  ][x  ]+=cnt ) %= 4;
  if( isValid(x+1,y  ) ) ( tmp_G[y  ][x+1]+=cnt ) %= 4;
  if( isValid(x  ,y+1) ) ( tmp_G[y+1][x  ]+=cnt ) %= 4;
  if( isValid(x+1,y+1) ) ( tmp_G[y+1][x+1]+=cnt ) %= 4;
}

inline void automatically_pusher(int tmp,int y){
  if( !( 1 <= y && y <= 4 ) ) return;
  int x = 0;
  while( x < 4 ){
    int cnt = tmp & ((1<<2)-1);
    tmp >>= 2;
    push(x,y,cnt);
    x++;
  }
}

int main(){
  cin.tie(0);
  std::ios::sync_with_stdio(0);
  int T;
  cin >> T;
  while(T--){
    rep(i,7)rep(j,5)G[i][j] = -1;
    REP(i,1,6)rep(j,5){
      cin >> G[i][j];
      G[i][j]--;
    }
    int answer = 0;
    rep(i,7)rep(k,LEN)dp[i][k] = -1;
    dp[0][0] = 0;
    REP(i,1,6)rep(pre,LEN)if(dp[i-1][pre]!=-1)rep(cur,LEN){
	rep(j,7)rep(k,5)tmp_G[j][k] = G[j][k];
	automatically_pusher(pre,i-1);
	automatically_pusher(cur,i);
	int cost = 0;
	rep(j,5)if(G[i][j]!=-1)cost+=getCost(tmp_G[i][j]);
	dp[i][cur] = max(dp[i][cur],dp[i-1][pre]+cost);
	answer = max(answer,dp[i][cur]);
      }
    cout << answer << endl;
  }
  return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <vector>

using namespace std;
typedef long long ll;


ll ans, mx, mn, flag, sum, cnt;
ll b[8];
int main(){
	ll n;
	cin>>n;
	ll a[n];
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	for(int i=0; i<n; i++){
		if(a[i]>=1 && a[i]<=399) b[0]++;
		else if(a[i]>=400 && a[i]<=799) b[1]++;
		else if(a[i]>=800 && a[i]<=1199) b[2]++;
		else if(a[i]>=1200 && a[i]<=1599) b[3]++;
		else if(a[i]>=1600 && a[i]<=1999) b[4]++;
		else if(a[i]>=2000 && a[i]<=2399) b[5]++;
		else if(a[i]>=2400 && a[i]<=2799) b[6]++;
		else if(a[i]>=2800 && a[i]<=3199) b[7]++;
		
	}
	
	
	for(int i=0; i<8; i++){
		if(b[i]>0) cnt++;
	}
	for(int i=0; i<n; i++){
		if(a[i]>=3200) ans++;
	}
	if(cnt==0)cout<<1<<" "<<ans+cnt<<endl;
	else cout<<cnt<<" "<<ans+cnt<<endl;
}


Measured memory_bytes: 256
//g++ -std=c++14 test.cpp -o test.out
//問題URL
//https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e
 
#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 = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

struct mint {
  LL x; 
  mint(LL x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(LL t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
 
LL N;
LL A[100000];
 
mint ans = 1;
 
void solve(){
	vector<int> c(N+1);
	c[0] = 3;
	for(int i=0;i<N;i++){
		if(c[A[i]]==0){//そんな組み合わせは存在しない
			ans = 0;
			return;
		}
		ans *= c[A[i]];
		c[A[i]]--;
		c[A[i]+1]++;
	}
}
 
int main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> A[i];
 
    solve();
 
    cout << ans.x << endl;
    return 0;
}

Measured memory_bytes: 1408
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int cnt = 0;
        char ch[] = new char[s.length()];
        int r = s.length();
        for (int i = 0; i < r; i++) {
            ch[i] = s.charAt(i);
        }
        for (int i = 0; i < r / 2; i++) {
            if (ch[i] != (ch[r - i - 1])) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 23892
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main()
{
    int n, T, c[2123], t[2123];

    cin >> n >> T;
    REP(i, n)
    {
        cin >> c[i] >> t[i];
    }
    int ans = 100000000;

    REP(i, n)
    {
        if (T >= t[i])
        {
            ans = min(c[i], ans);
        }
    }

    if (ans == 100000000)
        cout << "TLE" << endl;
    else

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

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

#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end() 
#define sz(v) (int)((v).size())
#define fs first
#define sd second

typedef long long ll;

typedef pair < int, int > pi;
typedef pair < pi, int > ppi;

typedef vector < int > vi;
typedef vector < vector < int > > vvi;
typedef vector < pi > vpi;
typedef vector < vpi > vvpi;
typedef vector < ppi > vppi;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

double get_time() {
	return 1.0 * clock() / CLOCKS_PER_SEC;
}

int main() {
	int n;
	string s;
	cin >> n >> s;
	int r_cnt = 0;
	int res = 0;
	for(char ch : s)
		r_cnt += (ch == 'R');
	for(int i = 0; i < r_cnt; i++) {
		if(s[i] == 'W')
			res++;
	}
	cout << res << '\n';

}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
int getDivCount(int);

int main()
{
    int N, A, tmp = 0;
    int res = 1;
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> A;
        tmp = getDivCount(A);
        if (tmp == 0)
        {
            cout << tmp << endl;
            return 0;
        }
        res = i == 0 ? tmp : res > tmp ? tmp : res;
    }
    cout << res << endl;
}
int getDivCount(int num)
{
    int count = 0;
    while (num % 2 == 0)
    {
        num /= 2;
        ++count;
    }
    return count;
}


Measured memory_bytes: 3616
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
s, t = 0, 0
x = []
for i in range(n):
    if a[i] < b[i]:
        ans += 1
        s += b[i] - a[i]
    elif a[i] > b[i]:
        x.append(a[i] - b[i])
x.sort(reverse = True)
if s == 0:
    print(0)
    exit()
for i in range(len(x)):
    t += x[i]
    ans += 1
    if s <= t:
        print(ans)
        exit()
print(-1)

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

using namespace std;


int main(){
	int n,anterior=-1,sat=0;
	cin>>n;
	vector<int>a,b,c;
	a.resize(n);
	b.resize(n);
	c.resize(n-1);
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	for(int i=0; i<n; i++){
		cin>>b[i];
	}
	for(int i=0; i<n-1; i++){
		cin>>c[i];
	}
	for(int i=0; i<n; i++){
		sat+=b[a[i]-1];
		if(a[i]-1 == anterior){
			sat+=c[anterior-1];
		}
		anterior = a[i];
	}
	cout<<sat<<endl;
	return 0;
}

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

using namespace std;

int main(){

  int n;
  cin >> n;
  vector<int> a(n);

  for(int i = 0; i < n; i++) cin >> a[i];
  
  const int INF = ~(1<<31);
  vector<int> dp(n,INF);

  for(int i = 0; i < n; i++){
    auto it = lower_bound(dp.begin(),dp.end(),a[i]);
    *it  = a[i];
  }
  cout << lower_bound(dp.begin(),dp.end(),INF) - dp.begin() << endl;

}



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

int main()
{
    int N;
    cin >> N;
    int max, min;
    vector<int> X(N);

    for (int i = 0; i < N; i++)
    {
        cin >> X.at(i);
    }

    sort(X.begin(), X.end());
    max = X.at(N - 1);

    vector<int> result(max);
    for (int i = 1; i <= max; i++)
    {
        int sum = 0;
        for (int j = 0; j < N; j++)
        {
            sum += (X.at(j) - i) * (X.at(j) - i);
        }
        result.at(i - 1) = sum;
    }

    sort(result.begin(), result.end());

    cout << result.at(0) << endl;
}


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

class Program
{
    public static void Main()
    {


        var line = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        var A = line[0];
        var B = line[1];

        var k = (A + B) / 2;

        if((A + B) % 2 == 0)
        {
            Console.WriteLine(k);
        }
        else
        {
            Console.WriteLine("IMPOSSIBLE");
        }

        
    }
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n,i,j,r,g,b,remove;
  remove=0;
  r=0;
  b=0;
  g=0;
  string s;
  cin >> n >> s;
  if(n<=3) cout <<'0';
  
  else{
  for(i=0;i<n;i++)
  {
  if(s.at(i)=='R') r++;
  if(s.at(i)=='G') g++;
  if(s.at(i)=='B') b++;
  }
    
  for(i=0;i<n-1;++i)
  {
    for(j=1;2*j<=(n-1-i);++j)
   {
   if(s.at(i)!=s.at(i+j) && s.at(i)!=s.at(i+2*j) && s.at(i+j)!=s.at(i+2*j)) remove++;
   }   
  }
  cout << r*g*b-remove;
 }

return 0;}

Measured memory_bytes: 3576
#include <iostream>

using namespace std;

int main() {
   int a ;
   cin >> a ;
   int p =0 ; 
   for ( int i = 1 ; i<=9 ;i++){ //10
    for ( int j = 1 ; j <= 9 ; j++)
    if (i*j==a){
        p=1 ;  ;
        break ; }
    if (p==1) break ; 
}if (p==0) cout<<"No" ;
else cout<<"Yes" ; 
    return 0;
}
    

Measured memory_bytes: 384
N=gets.to_i
A=Array.new(N,0),B=Array.new(N,0),ind=Array.new(N,0)
for i in 0..N-1
	ta,tb=gets.split(" ").map(&:to_i)
	A[i]=ta
	B[i]=tb
	ind[i]=i
end

ind=ind.sort {|x,y|(A[y]+B[y])<=>(A[x]+B[x])}
sgn=1
sum=0
for i in 0..N-1
	sum+=(sgn==1)? A[ind[i]] : -B[ind[i]]
	sgn*=-1
end
puts sum

Measured memory_bytes: 5736
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
n = int(input())
arr = list(map(int , input().split()))
q = int(input())
m = defaultdict(int)
for i in arr:
	m[i]+=1
ss = sum(arr)
for ii in range(q):
	b , c = map(int , input().split())
	temp = m[b]
	del m[b]
	m[c] += temp
	ss = ss - b*temp + c*temp
	print(ss)









Measured memory_bytes: 24132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  int n;
  cin >> n;
  int n_max=1e5+1;
  vector<int> ele;
  ele.pb(1);
  rep1(i,5) ele.pb(pow(9,i));
  rep1(i,6) ele.pb(pow(6,i));
  //  rep(i,ele.size()) cout << ele[i] << endl;
  queue<pair<int,int> > q;
  q.push(mp(0,0));
  int dist[n_max];
  rep(i,n_max) dist[i]=INT_MAX;
  dist[0]=0;

  while(!q.empty()){
    int kazu=q.front().first;
    int kyori=q.front().second;
    q.pop();
    rep(i,ele.size()){
      if(kazu+ele[i]>n) continue;
      if(kyori+1<dist[kazu+ele[i]]){
	dist[kazu+ele[i]]=kyori+1;
	//	cout << kazu+ele[i] << " " << kyori+1 << endl;
	q.push(mp(kazu+ele[i],kyori+1));
      }
    }
  }

  cout << dist[n] << endl;


  
  return 0;
    

}


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

ll solve() {
    string S;
    cin >> S;
    ll ans = 0;
    int l = 0, r = S.size()-1;
    while ( l < r ) {
        if ( S[l] == S[r] ) {
            l++, r--;
            continue;
        } else if ( S[l] == 'x' ) {
            ans++;
            l++;
        } else if ( S[r] == 'x' ) {
            ans++;
            r--;
        } else {
            return -1;
        }
    }
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  for (int i = 0; i < Q; i++){
    long long x;
    cin >> x;
    int s = 0, t = 0;
    long long sum = 0, ans = 0;
    while (1){
      while (t < N && sum + a[t] <= x){
        sum += a[t];
        t++;
      }
      ans += (t - s);
      sum -= a[s];
      s++;
      if (s >= N){
        break;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3640
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int N; int M;
	while(~scanf("%d%d", &N, &M)) {
		map<int, int> cnt;
		rep(i, N) {
			int X;
			scanf("%d", &X);
			++ cnt[X];
		}
		vector<vector<vi>> v(2, vector<vi>(M));
		for(auto p : cnt)
			v[p.second % 2][p.first % M].push_back(p.second);
		int ans = 0;
		rep(x, M) {
			int y = (M - x) % M;
			if(x >= y) continue;
			while(1) {
				bool update = false;
				rep(d, 4) {
					int a = d < 2, b = d % 2 == 0;
					auto &p = v[a][x], &q = v[b][y];
					if(!p.empty() && !q.empty()) {
						int t = p.back(), u = q.back();
						p.pop_back();
						q.pop_back();
						++ ans;
						if(t > 1)
							v[a ^ 1][x].push_back(t - 1);
						if(u > 1)
							v[b ^ 1][y].push_back(u - 1);
						update = true;
						break;
					}
				}
				if(!update) break;
			}
		}
		rep(a, 2) rep(x, M) {
			for(int &t : v[a][x]) {
				ans += t / 2;
				t %= 2;
			}
			v[a][x].erase(remove(v[a][x].begin(), v[a][x].end(), 0), v[a][x].end());
		}
		rep(x, M) {
			int y = (M - x) % M;
			if(x != y) continue;
			rep(a, 2) {
				ans += v[a][x].size() / 2;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}


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

int main()
{
	int h,w;
	cin>>h>>w;
	string s[h];
	for(int i=0; i<h; i++) cin>>s[i];
	for(int j=0; j<w+1; j++)cout<<"#";
	cout<<"#"<<endl;
	for(int p=0; p<h; p++){
		cout<<"#";
		cout<<s[p];
		cout<<"#"<<endl;
	}
	for(int r=0; r<w+1; r++)cout<<"#";
	cout<<"#"<<endl;
}


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

using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 200013
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define IINF 1000000000
#define mp make_pair
#define pb push_back
#define remove pop
#define all(x) x.begin(), x.end()

pair2 values[MAXN];

int main() {
	if (fopen("FILENAME.in", "r")) {
		freopen("FILENAME.in", "r", stdin);
		freopen("FILENAME.out", "w", stdout);
	}
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> values[i].first >> values[i].second;
	}

	double avg = 0;
	int total = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {

			total++;

			avg += sqrt((values[i].first - values[j].first) * (values[i].first - values[j].first) + (values[i].second - values[j].second) * (values[i].second - values[j].second));

		}
	}

	avg /= total;

	cout << setprecision(20) << avg * (n - 1) << endl;
}

//GCD GCD GCD USE GCD IN MATH

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int main(){
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) {cin >> a[i]; b[i] = a[i];}
    sort(a.begin(), a.end());
    for(int i = 0; i < n; i++){
        int num = b[i];
        int left = -1;
        int right = n - 1;
        while(right - left != 1){
            int middle = (left + right) / 2;
            if(a[middle] >= num) right = middle;
            else left = middle;
        }
        //cout << right << "\n";
        if(right < n / 2) cout << a[n / 2] << "\n";
        else cout << a[n / 2 - 1] << "\n";
    }
}

Measured memory_bytes: 4732
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;

#define ARRAY_MAX 505

ll gcd(ll x, ll y){

    if(y == 0){
        return x;
    }else{
        return gcd(y,x%y);
    }
}

int main(){

    ll n,k;
    cin >> n >> k;
    ll mod = 0;
    ll maxi = -1;
    bool ans;

    REP(i,n){
        ll tmp;
        cin >> tmp;
        maxi = max(maxi,tmp);
        mod = gcd(mod,tmp);
    }
    
    if(maxi < k){
        ans = false;
    }else{
        if(k % mod == 0){
            ans = true;
        }else{
            ans = false;
        }
    }
    if(ans){
        cout << "POSSIBLE" << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }



    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
count=0
s=[[0 for i in range(n)] for i in range(m)]

for j in range(n):
  L=list(map(int,input().split()))

  for i in range(1,L[0]+1):
    s[L[i]-1][j]=1

for i in range(m):
  if s[i]==[1]*n:
    count+=1

print(count)

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] array;
		array = br.readLine().split(" ");
		int n = Integer.parseInt(array[0]);//ロープの本数
		int l = Integer.parseInt(array[1]);//長さL
		ArrayList<Integer> list = new ArrayList<Integer>();//ロープのリスト

		for(String str:br.readLine().split(" ")){
			list.add(Integer.parseInt(str));
		}

		int index = -1;//ロープ2本の組み合わせでLの長さを超える最初の場所

		for(int i=0;i<n-1;i++){
			if(list.get(i)+list.get(i+1) >= l){
				index = i;
				break;
			}
		}

		if(index < 0){
			System.out.println("Impossible");
		}else{
			System.out.println("Possible");
			for(int i=0;i<index;i++){
				System.out.println(i+1);//indexより左をほどく
			}
			for(int i=n-1;index<i;i--){
				System.out.println(i);//indexより右をほどく
			}
		}

	}
//	public static void main(String[] args) throws Exception{
//		String answerText = "Possible";
//		ArrayList<Integer> answerList = new ArrayList<Integer>();
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		String[] array;
//		array = br.readLine().split(" ");
//		int n = Integer.parseInt(array[0]);//ロープの本数
//		int l = Integer.parseInt(array[1]);//長さL
//		TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
//
//		int cnt = 0;
//		for(String str:br.readLine().split(" ")){
//			map.put(cnt, Integer.parseInt(str));
//			cnt++;
//		}
//
//		int total = getLength(map);
//
//		while(true){
//			if(map.size() == 1){
//				break;
//			}
//			if(total >= l){
//				int first = map.firstKey();
//				int last = map.lastKey();
//				if(map.get(first) < map.get(last)){
//					total -= map.get(first);
//					answerList.add(first+1);
//					map.remove(first);
//				}else{
//					total -= map.get(last);
//					answerList.add(last);
//					map.remove(last);
//				}
//			}else{
//				answerText = "Impossible";
//				break;
//			}
//		}
//		System.out.println(answerText);
//		if(answerText.equals("Possible")){
//			for(Integer i:answerList){
//				System.out.println(String.valueOf(i));
//			}
//		}
//	}
//
//	private static Integer getLength(TreeMap<Integer,Integer> map){
//		int ret = 0;
//
//		for(int i:map.values()){
//			ret += i;
//		}
//		return ret;
//	}
}


Measured memory_bytes: 56180
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int mod=1e9+7;
                     // I'm in Love with Experience. 
void solve()
{
    ll N;cin>>N;
    ll A[N]; for(ll i=0;i<N;++i)cin>>A[i];
    ll s=0,mx=A[0];
    for(ll i=1;i<N;++i)
    {
        if(mx>A[i])
        {
            s+=mx-A[i];
        }
        else
        {
            mx=A[i];
        }
    }
    cout<<s<<'\n';
}
int main(void)
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    solve();exit(0);
}/*Solved By:- Ritik Agarwal*/

Measured memory_bytes: 5172
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int n;
  ll k;
  cin >> n >> k;
  if (k == 1) {
    cout << 0 << endl;
    return 0;
  }
  vl cum(n + 1);
  cum[0] = 0;
  FOR(i, 1, n + 1) {
    ll a;
    cin >> a;
    cum[i] = cum[i - 1] + a;
  }
  map<int, ll> m;
  ll ans = 0;
  REP(i, min((int)k, n + 1)) { m[(cum[i] - i) % k]++; }
  for (auto i = m.begin(); i != m.end(); i++) {
    auto v = i->second;
    ans += v * (v - 1) / 2;
  }

  int i = min((int)k, n + 1);
  while (i <= n) {
    m[(cum[i] - i) % k]++;
    m[(cum[i - k] - (i - k)) % k]--;
    ans += m[(cum[i] - i) % k] - 1;
    i++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 14336
#include <iostream>

using namespace std;

int main()
{
    string line;
    cin >> line;
    int diff = 0;
    for (auto ch : line)
    {
        if (ch == '0')
        {
            diff++;
        }
        else
        {
            diff--;
        }
    }
    cout << (line.size() - abs(diff)) << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
int main()
{
int n,i;
  scanf("%d",&n);
 double a[n],mul,bo;
  mul=1;
  bo=0;
  
  for(i=0;i<n;++i)
  {
  scanf("%lf",&a[i]);
  mul=mul*a[i];
  }
  
   for(i=0;i<n;++i)
  {
  bo=bo+mul/a[i];
  }

  printf("%.7f",mul/bo);
  
return 0;
}

Measured memory_bytes: 1732