akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

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

int d[210][210];

bool isOutOfRange(int y, int x, int h, int w){
	return y < 0 || y >= h || x < 0 || x >= w;
}

int main(){
	int h, w;
	cin>>h>>w;
	vector<string> vs(h);
	rep(i, h) cin>>vs[i];

	vector<pii> v;
	pii s, g;
	rep(i, h) rep(j, w) if(vs[i][j] == '$') v.pb({i, j});
	rep(i, h) rep(j, w) if(vs[i][j] == '@') s = {i, j};
	rep(i, h) rep(j, w) if(vs[i][j] == '%') g = {i, j};

	rep(i, 210) rep(j, 210) d[i][j] = INF;
	rep(i, v.size()){
		queue<pii> q;
		q.push(v[i]);
		d[v[i].fi][v[i].se] = 0;
		while(!q.empty()){
			pii p = q.front();	q.pop();
			int c = d[p.fi][p.se];
			rep(j, 4){
				int nx = p.se + dx[j], ny = p.fi + dy[j];
				if(isOutOfRange(ny, nx, h, w) || vs[ny][nx] == '#') continue;
				int nc = d[ny][nx];
				if(c+1 < nc){
					d[ny][nx] = c + 1;
					q.push({ny, nx});
				}
			}
		}
	}
	priority_queue<pair<int, pii>, vector<pair<int, pii> > , greater<pair<int, pii> > > q;
	pair<int, pii> p;
	set<pii> used;
	q.push({0, s});
	used.insert(s);
	while(!q.empty()){
		p = q.top(); q.pop();
		int c = p.fi;
		//cout<<" "<<p.se.fi<<" "<<p.se.se<<" "<<p.fi<<endl;
		rep(i, 4){
			int nx = p.se.se + dx[i], ny = p.se.fi + dy[i];
			if(isOutOfRange(ny, nx, h, w) || vs[ny][nx] == '#') continue;
			int nc = d[ny][nx];
			if(nc <= c+1 || used.count({ny, nx})) continue;
			if(g == (pii){ny, nx}){
				cout<<"Yes"<<endl;
				return 0;
			}
			q.push({c+1, {ny, nx}});
			used.insert({ny, nx});
		}
	}
	cout<<"No"<<endl;

	// for(int i = 0; i < h; i++){
	// 	for(int j = 0; j < w; j++){
	// 		printf("%3d", (d[i][j]==INF?-1:d[i][j]));
	// 	}
	// 	printf("\n");
	// }
}

Measured memory_bytes: 3724
#!python3


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

    dp = [[[0]*(size+1) for j in range(2)] for i in range(size+1)]

    dp[0][0][0] = 1
    for i in range(size):
        for less in range(2):
            for k in range(size):
                for x in range(10 if less else N[i] + 1):
                    #print((i, less, k), x, (i+1, int(less or x < N[i]), k + (1 if x else 0)))
                    dp[i+1][less or x < N[i]][k + (1 if x else 0)] += dp[i][less][k]
        #print(dp[i+1])

    print(dp[-1][0][K] + dp[-1][1][K])

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3428
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  int n; cin >> n;
  vector<int> a(n);
  vector<int> cnt(3, 0);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnt[a[i] % 3]++;
  }

  if (cnt[0] == n) {
    cout << 1 << endl;
    return 0;
  }
  
  lint ans = cnt[0];
  if (cnt[1] > cnt[2]) {
    swap(cnt[1], cnt[2]);
  }
  
  ans += cnt[1] + min(cnt[1] + 3, cnt[2]);
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 4688
#include <bits/stdc++.h>
using namespace std;
  
int main(){
  long long n;
  string res = "";
  cin >> n;
  if(n == 0) res += '0';
  long long i = 1;
  while(n){
    if(n % (2 * abs(i))){
      res += '1';
      n -= i;
    }else{
      res += '0';
    }
    i *= -2;
  }
  reverse(res.begin(), res.end());
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n,k;cin >> n >> k;
    vector<int> a(n);
    vector<ll> sum(n+1);
    for(int i=0;i<n;i++){
        cin >> a[i];
        sum[i+1]=sum[i]+a[i];
    }
    ll ans=0;
    vector<ll> c(40);
    c[0]=1;
    for(int i=1;i<40;i++){
        c[i]=c[i-1]*2;
    }
    for(int i=39;i>=0;i--){
        int cnt=0;
        for(int j=0;j<n;j++){
            for(int k=j+1;k<n+1;k++){
                ll x=(ans+c[i])&(sum[k]-sum[j]);
                if(x==ans+c[i]){
                    cnt++;
                }
            }
        }
        if(cnt>=k){
            ans+=c[i];
        }
    }
    cout << ans << endl;
}

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

class Program
{
    static void Main()
    {
        Console.WriteLine(Solve());
        return;
    }

    public static string Solve()
    {
        string b = Read();
        switch(b)
        {
            case "A":
                return "T";
            case "C":
                return "G";
            case "G":
                return "C";
            case "T":
                return "A";
        }
        return "";
    }

    private static string Read() { return Console.ReadLine(); }
    private static int ReadInt() { return int.Parse(Read()); }
    private static long ReadLong() { return long.Parse(Read()); }
    private static double ReadDouble() { return double.Parse(Read()); }
    private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
    private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
    private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
}


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

int main(){
  int n; cin>>n;
  int d[n];
  for(int i=0;i<n;i++){cin>>d[i];}
  
  sort(d,d+n);
  
  cout<<d[n/2]-d[n/2-1];
  
  return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  int N;
  double T, A;
  cin >> N >> T >> A;
  vector<int> H(N); REP(i, N) cin >> H[i];

  double ans = pow(10, 9) + 7;
  int cnt = 0;
  REP(i, N) {
    double d = T - H[i] * 0.006;
    // cout << "d " << d << endl;
    if(abs(A - d) < ans) {
      ans = abs(A - d);
      cnt = i + 1;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
n = int(input())
r = [int(input()) for _ in range(n)]
maxv = 10 ** 9 * (-2)
minv = r[0]

for i in range(1, n):
    maxv = max(maxv, r[i] - minv)
    minv = min(minv, r[i])

print(maxv)


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

ll solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N), B(M);
    for ( int i = 0; i < N; i++ ) cin >> A[i];
    for ( int i = 0; i < M; i++ ) cin >> B[i];
    vector<ll> C = atcoder::convolution(A, B);
    for ( int i = 0; i < C.size(); i++ ) {
        cout << (i != 0 ? " " : "") << C[i];
    }
    cout << "\n";

    return 0;
}

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

Measured memory_bytes: 27200
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int,int> P;
typedef long long ll; 

ll mod = 1e9 + 7;

int main(){
	int n;
	string s,t;
	cin >> n >>  s >> t;
	for(int i=0;i<n;i++){
		cout << s[i] << t[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
li = list(map(int, input().split()))
flag = 0
for i in reversed(range(n)):
    for j in range(i):
        if li[j] > li[j+1]:
            li[j], li[j+1] = li[j+1], li[j]
            flag += 1

print(*li)
print(flag)



Measured memory_bytes: 5612
#include <iostream>
#include <stdlib.h>
#include <stdio.h>      /* printf */
#include <math.h>       /* pow */
#include <vector>
#include <algorithm>

void print_array(std::vector<int> list)
{
  for(int i = 0; i < list.size(); ++i){
    if(i>0) std::cout << " ";
    std::cout << list[i];
  }
  std::cout << std::endl;
}

void BubbleSort(std::vector<int> &listToSort, int &swapCounter){
    for (int j=0; j < listToSort.size(); j++) {
        for (int k=listToSort.size()-1; k>j; k--) {
            if(listToSort[k]<listToSort[k-1]) {
                std::swap(listToSort[k],listToSort[k-1]);
                swapCounter++;
            }
        }
            
    }
}

int main(void){

    int num;
    std::cin >> num;
    if (num>100) {
        std::cout << "list too big" << std::endl;
        return 1;
    }
    std::vector<int> list;
    for(int i = 0; i < num; i++){
    int value;
    std::cin >> value;
    list.push_back(value);
    }

    int swapNumber=0;
    BubbleSort(list,swapNumber);

    print_array(list);
    std::cout << swapNumber << std::endl;

    return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define pi 3.14159265358979323846
#define Endl endl
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
signed main(){
	deque<char> str;
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		str.push_back( s[i] );
	}
	int q;
	cin>>q;
	int hant = 0;
	for(int i=0;i<q;i++){
		int t;
		cin>>t;
		if( t == 1 ){
			hant = 1 - hant;
		}
		if( t == 2 ){
			int f;
			char c;
			cin>>f>>c;
			if( ( f == 1 && hant == 0 ) || ( f == 2 && hant == 1 ) ){
				str.push_front(c);
			}
			if( ( f == 2 && hant == 0 ) || ( f == 1 && hant == 1 ) ){
				str.push_back(c);
			}
		}
	}
	if( hant == 1 ){
		deque<char> str2;
		for(int i=0;i<str.size();i++){
			str2.push_back( str[ str.size() - 1 - i ] );
		}
		str = str2;
	}
	for(int i=0;i<str.size();i++){
		cout<<str[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 988
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
count=0
sm=[0 for i in range(n)]
sm2=[0 for i in range(n)]
for i in range(n):
    for j in range(n):
        if lis[i]>lis[j]:
            if i<j:
                sm2[i]+=1
            else:
                sm[i]+=1
#print(sm)
ans=0
for i in range(n):
    ans=(ans+sm[i]*((k*(k-1))//2))%mod
    ans=ans+sm2[i]*((k*(k+1))//2)%mod
print(ans%mod)


Measured memory_bytes: 9584
// Problem : A - Addition and Subtraction Easy
// Contest : AtCoder - AtCoder Beginner Contest 050
// URL : https://atcoder.jp/contests/abc050/tasks/abc050_a
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

#define spc ' '
#define endl '\n'

using namespace std;


int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int a, b;
	char o;
	cin >> a >> o >> b;
	if(o=='-')cout << a-b;
	else cout << a+b;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                boolean ebishu = true;
                for(int i = 1 ; i <= n ; i++){
                        if(n == Math.floor(i * 1.08)){
                                System.out.println(i);
                                ebishu = false;
                        }
                }
                if(ebishu) System.out.println(":(");
        }
}
//家庭でトラブルがありました、悲しいです

Measured memory_bytes: 35912
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    void solve(Scanner sc, PrintWriter pw) {
        int N = sc.nextInt();
        int[] data = new int[N];
        int totalZero = 0;
        String str = sc.next();
        for (int i = 0; i < str.length(); i++) {
            data[i] = str.charAt(i) == 'W' ? 1 : 0;
            if (data[i] == 0) {
                totalZero++;
            }
        }
        int result = 0;
        for (int i = 0; i < totalZero; i++) {
            if (data[i] == 1) {
                result++;
            }
        }
        pw.println(result);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        new Main().solve(sc, pw);
        pw.flush();
        pw.close();
        sc.close();
    }
}


Measured memory_bytes: 41372
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

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

  int H, W; LL L;
  while(cin>>H>>W>>L,H){
	vector<string> vs(H);
	REP(i,H) cin >> vs[i];
	int sx, sy, sd;
	REP(y,H) REP(x,W)
	  if(vs[y][x] != '.' && vs[y][x] != '#'){
		sx = x, sy = y;
		switch(vs[y][x]){
		case 'N': sd = 0; break;
		case 'E': sd = 1; break;
		case 'S': sd = 2; break;
		case 'W': sd = 3; break;
		}
	  }

	bool vis[100][100][4];
	fill((bool*)vis, (bool*)vis+100*100*4, false);
	int tx = sx, ty = sy, td = sd;
	while(!vis[ty][tx][td]){
	  vis[ty][tx][td] = true;
	  int ttx = tx + dx[td], tty = ty + dy[td];
	  if(ttx < 0 || W <= ttx || tty < 0 || H <= tty || vs[tty][ttx] == '#'){
		td = (td + 1) % 4;
	  }
	  else{
		tx = ttx, ty = tty;
	  }
	}

	int lx = tx, ly = ty, ld = td;
	LL cnt = 0;
	while(vis[ty][tx][td]){
	  vis[ty][tx][td] = false;
	  int ttx = tx + dx[td], tty = ty + dy[td];
	  if(ttx < 0 || W <= ttx || tty < 0 || H <= tty || vs[tty][ttx] == '#'){
		td = (td + 1) % 4;
	  }
	  else{
		tx = ttx, ty = tty, ++cnt;
	  }
	}

	tx = sx, ty = sy, td = sd;
	while(L && (lx != tx || ly != ty || ld != td)){
	  int ttx = tx + dx[td], tty = ty + dy[td];
	  if(ttx < 0 || W <= ttx || tty < 0 || H <= tty || vs[tty][ttx] == '#'){
		td = (td + 1) % 4;
	  }
	  else{
		tx = ttx, ty = tty, --L;
	  }
	}

	if(L > cnt)
	  L %= cnt, L+=cnt;

	while(L){
	  int ttx = tx + dx[td], tty = ty + dy[td];
	  if(ttx < 0 || W <= ttx || tty < 0 || H <= tty || vs[tty][ttx] == '#'){
		td = (td + 1) % 4;
	  }
	  else{
		tx = ttx, ty = tty, --L;
	  }
	}
	char ch;
	switch(td){
	case 0: ch = 'N'; break;
	case 1: ch = 'E'; break;
	case 2: ch = 'S'; break;
	case 3: ch = 'W'; break;
	}
	cout << ty+1 << " " << tx+1 << " " << ch << endl;
  }
  
  return 0;
}

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

// #define int ll
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using si = set<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

#define fastio    ios::sync_with_stdio(0); cin.tie(0)
#define rep(i, n) for (int i = 0; i < n; i++)
#define dotc()    int tcs; if (cin >> tcs) rep(tc, tcs)
#define sz(x)     (int)x.size()
#define eb        emplace_back
#define pb        push_back
#define mp        make_pair
#define all(x)    x.begin(), x.end()
#define rall(x)   x.rbegin(), x.rend()
#define fi        first
#define se        second

int inf(0x3fffffff);
int mod(1000000007);
double pi(acos(-1.0));

ll iv(ll a, ll b) {
  return a > 1 ? b - iv(b % a, a) * b / a : 1;
}

int32_t main() {
  fastio;
#ifdef LOCAL
  freopen("io\\in.txt", "r", stdin);
  freopen("io\\out.txt", "w", stdout);
#endif

  int n, k;
  cin >> n >> k;
  vi a(n);
  rep(i, n) cin >> a[i];
  sort(all(a));

  ll cur = 0, c = 1;
  for (int i = 1; i <= k - 1; i++) {
    c = c * (n - 1 - i + 1) % mod * iv(i, mod) % mod;
  }

  cur += (a.back() - a[0]) * c % mod;

  for (int i = 1; i <= n - k; i++) {
    c = c * (n - k - i + 1) % mod * iv(n - i, mod) % mod;
    cur = (cur + (a[n - i - 1] - a[i]) * c) % mod;
  }
  cout << (cur + mod) % mod;

  return 0;
}


Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();

        if (B % A == 0) {
            System.out.println(A + B);
        } else {
            System.out.println(B - A);
        }
    }

}


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

const int INF = 1e9;
int d,n;
int a[110],e[110],r[110];
int memo[110][110];

int rec(int hp, int exp){
  if(hp==0)return 0;
  if(memo[hp][exp]>=0)return memo[hp][exp];

  int res = INF;
  for(int i=0;i<n;i++){
    if(exp>=r[i]){
      int nhp = max(0,hp-a[i]), nexp = min(100,exp+e[i]);
      if(hp == nhp && exp == nexp)continue;
      res = min(res, rec(nhp, nexp) + 1 );
    }
  }
  return memo[hp][exp] = res;
}

int main(){
  while(cin >> d >> n, d){
    for(int i=0;i<n;i++)cin >> a[i] >> e[i] >> r[i];

    memset(memo,-1,sizeof(memo));
    int ans = rec(d,0);
    if(ans==INF)cout << "NA" << endl;
    else cout << ans << endl;
  }
}

Measured memory_bytes: 1228
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    if N == 1:
        print(1)
        return
    for i in range(0, N):
        if i == 0:
            if A[i + 1] == A[i]:
                B[A[i]] = 2
                continue
        elif i == N - 1:
            if A[i - 1] == A[i]:
                B[A[i]] = 2
                continue
        elif A[i - 1] == A[i] or A[i + 1] == A[i]:
            B[A[i]] = 2
            continue
        B[A[i]] = 1
    # print(*B.items())
    for b in B:
        if B[b] == 0:
            continue
        if B[b] == 2:
            B[b] = 0
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = 0
                # print(b * i)
    res = 0
    for v in B.values():
        if v:
            res += 1
    # print(*B.items())
    print(res)
    return

main()


Measured memory_bytes: 35584
def bisection(fun,start,end):
    prev=0
    while True:
        test=(start+end)/2
        if abs(test-prev)<1e-8:
            return test
        prev=test
        if fun(test)>0:
            start=test
        else:
            end=test
        
    

import math
a,b,x = map(int,input().split())

S = x/a

if x==a*a*b:
    theta=0
else:
    if S<=(a*b/2):
        fun = lambda t: b*b*(math.sin(math.radians(t))*math.cos(math.radians(t))+math.cos(math.radians(t))**3/math.sin(math.radians(t)))/2 - S
    else:
        fun = lambda t: (a*math.cos(math.radians(t))+b*math.sin(math.radians(t)))*b*math.cos(math.radians(t))-(b*b*math.cos(math.radians(t))*math.sin(math.radians(t))+a*a*math.cos(math.radians(t))*math.sin(math.radians(t))+(b*math.cos(math.radians(t))-a*math.sin(math.radians(t)))**2*math.tan(math.radians(t)))/2-S
    theta = bisection(fun,1e-6,90)
print(theta)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;
int H,W,d;

int main(int argc, char *argv[])
{
  scanf("%d%d%d",&H,&W,&d);
  int stride = (W/d+1)*d;
  
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int x,y;
      x = stride+i+j;y = stride+i-j;
      if((x+1)/d%2==1&&(y+1)/d%2==1) printf("R");
      else if((x+1)/d%2==0&&(y+1)/d%2==1) printf("G");
      else if((x+1)/d%2==0&&(y+1)/d%2==0) printf("B");
      else if((x+1)/d%2==1&&(y+1)/d%2==0) printf("Y");
    }
    printf("\n");
  }
  
  return 0;
}


Measured memory_bytes: 512
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
  // "math"
  "sort"
)

// 行単位で読み込む場合
var sc = bufio.NewScanner(os.Stdin)

func main() {
  sc.Scan()
  N, _ := strconv.Atoi((strings.Split(sc.Text(), " "))[0])

  sc.Scan()
  list := []int{}
  for i := 0; i < N; i++ {
    get, _ := strconv.Atoi((strings.Split(sc.Text(), " "))[i])
    list = append(list, get)
  }
  sort.Sort(sort.Reverse(sort.IntSlice(list)))

  alice := 0
  bob := 0

  for i, v := range list {
    if i % 2 == 0 {
      alice += v
    } else {
      bob += v
    }
  }
  
  fmt.Println(alice - bob)
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll mo = 1000000007;
ll mypow(ll a, ll b)
{
  ll res = 1;
  a %= mo;
  while (b)
  {
    if (b & 1)
      res = res * a % mo;
    a = a * a % mo;
    b >>= 1;
  }
  return res;
}
const ll MAX = 510000;
const ll MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (ll i = 2; i < MAX; i++)
  {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
long long COM(ll n, ll k)
{
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
vector<ll> factorial(ll n)
{
  vector<ll> fac;
  fac.push_back(1);
  for (ll i = 1; i < n + 10; i++)
  {
    fac.push_back((fac[i - 1] * i) % mo);
  }
  return fac;
}
int main()
{
/* 
https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5
ボール      箱	      入れ方に制限なし 箱の中身は1つ以下 箱の中身は1つ以上
区別できる   区別できる  1            2             3
区別できない  区別できる  4            5             6
区別できる   区別できない 7            8             9
区別できない  区別できない 10          11            12
*/
ll n , k ;
cin >> n >> k ;
auto mod = [](ll modx) {modx%=mo;modx+=mo;modx%=mo;return modx; };
COMinit();
vector<ll> fac = factorial(100000);

//1
//cout << mypow(k,n) << endl;
//2
//cout << (COM(k,n)*fac[n])%mo << endl;
/* 
//3
ll t=0;
rep(i,k+1){
  t=mod(t+mypow(-1,k-i)*COM(k,i)*mypow(i,n));
}
cout << t << endl;
 */
//4
//cout << COM(n+k-1,n) << endl;
//5
//cout << COM(k,n) << endl;
//6
cout << COM(n-1,k-1) << endl;
return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, p;
    cin >> n >> p;
    vector<int> a(n);
    int odd = 0, even = 0;
    rep(i, 0, n){
        cin >> a[i];
        if(a[i] % 2) odd++;
        else even++;
    }
    int ans = 1;
    rep(i, 0, even) ans *= 2;
    rep(i, 0, odd - 1) ans *= 2;
    if(p == 1 && odd == 0) ans = 0;
    cout << ans << endl;
}

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

#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl

typedef long long ll;

using namespace std;

const int MAX_N = 100000;
const int INF = 1001001001;
int N, K;
int dp[MAX_N+1];

void solve() {

    cin >> N >> K;
    vector<int> H(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> H[i];
    }

    for (int i = 0; i < MAX_N+1; i++) {
        dp[i] = INF;
    }

    dp[0] = 0;
    dp[1] = 0;

    for (int i = 2; i <= N; i++) {
        for (int k = 1; k <= K; k++) {
            if (i-k < 1) {
                break;
            } else {
                dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]));
            }
        }
    }

    print(dp[N]);

}

signed main() {
    solve();
}


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

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


Measured memory_bytes: 3592
// 173

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <iomanip>
#include <climits>
#include <string>
#include <cmath>

using namespace std;
using ll = long long int;
#define NUM 1000000007

int main(){
    int x;
    cin >> x;
    if(x >= 30){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3592
S = input()

if S[0] == S[1] == S[2] == "R":
    print(3)

elif (S[0] == S[1] == "R" and S[2] == "S") or (S[1] == S[2] == "R" and S[0] == "S"):
    print(2)

elif "R" in S:
    print(1)

else:
    print(0)

Measured memory_bytes: 9072
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int main(void){
	int N=0,M=0,work=0;
	cin>>N>>M;
	int A[110];
	for(int i=0;i<N;i++){
		cin>>A[i];
	}
	for(int j=1;j<=M;j++){
		for(int i=0;i<N-1;i++){
			if(A[i]%j>A[i+1]%j){
				work=A[i];
				A[i]=A[i+1];
				A[i+1]=work;
			}
		}
	}
	for(int i=0;i<N;i++){
		cout<<A[i]<<endl;
	}
	return 0;
}
//14:19秒


Measured memory_bytes: 3052
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

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

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

int a, v, b, w, t;

int main() {
  cin >> a >> v >> b >> w >> t;

  if (v <= w) {
    cout << "NO" << endl;
    return 0;
  }

  int tt = (abs(a - b) + (v - w) - 1) / (v - w);
  bool can = tt <= t;
  if (can) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 3616
#include <bits/stdc++.h> 
#define int long long
#define quickie ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rep1(i, a, b) for(int i=a; i<=b; i++)
#define repp(i, a, b) for(int i=b-1; i>=a; i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define db double
#define mi map<int, int>
#define mc map<char, int>
#define ms map<string, int>
#define vi vector<int>
#define qi queue<int>
#define MI(x) power(x, mod-2)
#define test int t; cin >> t;
#define mod 1000000007LL
//#define mod 998244353 
using namespace std;
int power(int x, int y) ;
int gcd(int a, int b) ;

signed main() {
    quickie
    int n ;
    cin >> n ;
    map<string, int> m ;
    int mx = 0 ;
    rep(i, 0, n) {
        string s ;
        cin >> s ;
        m[s]++ ;
        if(m[s] > mx) mx = m[s] ;
    }
    vector<string> v ;
    for(auto it = m.begin(); it!=m.end(); it++) {
        if(it->se == mx) v.pb(it->fi) ;
    }
    sort(v.begin(), v.end()) ;
    rep(i, 0, v.size()) {
        cout << v[i] << endl ;
    }
}
 
int power(int x, int y) {
    int res = 1; x %= mod;
    while (y > 0) {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res%mod;
}
 
int gcd(int a,int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

Measured memory_bytes: 25584
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]=='B' &&  i-1>=0){
            s.erase(i-1,2);
            i-=2;
        }else if(s[i]=='B'){
            s.erase(i,1);
            i-=1;
        }
    }
    cout<<s;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        MyReader reader = new MyReader();
        int n = reader.readInt();
        String s = reader.readString();
        System.out.println(problem052b(n, s));
    }

    private static int problem052b(int n, String s) {
        int x = 0, max = 0;
        for (char c : s.toCharArray()) {
            switch (c) {
                case 'I':
                    x++;
                    break;
                case 'D':
                    x--;
                    break;
                default:
                    // NOP
            }
            max = Math.max(x, max);
        }
        return max;
    }

    private static class MyReader {
        private final BufferedReader br;
        private MyReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        private String readString() throws IOException {
            return br.readLine();
        }

        private int readInt() throws IOException {
            return Integer.parseInt(readString());
        }

        private String[] readStrings(String regex) throws IOException {
            return readString().split(regex);
        }

        private int[] readInts(String regex) throws IOException {
            String[] strings = readStrings(regex);
            int[] ints = new int[strings.length];
            for (int i = 0; i < ints.length; i++) {
                ints[i] = Integer.parseInt(strings[i]);
            }
            return ints;
        }
    }
}

Measured memory_bytes: 25324
//
//  sublime text 3,
//  emre yazicioglu
//

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
#define pb push_back
#define fi first
#define se second
#define INF (ll) (1e18 + 7)
#define MOD (ll) (1e9 + 7)

const int N = 2e6 + 7;
ll mn = INF, mx = -INF;
ll n, m, k, s, q, t;
ll a, b, c, d, e;
ll ans, cur, sum, cnt;
ll ar[N], p[N], dp[N];
string str; bool h[N];
pll pp[N]; vll v;

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

  // freopen("../in.txt","r",stdin);
  // freopen("../out.txt","w",stdout);

  cin >> n >> str;
  for(int i = 1; i < n; i++)
    if(str[i] != str[i - 1])
      ans++;
  cout << ans + 1;
}

Measured memory_bytes: 2560
import sys

input = sys.stdin.buffer.readline

n = int(input())
# n+1個
A = list(map(int, input().split()))

if n == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
if A[0] > 0:
    print(-1)
    exit()

ans = 0
max2 = 0
kouho = [0] * (n + 1)
for i in range(n, 0, -1):
    max1 = pow(2, i)
    max2 += A[i]
    max2 = min(max1, max2)
    kouho[i] = max2
kouho[0] = 1
not_leave = 1
for i in range(1, n + 1):
    cnt = 0
    not_leave *= 2
    temp = min(kouho[i], not_leave)
    ans += temp
    not_leave -= A[i]
    if not_leave <= 0 and i != n:
        print(-1)
        exit()
    if i == n:
        if not_leave == 0:
            continue
        elif not_leave < 0:
            print(-1)
            exit()
ans += 1
print(ans)


Measured memory_bytes: 84388
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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 (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    string X;
    cin >> X;
    int sNum = 0;
    int matchNum = 0;
    for (const char c : X)
    {
        if (c == 'S')
        {
            ++sNum;
        }
        else if (sNum > 0)
        {
            --sNum;
            ++matchNum;
        }
    }
    cout << X.length() - matchNum * 2 << endl;
}


Measured memory_bytes: 720
# abc109_b

from collections import Counter


def solve(words):
    commons = Counter(words).most_common()
    if commons[0][1] > 1:
        return "No"
    else:
        # initial letter first word not important
        first_letters = list(map(lambda x: x[0], words[1:]))
        # final letter final word not important
        last_letters = list(map(lambda x: x[-1], words[:-1]))
        if first_letters == last_letters:
            return "Yes"
        else:
            return "No"


if __name__ == "__main__":
    N = int(input(""))
    words = [input("") for i in range(N)]
    print(solve(words))


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

int main() {
    int k;
    vector<int> a={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cin >> k;
    cout << a.at(k-1);
    
}

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

if n >= m:
    print(0)
    exit()

al_s = sorted(al)
res=[]
for i in range(m-1):
    res.append(al_s[i+1]-al_s[i])

res_s = sorted(res)

print(sum(res)-sum(res_s[m-n:]))

Measured memory_bytes: 20500
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//clock_t start=clock();clock_t end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef pair<pii,pii> P;
typedef tuple<ll,ll,ll> tl;
typedef pair<double,double> pdd;
typedef vector<vector<ll>> mat;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll mod5=1000000009;
ll inf=1LL<<62;
double pi=3.141592653589793238462643383279L;
double eps=1e-14;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
#define mrep(itr,mp) for(auto& itr:mp)
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umh unordered_map<ll,ll,custom_hash>
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll c=gcd(a,b);
    return a*b/c;
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
    now%=md;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll popcount(ll n){
    ll ret=0;
    ll u=n;
    while(u>0){
        ret+=u%2;
        u/=2;
        
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    ll kai[100010];
    ll ata[100010];
    ll sum[100010];
    ll x[n];
    rep(i,0,n)cin>>x[i];
    kai[0]=1;
    rep(i,1,100010)kai[i]=kai[i-1]*i%mod;
    sum[0]=0;
    rep(i,1,n){
        ata[i]=kai[n-1]*gyaku(i,mod)%mod;
        sum[i]=(sum[i-1]+ata[i])%mod;
        //cout<<sum[i]<<endl;
    }
    ll ans=0;
    rep(i,1,n){
        ll sa=x[i]-x[i-1];
        (ans+=sa*sum[i])%=mod;
    }
    cout<<ans<<endl;
}


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

int a[510000];
int h;
void maxheapify(int i) {
	int l = 2 * i, r = 2 * i + 1;
	int lar;
	if (l <= h && a[i] < a[l])lar = l;
	else lar = i;
	if (r <= h&& a[lar] < a[r])lar = r;

	if (lar != i) {
		swap(a[i], a[lar]);
		maxheapify(lar);
	}
}
void buildHeap(){
	for (int i = h / 2; i > 0; i--) maxheapify(i);
}

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

	cin >> h;
	for (int i = 1; i <= h; i++) {
		cin >> a[i];
	}
	buildHeap();
	for (int i = 1; i <= h; i++) {
		cout << " " << a[i];
	}
	cout << endl;
}


Measured memory_bytes: 5124
while 1:
    n = int(input())
    if n == 0:
        break
    x = {}
    for i in range(n):
        p,d1,d2 = map(int,input().split())
        v = d1 + d2
        x[p] = v
    x = sorted(x.items(), key=lambda x:x[1])
    print(f'{x[n-1][0]} {x[n-1][1]}')


Measured memory_bytes: 7396
n=int(input())
s=input()
l=int(len(s))
m=0
if l%2==0:
  a=s[0:l//2]
  b=s[l//2:l]
  for i in range(n//2):
    if a[i]!=b[i]:
      m+=1
  if m==0:
        print("Yes")
  else:
        print("No")
else:
  print("No")

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

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define sz(s) (int)s.size()

vector<int> solve(vector<int> a) {
	int n = a.size();
	vector<int> b = a;
	sort(b.begin(), b.end());
	multiset<int> lef, rig;
	// keep sl <= sr
	int m = n / 2;
	rep(i, 0, m) lef.insert(b[i]);
	rep(i, m, n) rig.insert(b[i]);
	while (sz(lef) < sz(rig) - 1) {lef.insert(*rig.begin()); rig.erase(rig.begin());}
	while (sz(lef) > sz(rig)) {rig.insert(*lef.rbegin()); lef.erase(--lef.end());}

	vector<int> ans;
	rep(i, 0, n) {
		int v = a[i];
		if (lef.find(v) != lef.end()) {lef.erase(lef.find(v));}
		else rig.erase(rig.find(v));
		// balance
		while (sz(lef) < sz(rig) - 1) {lef.insert(*rig.begin()); rig.erase(rig.begin());}
		while (sz(lef) > sz(rig)) {rig.insert(*lef.rbegin()); lef.erase(--lef.end());}

		// cout << *rig.begin() << '\n';
		// cerr << lef.size() << ' ' << rig.size() << endl;
		// cout << "l: ";
		// for (auto v : lef) cout << v << ' ';
		// cout << "\nr: ";
		// for (auto v : rig) cout << v << ' ';
		// cout << '\n';
		ans.push_back(*rig.begin());
		if (*rig.begin() <= v) rig.insert(v);
		else lef.insert(v);
		// balace
		while (sz(lef) < sz(rig) - 1) {lef.insert(*rig.begin()); rig.erase(rig.begin());}
		while (sz(lef) > sz(rig)) {rig.insert(*lef.rbegin()); lef.erase(--lef.end());}
	}
	return ans;
}

vector<int> brute(vector<int> a) {
	int n = a.size();
	vector<int> ans;
	rep(i, 0, n) {
		vector<int> b;
		rep(j, 0, n) if (i != j) b.push_back(a[j]);
		sort(b.begin(), b.end());
		ans.push_back(b[(n - 1) / 2]);
	}
	return ans;
}

void stress() {
	srand(42);
	rep(turn, 0, 100) {
		int n = 1 + rand() % 10;
		vector<int> a(n);
		rep(i, 0, n) a[i] = 1 + rand() % 1000;
		vector<int> expect = brute(a);
		vector<int> result = solve(a);
		if (expect != result) {
			cerr << "failed\n";
			cout << n << '\n';
			rep(i, 0, n) cout << a[i] << ' ';
			cout << '\n';
			rep(i, 0, n) cout << expect[i] << ' '; 
			cout << '\n';
			rep(i, 0, n) cout << result[i] << ' ';
			cout << '\n';
			return;
		}
	}
	cerr << "passed all\n";
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &v : a) cin >> v;
	vector<int> ans = solve(a);
	for (auto v : ans) cout << v << '\n';
	// stress();
}

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

int main(){
  int n,m;cin>>n>>m;
  vector<int> p(m),y(m);
  vector<vector<int>> x(n,vector<int>(0,0));
  REP(i,m){
    int pp,yy;cin>>pp>>yy;
    p.at(i)=pp;y.at(i)=yy;
    x.at(pp-1).push_back(yy);
  }
  REP(i,n) sort(x.at(i).begin(),x.at(i).end());
  REP(i,m){
    ll ans=ll(p.at(i))*1000000;
    ans+=+int(lower_bound(x.at(p.at(i)-1).begin(),x.at(p.at(i)-1).end(),y.at(i))-x.at(p.at(i)-1).begin()+1);
    cout<<setfill('0')<<right<<setw(12)<<ans<<endl;
  }
}


Measured memory_bytes: 7808
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
CD = [tuple(map(int, input().split())) for _ in range(N)]

AB.sort(key = max, reverse = True)
CD.sort(key = min)

counter = 0
for a, b in AB:
    for c, d in CD:
        if a < c and b < d:
            CD.remove( (c, d) )
            counter += 1
            break

print(counter)


Measured memory_bytes: 39024
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rrep(i,n,a) for(int i=n;i>=a;i--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define pcnt(n) __builtin_popcount(n)
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;


signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    int ans = 0;
    rep(i,k,n+2){
        ans+=((2*n-i+1)*i/2-(i-1)*i/2+1)%MOD;
        ans%=MOD;
    }
    cout<<ans%MOD<<endl;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll>mp;
ll a,b,c,d;
ll dfs(ll n)
{
	if(n==0)return 0;
	if(n==1)return d;
	if(mp.find(n)!=mp.end())return mp[n];
	ll res=1e18;
	if(1e18/n>=d){res=n*d;}
	res=min(dfs(n/2)+a+n%2*d,res);
	res=min(dfs(n/3)+b+n%3*d,res);
	res=min(dfs(n/5)+c+n%5*d,res);
	if(n!=2)res=min(dfs(n/2+1)+a+2*d-n%2*d,res);
	res=min(dfs(n/3+1)+b+3*d-n%3*d,res);
	res=min(dfs(n/5+1)+c+5*d-n%5*d,res);
	return mp[n]=res;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		ll n;
		mp.clear();
		cin>>n>>a>>b>>c>>d;
		cout<<dfs(n)<<"\n";
	}
	return 0;
}

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

vector<int> G[100010];
bool used[100010];
int par[100010];
int dep[100010];
int low[100010];

void dfs(int v,int p,int d){
    used[v] = true;
    par[v] = p;
    dep[v] = d;
    low[v] = d;
    for(int i = 0 ; i < G[v].size() ; i ++){
        if(G[v][i] == p)continue;
        if(used[G[v][i]]){
            low[v] = min ( low[v] , dep[G[v][i]] );
        }
        else {
            dfs(G[v][i],v,d+1);
            low[v] = min ( low[v] , low[G[v][i]] );
        }
    }
}

int main(){
    int V,E;
    int s[100010],t[100010];
    scanf("%d%d",&V,&E);
    for(int i = 0 ; i < E ; i ++){
        scanf("%d%d",&s[i],&t[i]);
        G[s[i]].push_back(t[i]);
        G[t[i]].push_back(s[i]);
        if(s[i] > t[i])swap(s[i],t[i]);
    }
    for(int i = 0 ; i < 100010 ; i ++){
        used[i] = false;
    }
    dfs(0,-1,0);
    
    vector<pair<int,int>> ans;
    for(int i = 0 ; i < E ; i ++){
        if(par[s[i]] == t[i]){
            if(low[s[i]] > dep[t[i]])ans.push_back(pair<int,int>(s[i],t[i]));
        }
        else if(par[t[i]] == s[i]){
            if(low[t[i]] > dep[s[i]])ans.push_back(pair<int,int>(s[i],t[i]));
        }
    }
    sort(ans.begin(),ans.end());
    for(int i = 0 ; i < ans.size() ; i ++){
        printf("%d %d%c",ans[i].first,ans[i].second,10);
    }
}

Measured memory_bytes: 7504
<?php
/**
 * Created by PhpStorm.
 * User: okawa.t.af
 * Date: 2019-02-22
 * Time: 17:34
 */
$N = fgets(STDIN);
$L = explode(" ",fgets(STDIN));
$intL = [];
foreach($L as $l){
    array_push($intL,(int)$l);
}
$MAXintL = max($intL);
$sumintL = array_sum($intL);
if(2*$MAXintL >= $sumintL){
    echo "No";
}else{
    echo "Yes";
}

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

using namespace std;



int mod(int a, int b){
  if(a>b)
    return a-b;
  return b-a;
}

int maximum(int a, int b)
{
  if(a>b)
    return a;
  return b;
}

int main(){
    int n;
    cin >> n;
    double ph[n];
    for(int i=0;i<n;i++)
        cin >> ph[i];
    double dp[n+1][n+1];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dp[i][j]=0;
    dp[0][0]=1.0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(j==0){
                dp[i][j] = (1-ph[i-1])*dp[i-1][j];
            }
            else {
                dp[i][j] = ph[i-1]*dp[i-1][j-1]+(1-ph[i-1])*dp[i-1][j];
            }
        }
    }
    double ans=0;
    for(int i=1+n/2;i<=n;i++){
        ans+=dp[n][i];
    }
    printf("%.9lf\n",ans);
    return 0;
}

Measured memory_bytes: 74112
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353

print(a_list[n] % 998244353)



Measured memory_bytes: 24800