akhauriyash/Code-Regression huggingface dataset:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
f.sort(reverse=True)
hi=10**12
lo=0
def c(mi):
    tmp=0
    for i,j in zip(a,f):
        if mi//j<i:
            tmp+=i-mi//j
    if tmp<=k:
        return True
    return False
while hi>=lo:
    mi=(hi+lo)//2
    if c(mi):
        hi=mi-1
    else:
        lo=mi+1
print(lo)

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

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

    REP(i,100){
        REP(j,100){
            if(i*4+j*7==N){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

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

a = [ int( i ) for i in input().split() ]
#print( a )

sumA = int( 0 )
for ai in a:
    sumA += ai

ans = n - sumA

if ans >= 0:
    print( ans )
elif ans < 0:
    print( "-1" )


Measured memory_bytes: 9864
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;
const ll inf = 1001001001;
const ll mod = 1000000007;
 
int main() {
 int n;
 cin >> n;
 vector<ll>a(n);
 rep(i, 0, n)cin >> a[i];
 sort(a.begin(), a.end());
 int cnt = 0;
 ll sum = 0; 
 rep(i, 0, n-1){
     sum += a[i];
     if(sum*2 < a[i+1])cnt=i+1;
 }
 cout << n-cnt << endl;
}

Measured memory_bytes: 1024
package main

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

func process(max int) (ret int) {
	count := 0
	for a := 1; a < max; a++ {
		count += (max - 1) / a
	}
	return count
}

func scanNum() (n int) {
	fmt.Scanf("%d\n", &n)
	return
}

func scanStrings(n int) []string {
	sc := bufio.NewScanner(os.Stdin)

	ret := make([]string, n)
	for i := 0; i < n; i++ {
		if sc.Scan() {
			ret[i] = sc.Text()
		}
	}
	return ret
}

func main() {

	ret := process(scanNum())
	fmt.Println(ret)
}


Measured memory_bytes: 1860
//hail to jwalaji
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
   // cout<<"good 1: "<<endl;
    vector<int> arr[1000002];
    for(lli i=2;i<1000002;i++){
        if(arr[i].size()==0){
                lli k=i;
            while(k<1000002){
                arr[k].push_back(i);
                k+=i;
            }
        }
    }
    // cout<<"good 2: "<<endl;
    vector<lli> coun(1000002,0);
    lli n,maxa=0;
    cin>>n;
    for(lli i=0;i<n;i++){
        lli a;
        cin>>a;
        for(auto &k:arr[a]){
            coun[k]++;
            if(coun[k]>maxa){
                maxa=coun[k];
            }
        }
    }
    if(maxa>=n){
        cout<<"not coprime"<<endl;
    }
    else if(maxa==1||maxa==0){
        cout<<"pairwise coprime"<<endl;
    }
    else{
        cout<<"setwise coprime"<<endl;
    }
return 0;
}


Measured memory_bytes: 66512
import sys
input = sys.stdin.readline

n = int(input())
s = input()

for i in range(len(s)-1):
  res = chr(ord(s[i])+n)
  if ord(res) > ord("Z"):
    res = chr(ord(res)-ord("Z")+ord("A")-1)
  print(res,end="")

print("")

Measured memory_bytes: 4468
#include<stdio.h>
long key[251];
int main(){
    int i, h;
    scanf("%d", &h);
    for(i=1; i<=h; i++)scanf("%ld", &key[i]);
    for(i=1; i<=h; i++){
        printf("node %d: key = %d, ", i, key[i]);
        if(i!=1)printf("parent key = %d, ", key[i/2]);
        if(2*i<=h){
            printf("left key = %d, ", key[2*i]);
            if(2*i+1<=h)printf("right key = %d, ", key[2*i+1]);
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#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 equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int x, y, z;
  cin >> x >> y >> z;

  int ans = 0, res = y + 2 * z;
  while (res <= x) {
    ans++;
    res += y + z;
  }
  cout << ans << endl;




  
  return 0;
}

Measured memory_bytes: 256
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

ct = 0
for d in range(1,10):
    for i in range(3**d):
        k = i
        v = 0
        ptn = 0
        for j in range(d):
            if k % 3 == 0:
                v = v * 10 + 3
                ptn |= 1
            elif k % 3 == 1:
                v = v * 10 + 5
                ptn |= 2
            else:
                v = v * 10 + 7
                ptn |= 4
            k //= 3
        if v <= n and ptn == 7:
            ct += 1
print(ct)


Measured memory_bytes: 3064
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")


P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
int main(){
  char c;cin>>c;
  if(c == 'A')cout << "T" << endl;
  if(c == 'G')cout << "C" << endl;
  if(c == 'C')cout << "G" << endl;
  if(c == 'T')cout << "A" << endl;
}

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

using namespace std;

int main()
{
    string ox;
    int win = 0;
    cin >> ox;
    for (int i = 0; i < ox.size(); i++)
    {
        if (ox[i] == 'o')
        {
            win++;
        }
    }
    if (15 - ox.size() + win >= 8)
        printf("YES\n");
    else
        printf("NO\n");
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	vector<int> b(100001);
	vector<int> c(100001);
	rep(i,n){
		cin >> a.at(i);
		if(i%2==0) b.at(a.at(i))++;
		else c.at(a.at(i))++;
	}
	int x=0,maxx=0,y=0,maxy=0;
	rep(i,100001){
		if(maxx<=b.at(i)){
			maxx=b.at(i);
			x=i;
		}
		if(maxy<=c.at(i)){
			maxy=c.at(i);
			y=i;
		}
	}
	if(x==y){
		int d=0,e=0;
		maxx=0;
		maxy=0;
		rep(i,100001){
			if(maxx<=b.at(i) && i!=x){
				maxx=b.at(i);
				d=i;
			}
			if(maxy<=c.at(i) && i!=y){
				maxy=c.at(i);
				e=i;
			}
		}
		if(maxx>=maxy) x=d;
		else y=e;
	}
	int ans=0;
	rep(i,n){
		if(i%2==0 && a.at(i)!=x) ans++;
		if(i%2==1 && a.at(i)!=y) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
signed main(){
    int N; cin >> N;
    vector<int>H(N);
    int ans = 0;
    int cnt = 1;
    for(auto & e : H) cin >> e;
    reverse(all(H));
    for(size_t i = 1; i < H.size();++i){
        if(H[i] >= H[i-1]){
            cmax(ans,cnt++);
        } else {
            cnt = 1;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String args[]){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n + 1];
        int b[] = new int[m + 1];
        
        int x = sc.nextInt();
        int y = sc.nextInt();
        a[0] = x;
        b[0] = y;
        for(int i = 1; i < n + 1; i++){
            a[i] = sc.nextInt();
        }
        for(int i = 1; i < m + 1; i++){
            b[i] = sc.nextInt();
        }
        Arrays.sort(a);
        Arrays.sort(b);
        
        System.out.println(a[n] < b[0] ? "No War" : "War");
    }
}


Measured memory_bytes: 21844
#include<stdio.h>
int MIN(int a,int b){return a<b?a:b;}
int main(){
  int a=0,b=0,c=0,n,d,i,j;
  scanf("%d %d %d",&n,&i,&j);
  while(n--){
    scanf("%d",&d);
    if     (d<=i)a++;
    else if(d<=j)b++;
    else         c++;
  }
  printf("%d\n",MIN(MIN(a,b),c));
  return 0;
}
				  
   


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <ctype.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
typedef long long ll;
constexpr ll INF = 1000000000;
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n; cin >> n;
	vector<int>a(n);
	rep(i, n)cin >> a[i];
	

	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	int x = a[0];

	vector<int>count(x + 3);

	for (int i = 0; i < n; i++) {
		if (a[i] != 0) {
			count[a[i]]++;
			count[a[i] - 1]++;
			count[a[i] + 1]++;
		}
		else if (a[i] == 0) {
				count[a[i]]++;
				count[a[i] + 1]++;
				count[x + 2]++;
			}
	}

	sort(count.begin(), count.end());
	reverse(count.begin(), count.end());
	cout << count[0] << endl;
}

Measured memory_bytes: 1024
from operator import itemgetter
N = int(input())
cities = []

for i in range(N):
    x, y = map(int, input().split())
    cities.append((i, x, y))


edge = []
for k in (itemgetter(1), itemgetter(2)):
    cities.sort(key=k)
    for j in range(N-1):
        d = min(abs(cities[j+1][1]-cities[j][1]),
                abs(cities[j+1][2]-cities[j][2]))
        edge.append((cities[j][0], cities[j+1][0], d))
edge.sort(key=itemgetter(2))


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード

    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


uf = UnionFind(N)

ans = 0
for e in edge:
    if not uf.isSameGroup(e[0], e[1]):
        ans += e[2]
        uf.Unite(e[0], e[1])
print(ans)


Measured memory_bytes: 46612
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		long mod=1000000007;
		int[] a =new int[m];
		long[] dp=new long[n+1];
		dp[0]=1;
		for(int i=0; i<m; i++){
			a[i] = sc.nextInt();
			if(i!=0 && a[i]==a[i-1]+1){
				System.out.println(0);
				return;
			}
		}
		int count=0;
		boolean kk=false;
		for(int i=1; i<n+1; i++){
			if(m!=0 && !kk && i==a[count] && i!=n){
				count++;
				if(count>m-1){
					count=0;
					kk=true;
				}
				dp[i+1]=dp[i-1];
			}else{
				if(i==1){
					dp[i]+=dp[i-1];
					dp[i]%=mod;
					continue;
				}
				if(dp[i]==0){
					dp[i]+=dp[i-1]+dp[i-2];
					dp[i]%=mod;
				}
			}
		}
		System.out.println(dp[n]);
	}
}


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

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


    int max = Y / 1000;
    int x = max/10+1, y = max/5+1;
    bool ans = false;

    int i, j, k;
    for( i = 0; i < x && !ans; ++i ){
        for( j = 0; j < y && !ans; ++j ){
            k = N - (i+j);
            if( k < 0 ) continue;
            if( 10*i+5*j+k != max ) continue;
            ans = true;
            --i, --j;
        }
    }


    if( !ans ) i = j = k = -1;
    cout << i << " " << j << " " << k << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  int ans = C * (max(X, Y) * 2);
  if(X > Y) {
  for(int i = 0; i <= Y; i++) {
    ans = min(ans, (i * B) + (A * (i+(X-Y))) + C*2*(Y-i));
  }
  }
  else {
    for(int i = 0; i <= X; i++) {
    ans = min(ans, (i * A) + (B * (i+(Y-X))) + C*2*(X-i));
  }
  }
  cout << ans;
}

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

int main(int argc, const char * argv[]) {

    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);

    /////////////////////
    // Write code below /
    /////////////////////

    int balls;
    int colors;
    int result = 0;

    cin >> balls;
    cin >> colors;

    for (int i=0; i<balls; i++) {
        if (i==0) {
            result+=(colors);
        } else {
            result*=(colors-1);
        }
    }

    cout << result;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;class Main{public static void main(String[]a){int w=90,l;double x=0,y=0;for(Scanner s=new Scanner(System.in);s.hasNext();){String[] e=s.next().split(",");l=new Integer(e[0]);x+=l*Math.cos(Math.PI*w/180);y+=l*Math.sin(Math.PI*w/180);w-=new Integer(e[1]);}System.out.printf("%d\n%d\n",(int)x,(int)y);}}

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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define MOD 1000000007
#define INF (1ll<<60)
typedef pair<li, li> PI;

li val[100100][3];
li dp[100100][3];

int main(void)
{
	li n;
	cin >> n;
	rep(i, n) {
		rep(j, 3) {
			cin >> val[i][j];
		}
	}
	rep(i, 3) {
		dp[0][i] = 0;
	}
	for (li i = 1; i <= n; ++i) {
		rep(j, 3) {
			dp[i][j] = 0;
			rep(k, 3) {
				if (j == k)continue;
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + val[i - 1][j]);
			}
		}
	}

	cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;

	return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define lli long long int
#define endl "\n"
using namespace std;
int main()
{
  lli a,b,c=0,n;
  cin>>a>>n;
  for(int i=0;i<n;i++)
  {
    cin>>b;
    c+=b;
  }
  if(c<a)
  	cout<<"No";
  else
    cout<<"Yes";
  return 0;
}

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

#define rep(i, n) for(int i=0; i < n; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll=long long;


int main() {
  int n;cin >> n;
  string s,t;cin >> s >> t;
  string ans;

  rep(i,n){
    ans+=s[i];
    ans+=t[i];
  }
  cout << ans;
}

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

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

int main() {
	int N, M;
	cin >> N >> M;
	
	vector< int > A(N), B(M), C(N, 0);
	
	for_(i,0,N) cin >> A[i];
	for_(i,0,M) cin >> B[i];
	
	for_(i,0,M) {
		for_(j,0,N) {
			if (A[j] <= B[i]) {
				++C[j];
				break;
			}
		}
	}
	
	int ans = 0, mx = C[0];
	
	for_(i,1,N) if (mx < C[i]) {
		ans = i;
		mx = C[i];
	}
	
	cout << ans + 1 << endl;
	
	return 0;
}

Measured memory_bytes: 1204
import java.util.Scanner;

public class Main {
	public static void main(String [] args){
		//????????£?????????????????????
		Scanner sc = new Scanner(System.in);
		//??°?????????
		while(true){
			//??????????????????
			int H = sc.nextInt();
			//?¨????????????????
			int W = sc.nextInt();
			//?????¶??? ????????¨???0?????´?????????
			if(H == 0 && W ==0){
				break;
			}
			//?¨?????????°?????????
			for(int i = 0; i < H; i++){
				
			//???????????°?????????
				for(int j = 0; j < W; j++){
					//?????¶???
					//if(i == 0 || j == 0){
					if(j == 0 || j == W - 1 || i == 0 || i == H - 1){
						System.out.print("#");
					}else{
						System.out.print(".");
					}
				}
				System.out.println("");
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 32424
import sys
import fractions

n,k = map(int,input().split())
a = list(map(int,input().split()))

if k > max(a) :
  print('IMPOSSIBLE')
  sys.exit()
if k in a :
  print('POSSIBLE')
  sys.exit()
  
g = fractions.gcd(a[0],a[1])
for i in range(2,n) :
  g = fractions.gcd(g,a[i])
  
if k%g == 0 :
  print('POSSIBLE')
else :
  print('IMPOSSIBLE')

Measured memory_bytes: 16244
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll h,w,n;
vvl a;

int main(){
	cin>>h>>w>>n;
	a=vvl(h,vl(w));
	for(int i=0;i<n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		a[x-1][y-1]=w;
	}
	vl dp(w);
	for(int i=0;i<h;i++){
		vl DP(w);
		ll mx=0;
		vl b(3,-INF);
		for(int j=0;j<w;j++){
			mx=max(mx,dp[j]);
			b[2]=max(b[2],b[1]+a[i][j]);
			b[1]=max(b[1],b[0]+a[i][j]);
			b[0]=max(b[0],mx+a[i][j]);
			DP[j]=max({b[0],b[1],b[2]});
		}
		dp=DP;
	}
	cout<<dp[w-1]<<endl;
}

Measured memory_bytes: 74072
N, M = map(int,input().split())
A = [list(input()) for i in range(N)]
B = [list(input()) for i in range(M)]

Diff = N - M + 1
if Diff == 1 :
    if A == B :
        print("Yes")
    else :
        print("No")
    exit()

def partofA(i, j) :
    Ans = []
    for x in range(M) :
        Ansx = []
        for y in range(M) :
            Ansx.append(A[x+i][y+j])
        Ans.append(Ansx)
    return Ans

for i in range(Diff) :
    for j in range(Diff) :
        if partofA(i,j) == B :
            print("Yes")
            exit()

print("No")


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

struct edge {int to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
//static const int INF = 2147483647;
//static const int INf = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
static const int INF = 1000000000;
static const int NIL = -1;
static const int MOD = 1000000007;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define np next_permutation
#define pq priority_queue
#define itn int
#define scnaf scanf
#define reutnr return
#define scamf scanf
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
//#define int ll

signed main(){
    bool rullonz = false;
    char c[5];
    scanf("%s",&c);
    for(int i=0;i<4;i++){
        if(c[i]=='A' && c[i+1]=='C') rullonz = true;
    }

    if(rullonz) printf("Yes\n");
    else printf("No\n");
    return 0;
}

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

int main()
{
  string S,result;
  cin >> S;
  int index = S.length();
  if(S[index - 1 ]!='s'){
    result = S + "s" ;
  }else{
    result = S + "es";
  }

  cout << result << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

template<typename T>
struct Point {
	T x, y;
	Point(T x=0, T y=0):x(x), y(y) {}
	Point(std::pair<T, T> p): x(p.first), y(p.second) {}
	Point& operator+= (const Point &o){ x += o.x; y += o.y; return *this; }
	friend Point operator+ (Point a, const Point &b) { a += b; return a; }
	Point& operator-= (const Point &o){ x -= o.x; y -= o.y; return *this; }
	friend Point operator- (Point x, const Point &y) { x -= y; return x; }
	Point& operator*= (const T &a) { x *= a, y *= a; return *this; }
	friend Point operator* (const T a, Point x) { x *= a; return x; }
	Point& operator/= (const T &a) { x /= a, y /= a; return *this; }
	friend Point operator/ (Point x, const T a) { x /= a; return x; }
	T dot(const Point &o) const { return x*o.x+y*o.y; }
	T det(const Point &o){ return x*o.y-y*o.x; }
	// complex product
	Point cp(const Point &o) {
		complex<T> p = complex<T>(x, y) * complex<T>(o.x, o.y);
		return Point(p.real(), p.imag());
	}
	bool operator< (const Point &o) { return x<o.x || (x==o.x && y<o.y); };
};

typedef Point<double> P;
double dist2(P a, P b){
	return (a-b).dot(a-b);
}

vector<P> circles_intersections(P x1, double r1, P x2, double r2){
	P z = x2-x1;
	double d2 = dist2(z, P());
//	double cos = (r1*r1 + d2 - r2*r2)/(2*r1*sqrt(d2));
//	if(cos<-1 || 1<cos) return {};
//	P p(r1*cos, r1*sqrt(1-cos*cos));
//	vector<P> r{p, P(p.x, -p.y)};
//	for(P &t: r){
//		t = t.cp(z) / sqrt(d2) + x1;
//	}
//	return r;
	double a = (d2 + r1*r1 - r2*r2)/2;
	double b2 = d2 * r1*r1 - a*a;
	double c = d2;
	if(abs(b2) < 1e-10){
		return {P(a * z.x / c, a * z.y / c) + x1};
	}
	if(b2 < 0) return vector<P>();

	double b = sqrt(b2);
	return {P((a * z.x + z.y * b) / c,
			  (a * z.y - z.x * b) / c) + x1,
		   P((a * z.x - z.y * b) / c,
			 (a * z.y + z.x * b) / c) + x1};
}

int main(){
	int N, K;
	cin >> N >> K;
	vector<double> X(N), Y(N), C(N);
	for(int i=0; i<N; i++) cin >> X[i] >> Y[i] >> C[i];

	double lb = 0, ub = 1000000;
	double eps = 1e-8;
	for(int l=0; l<100; l++){
		double med = (lb+ub)/2;
		bool ok = false;
		vector<P> candidates;
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				vector<P> is = circles_intersections(P(X[i], Y[i]), med/C[i], P(X[j], Y[j]), med/C[j]);
				for(P p: is){
					candidates.push_back(p);
				}
			}
			candidates.push_back(P(X[i], Y[i]));
		}

		for(P p: candidates){
			int cnt = 0;
			for(int k=0; k<N; k++){
				if(C[k]*sqrt(dist2(P(X[k], Y[k]), p)) <= med+eps) cnt++;
			}
			if(cnt >= K){
				ok = true;
				debug(med, cnt, K, p.x, p.y);
			}
		}

		if(ok){
			ub = med;
		} else {
			lb = med;
		}
	}

	cout << setprecision(10) << lb << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef pair<double,double> PD;
typedef pair<int,P> ed;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
const double eps = 1e-10;
  
int main() {
  int N,A;
  cin >> N >> A;
  cout << N*N - A << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define IoFast ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long int
#define float long double
#define foor(i, a, b) for ( int (i) = (a); (i)<(b); (i)++ )
#define foor2(i, a, b) for( int (i) = (a); (i)>(b); (i)-- )
#define foorl(i, a, b) for ( ll (i) = (a); (i)<(b); (i)++ )
#define foorl2(i, a, b) for( ll (i) = (a); (i)>(b); (i)-- )
#define mp make_pair
#define f1 first
#define f2 second
#define pb push_back
#define pii pair<int,int>
#define vpii vector <pii>
#define vi vector<int>
#define sz(a) (int) a.size( )
#define fillArr(n, a) foor(i, 0, n) cin >> a[i];
#define print(a) cout << #a << endl;
#define umax(a,b) a = max ( a, b )
#define umin(a,b) a = min ( a, b )
#define all(k) k.begin ( ), k.end( )
#define rall(k) k.rbegin ( ), k.rend( )
#define clean(k) memset( k, 0, sizeof(k) )
#define endl '\n'
#define intt ll
 
const intt maxn = 1e10;
 
int main() {
    intt n;
    cin >> n;
    intt b = n;
    intt a = 0;
    while (b != 0) {
        b = b / 10;
        a++;
    }
    b = 0;
    foor (i,0,a) {
        intt c = 1;
        foor (j,0,i) {
            c *= 10;
        }
        b += 9 * c;
    }
    foor(i,0,10) {
        if(b <= n) {
            cout << 9 * a - i << endl;
            break;
        }
        b -= pow(10, a - 1);
    }
}

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

int main(){
long long N,a,b,c,d;
  cin>>N;
  a=N/3;
  b=N/5;
  c=N/15;
  d=N*(N+1)/2-3*a*(a+1)/2-5*b*(b+1)/2+15*c*(c+1)/2;
  cout<<d<<endl;
}
  

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define dbg(a,n) for(int i=1;i<=n;i++)printf("%d ",a[i]);printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e5+10,mod=1e9+7,inf=0x3f3f3f3f;
int n,m,k,t;
int a[maxn],b[maxn];
int main()
{
    int i,j;
    //freopen("in.txt","r",stdin);
    ll ret=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    deque<int>pq;
    pq.push_back(a[1]);
    for(i=n,j=2;i>=j;)
    {
        ret+=abs(a[i]-pq.front());
        pq.push_front(a[i--]);
        if(i>=j)ret+=abs(pq.back()-a[i]),pq.push_back(a[i--]);
        if(i>=j)ret+=abs(a[j]-pq.front()),pq.push_front(a[j++]);
        if(i>=j)ret+=abs(a[j]-pq.back()),pq.push_back(a[j++]);
    }
    pq.clear();
    ll ret1=0;
    pq.push_back(a[n]);
    for(j=1,i=n-1;i>=j;)
    {
        ret1+=abs(a[j]-pq.front());
        pq.push_front(a[j++]);
        if(i>=j)ret1+=abs(pq.back()-a[j]),pq.push_back(a[j++]);
        if(i>=j)ret1+=abs(a[i]-pq.front()),pq.push_front(a[i--]);
        if(i>=j)ret1+=abs(a[i]-pq.back()),pq.push_back(a[i--]);
    }
    printf("%lld\n",max(ret,ret1));
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int x,a,b;
    cin>>x>>a>>b;
    cout<<(x-a)%b<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
using ull = unsigned long long;
#define rep(i,n) for(ull i=0, i##_len=(n); i<i##_len; ++i)
#define repin(a,n) vector<ull> a(n);rep(i,n){cin>>a[i];}
#define in(a) ull a;cin>>a;
#define out(a) cout<<a;
int main()
{
	in(p);
	in(q);
	in(r);
	vector<ull> a = { p,q,r };
	sort(a.begin(), a.end());
	out(a[0] + a[1]);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <algorithm>
#include <iostream>
#define ll long long int
#define cases int t; cin >> t; while (t--)
#define fir for (ll i = 0; i < n; i++)
#define fira for (ll i = 0; i < n; i++) cin >> a[i]
#define firan ll n; cin >> n; ll a[n]; fira;
#define pb push_back
using namespace std;

int main()
{
    int n; cin >> n;
    vector <int> a;
    while (n > 0)
    {
        a.pb(n%10);
        n /= 10;
    }
    for (int i = a.size()-1; i >= 0; i--)
    {
        if (a[i] == 1) cout << 9;
        else cout << 1;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
s=input()
s=list(map(str,str(s)))
l=len(s)-1

for i in range(2**l):
    listA=['+']*len(s)
    for j in range(l):
        if ((i>>j)&1):
            listA[j]='-'
    listB=[]
    for o,p in zip(s,listA):
        listB.append(o)
        listB.append(p)
    del listB[-1]
    listC=''.join(listB)
    ans=eval(listC)
    if ans==7:
        print('{}=7'.format(listC))
        break



Measured memory_bytes: 3064
/**
 *    author:  tourist
 *    created: 23.05.2020 15:47:40       
**/
#include <bits/stdc++.h>

using namespace std;

const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, -1, 0, 1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> order(n * n);
  for (int i = 0; i < n * n; i++) {
    cin >> order[i];
    --order[i];
  }
  vector<vector<int>> mat(n, vector<int>(n, 1));
  vector<vector<int>> dist(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dist[i][j] = min(min(i, j), min(n - 1 - i, n - 1 - j));
    }
  }
  vector<pair<int, int>> que;
  vector<vector<int>> inq(n, vector<int>(n, 0));
  long long ans = 0;
  for (int id : order) {
    int i = id / n;
    int j = id % n;
    ans += dist[i][j];
    mat[i][j] = 0;
    que.clear();
    que.emplace_back(i, j);
    inq[i][j] = 1;
    for (int b = 0; b < (int) que.size(); b++) {
      int mi = que[b].first;
      int mj = que[b].second;
      inq[mi][mj] = 0;
      int val = dist[mi][mj] + mat[mi][mj];
      for (int dir = 0; dir < 4; dir++) {
        int ni = mi + di[dir];
        int nj = mj + dj[dir];
        if (ni >= 0 && nj >= 0 && ni < n && nj < n && val < dist[ni][nj]) {
          dist[ni][nj] = val;
          if (inq[ni][nj] == 0) {
            que.emplace_back(ni, nj);
            inq[ni][nj] = 1;
          }
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 9112
In = input().split()
n1 = int(In[0])
n2 = int(In[1])
sum = n1 + n2; minus = n1 -n2; mult = n1*n2
if sum >= minus and sum >= mult:
    print(sum)
if minus > sum and minus > mult:
    print(minus)
if mult > sum and mult > minus:
    print(mult)


Measured memory_bytes: 3060
import java.util.Arrays;
import java.util.Scanner;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    if(Math.abs(x-a)<Math.abs(x-b)){
      System.out.println("A");
    }else{
      System.out.println("B");
    }
  }
}

Measured memory_bytes: 22868
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string.h>
using namespace std;
using ll = long long;

#define right true
#define left false

int main()
{
  map<char, bool> a;
  a['q'] = right;
  a['w'] = right;
  a['e'] = right;
  a['r'] = right;
  a['t'] = right;
  a['a'] = right;
  a['s'] = right;
  a['d'] = right;
  a['f'] = right;
  a['g'] = right;
  a['z'] = right;
  a['x'] = right;
  a['c'] = right;
  a['v'] = right;
  a['b'] = right;
  a['y'] = left;
  a['u'] = left;
  a['i'] = left;
  a['o'] = left;
  a['p'] = left;
  a['h'] = left;
  a['j'] = left;
  a['k'] = left;
  a['l'] = left;
  a['n'] = left;
  a['m'] = left;
  string s;
  while (cin >> s, s != "#")
  {
    bool pre = a[s[0]];
    int sum = 0;
    for (int i = 1; i < s.size(); ++i)
    {
      if (pre != a[s[i]])
      {
        sum++;
      }
      pre = a[s[i]];
    }
    cout << sum << endl;
  }

  return 0;
}


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

    using namespace std;

    long long cost=1e18;
    vector<int>dist(200005);
    map<int,int>mp;
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin>>n;
        long long k;
        cin>>k;
        vector<int>a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
            --a[i];
        }
        int x=1;
        mp[0]=0;
        int start=0;
        int l,h;
        for(int i=0;i<=n;i++){
            dist[x]=a[start];
            if(mp.count(dist[x])>0){
                l=mp[dist[x]];
                h=x;
                break;
            }
            else
                mp[dist[x]]=x;
            x++;
            start=a[start];
        }
        if(k<h)
            cout<<dist[k]+1;
        else{
            int loop=h-l;
            k-=l;
            k=k%loop;
            cout<<dist[l+k]+1;
        }
        return 0;
    }


Measured memory_bytes: 13972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
const ll mod = 1e9+7;

ll dp[2097155];

main(){
    int n;cin>>n;
    int a[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    for(int i=1;i<(1<<n);i++) dp[i]=0;
    dp[0]=1;
    for(int mask=0;mask<(1<<n);mask++){
        int x = __builtin_popcount(mask);
        for(int j=0;j<n;j++){
            if(!(mask&(1<<j)) && a[x][j]) dp[mask^(1<<j)]+= dp[mask],dp[mask^(1<<j)]%=mod; 
        }
    }
    cout<<dp[(1<<n)-1];
}

Measured memory_bytes: 19964
'use strict'

function main(s) {

  s = s.split('\n');

  const nums = s[1].split(' ').map(n => Number(n));

  const copy_nums = nums.slice(0);
  copy_nums.sort((a, b) => a - b);

  const med1 = copy_nums[copy_nums.length / 2];
  const med2 = copy_nums[(copy_nums.length / 2) - 1];

  const ans = [];

  for (const n of nums) {
    if (med1 > n)  ans.push(med1);
    if (med1 <= n) ans.push(med2);
  }

  console.log(ans.join('\n'));
}

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


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

int main() {
    string s;
    getline(cin, s);
    for (int i = 0; i < s.size(); i++) {
        if (s[i]>='a'&&s[i]<='z') s[i] += 'A' - 'a';
        else if (s[i]>='A'&&s[i]<='Z') s[i] += 'a' - 'A';
    }
    cout << s << endl;
    return 0;
}


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

int l[50];
int main() {
	int n, k; scanf("%d%d", &n, &k);
	rep(i, n)scanf("%d", &l[i]);
	sort(l, l + n, greater<>());
	printf("%d\n", accumulate(l, l + k, 0));
}

Measured memory_bytes: 256
gets
a = gets.split.map(&:to_i)

colors = Hash.new(0)

a.each do |rate|
  case rate
  when 1..399
    colors[:gray] += 1
  when 400..799
    colors[:brown] += 1
  when 800..1199
    colors[:green] += 1
  when 1200..1599
    colors[:light_blue] += 1
  when 1600..1999
    colors[:blue] += 1
  when 2000..2399
    colors[:yellow] += 1
  when 2400..2799
    colors[:orange] += 1
  when 2800..3199
    colors[:red] += 1
  else
    colors[:others] += 1
  end
end

colors_num = colors.keys.length

if colors_num == 1 && colors.include?(:others)
  puts "1 #{colors[:others]}"
elsif colors.include?(:others)
  puts "#{colors_num - 1} #{colors_num - 1 + colors[:others]}"
else
  puts "#{colors_num} #{colors_num}"
end


Measured memory_bytes: 1788
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
using qll = queue<ll>;
using vb = vector<bool>;
using sll = stack<ll>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)
#define REP(i,n) for(long long i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define elnd endl //* missspell check
ll INF = 1LL << 60;


void dfs2(vector<vll> &G, vb &checked, vll &ts, ll u){
    checked[u] = true;
    for(auto v: G[u]){
        if(!checked[v])
            dfs2(G, checked, ts, v);
    }
    ts.push_back(u);
}

vll dfs_toposort(vector<vll> &G, vb &checked){
    ll N = G.size();
    fill(ALL(checked), false);
    vll ts;
    REP(i, N){
        if(!checked[i]){
            dfs2(G, checked, ts, i);
        }
    }
    reverse(ALL(ts));
    return ts;
}

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){
    vector<vll> G(N), Ginv(N);
    M += N-1;
    REP(i, M){
        G[A[i]].push_back(B[i]);
        Ginv[B[i]].push_back(A[i]);
    }
    //* topological sort
    vb checked(N, false);
    vll ts = dfs_toposort(G, checked);
    //* 
    vll tsinv(N);
    REP(i, N){
        //* vectex ts[i] --> position i
        tsinv[ts[i]] = i;
    }
    //* find parent
    REP(v, N){
        if(Ginv[v].empty())
            cout << 0 << endl;
        else{
            ll res = -1;
            for(auto x: Ginv[v]){
                res = max(res, tsinv[x]);
            }
            cout << ts[res]+1 << endl;
        }
    }

}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(N-1+M);
    std::vector<long long> B(N-1+M);
    for(int i = 0 ; i < N-1+M ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
        A[i]--; B[i]--;
    }
    solve(N, M, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 20344
#include "bits/stdc++.h"
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/10/11  Problem: N18_a  / Link:   ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL N;
int a[100005];
LL ans = 0LL;

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

	cin >> N;
	FOR(i, 0, N)cin >> a[i], a[i]--;
	FOR(i, 0, N - 1) {
		if (a[i] == i)swap(a[i], a[i + 1]), ans++;
	}

	if (a[N - 1] == N - 1)ans++;

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 768
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(m)]

bc = sorted(bc,key=lambda x:(x[1]),reverse=True)
count=0
for b,c in bc:
  count += b
  a.extend([c]*b)
  if count >= n:
    break
    
print(sum(sorted(a,reverse=True)[:n]))

Measured memory_bytes: 37704
def bb
	n = gets.chomp.to_i
	if    n <=      9 then puts n
	elsif n <=     99 then puts 9
	elsif n <=    999 then puts 9 +   n-100+1
	elsif n <=   9999 then puts 9 + 999-100+1
	elsif n <=  99999 then puts 9 + 999-100+1 +     n-10000+1
	elsif n <= 999999 then puts 9 + 999-100+1 + 99999-10000+1
#	elsif n <= 100000 then puts 90909
	end
end

bb

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

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<char>> vec(h,vector<char>(w));
  vector<vector<int>> tor(h,vector<int>(w));
  vector<bool> judge(h);
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> vec.at(i).at(j);
    }
  }
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      for(int k = 0; k < h; k++){
        if(vec.at(k).at(j) == '#'){
          tor.at(i).at(j) += 1;
          break;
        }
      }
      for(int k = 0; k < w; k++){
        if(vec.at(i).at(k) == '#'){
          tor.at(i).at(j) += 1;
          break;
        }
      }
    }
  }
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(tor.at(i).at(j) == 2){
        judge.at(i) = false;
        break;
      }
      else if(j == w - 1 && tor.at(i).at(j) != 2){
        judge.at(i) = true;
      }
    }
  }
  for(int i = 0; i < h; i++){
    if(judge.at(i)){
      continue;
    }
    for(int j = 0; j < w; j++){
      if(tor.at(i).at(j) == 2){
        cout << vec.at(i).at(j);
      }
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
from collections import deque

class UnionFind():
  def __init__(self, n):
    self.seg_tree = [-1] * n
  
  def root(self, i):
    if self.seg_tree[i] < 0:
      return i
    else:
      self.seg_tree[i] = self.root(self.seg_tree[i])
      return self.seg_tree[i]

  def size(self, i):
    return -self.seg_tree[self.root(i)]

  def unite(self, i, j):
    if self.same(i, j):
      return

    if self.size(i) == self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    elif self.size(i) > self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    else:
      self.seg_tree[self.root(j)] -= self.size(i)
      self.seg_tree[self.root(i)] = self.root(j)

  def same(self, i, j):
    return self.root(i) == self.root(j)

N, M = map(int, raw_input().split())
AB = [map(long, raw_input().split()) for _ in range(M)]

uf = UnionFind(N)
rev_res = []

ans = N * (N - 1) / 2
for a, b in reversed(AB):
  rev_res.append(ans)
  if not uf.same(a - 1, b - 1):
    ans -= uf.size(a - 1) * uf.size(b - 1)
  uf.unite(a - 1, b - 1)

for r in reversed(rev_res):
  print r

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

#define ll long long int
#define inv(name,Type,size) vector<Type> name(size);for(int index=0;index<n;index++) cin>>name[index];
#define F(a,n,i) for(int i=a;i<n;i++)
#define pb push_back
#define endl "\n"
#define mod 10000000007
#define modpro 99824435

const int d4i[4]={-1,0,1,0},d4j[4]={0,1,0,-1};
const int d8i[8]={-1,-1,0,1,1,1,0,-1},d8j[8]={0,1,1,1,0,-1,-1,-1};


void solve(){
	int n;
	cin>>n;
	//vector<vector<int>> dp(n,vector<int>(3));
	int dp[n][3];
	F(0,n,i)
		F(0,3,j) dp[i][j] = 0;
	vector<int> vals(3);
	for(int j=0;j<3;j++){
		cin>>dp[0][j];
	}
	F(1,n,i){
		for(int j=0;j<3;j++){
			cin>>vals[j	];
		}
		for(int j=0;j<3;j++){
			//dp[i][j] --> not 'j'
			for(int k=0;k<3;k++){
				if(j!=k) dp[i][j] = max(dp[i][j],vals[j] + dp[i-1][k]);
			}
		}
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}

int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  
  //int t;cin>>t;while(t--) solve(),cout<<endl;
  solve();
}



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

using namespace std;

int main()
{
	int A , B ,C , D;
	cin >> A >> B >> C >> D;
	
	int i = 1;
	while (A > 0 && C > 0)
	{
		if (i % 2 != 0)
		{
			C -= B;
		}
		else
		{
			A -= D;
		}
		i++;
	}

	if (A > 0)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
}

Measured memory_bytes: 3672
n = int(input())
a = list(map(int,input().split()))
b = {}
for x in a:
  try:
    if b[x]:
      b[x] += 1
  except:
    b[x] = 1
#print(b)
ans = sum(a)
q = int(input())
for _ in range(q):
  x,y = map(int,input().split())
  try:
    if b[x] != -1:
      bx = b[x]
      b[x] = 0
  except:
    #print(b)
    print(ans)
    continue
  try:
    if b[y] != -1:
      b[y] += bx
  except:
    b[y] = bx
  #print(b)
  ans += bx * (y-x)
  print(ans)

Measured memory_bytes: 85228
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)


void solve(std::string S){
    S[3] = '8';
    cout << S << endl;

}

int main(){

    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}



Measured memory_bytes: 256
icase=0
if icase==0:
    sa=list(input())
    sb=list(input())
    sc=list(input())
    ia=0
    ib=0
    ic=0
    card="a"
    while ia<=len(sa) and ib<=len(sb) and ic<=len(sc) :
        if card=="a":
            if ia==len(sa):
                print("A")
                break
            card=sa[ia]
#            print(ia,card)
            ia=ia+1
        elif card=="b":
            if ib==len(sb):
                print("B")
                break
            card=sb[ib]
#            print(ib,card)
            ib=ib+1
        elif card=="c":
            if ic==len(sc):
                print("C")
                break
            card=sc[ic]
#            print(ic,card)
            ic=ic+1


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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll x;
    cin >> x;
    for (ll a = -200; a <= 200; a++)
    {
        for (ll b = -200; b <= 200; b++)
        {
            if (a * a * a * a * a - b * b * b * b * b == x)
            {
                cout << a << " " << b << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 3644
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int m=0, f=0, r=0, i;
    for(i=0; ; i++){
        scanf("%d %d %d", &m, &f, &r);
        if(m==-1 && f==-1 && r==-1){
            break;
        }
        else if(m==-1 || f==-1){printf("F\n");
        }else if(m+f>=80){printf("A\n");
        }else if(m+f>=65&&m+f<80){printf("B\n");
        }else if(m+f>=50&&m+f<65){printf("C\n");
        }else if(m+f>=30 && m+f<50 && r>=50){printf("C\n");
        }else if(m+f>=30&&m+f<50){printf("D\n");
        }else{printf("F\n");
        }
    }
    return 0;
}

Measured memory_bytes: 584