akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

ll h, w, a, b;
ll ans = 0;

ll fact[1001000];

ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	ll res = mod_pow(x*x%MOD, n / 2);
	if (n & 1)res = res*x%MOD;
	return res;
}

ll nCk(ll n, ll k) {
	return fact[n] * mod_pow(fact[k], MOD - 2) % MOD*mod_pow(fact[n - k], MOD - 2) % MOD;
}

int main() {
	fact[0] = 1;
	rep(i, 1001000 - 1) {
		fact[i + 1] = fact[i] * (i + 1) % MOD;
	}
	cin >> h >> w >> a >> b;
	rep(i, h - a) {
		ll num = nCk(b - 1 + i, i);
		num %= MOD;
		num *= nCk(h - 1 - i + w - b - 1, w - b - 1);
		num %= MOD;
		ans += num;
		ans %= MOD;
	}
	cout << ans << endl;
}

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

int main() {
string s;
cin>>s;
if(s=="ABC")cout<<"ARC";
if (s=="ARC")cout<<"ABC";

}


Measured memory_bytes: 3588
c[];main(n,m,i,j,k){for(;scanf("%d%d",&n,&m)*n;printf("%d\n",j>m?i:j)){for(i=3;i--;)for(scanf("%d",&j);j--;c[n-k]=i)scanf("%d",&k);for(i=n;i--;k+=c[i])j-=pow(3,i)*abs(k*2%4-c[i]);j=fmin(~j,pow(3,n)+j);}}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    cin >> N;
    vector<int>A(N);
    vector<int>cnt(N+1);
    int ans = 0;
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        ans+=A[i];
        cnt[i+1]+=A[i];
    }
    int res = ans;
    for(int i = 0; i < N; i++) {
        cnt[i+1]+=cnt[i];
        ans = min(ans,abs(cnt[i+1]*2-res));
    }
    cout << ans << endl;
}


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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  string s;
  cin >> s;
  ll ans = 15 - s.length();
  REP(i,s.length()){
    if(s[i]=='o') ans++;
  }
  if(ans>=8) cout << "YES" << endl;
  else cout << "NO"<< endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mk make_pair
#define mod 1000000007
int main(){
    ll n;
    cin>>n;
    vector<int> arr(n);
    ll sum=0;
    for(ll i=0;i<n;i++){
        cin>>arr[i];
        
    }
    ll ans=0;
    for(ll i=n-1;i>=0;i--){
        ans=(ans+arr[i]*(sum))%mod;
        sum=(sum+arr[i])%mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3924
($H,$W)=glob<>;
@s=map[/./g],<>;
$g=grep$_ eq'.',map@$_,@s;
$s[0][0]=1;
@q=(0,0);
while(@q){
	$Y=shift@q;
	$X=shift@q;
	for([$Y-1,$X],[$Y,$X-1],[$Y,$X+1],[$Y+1,$X]){
		($y,$x)=@$_;
		if(0<=$y&&$y<$H&&0<=$x&&$x<$W){
			if($s[$y][$x]=~s/\./$s[$Y][$X]+1/e){
				push@q,$y,$x
			}
		}
	}
}
print-($s[$H-1][$W-1]eq'.')||$g-$s[$H-1][$W-1]


Measured memory_bytes: 1280
from math import ceil

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

bottom_n_list = [(0, 0) for _ in range(n + 1)]
bottom_n_list[n] = (a[n], a[n])
for i in range(n-1, -1, -1):
    leaf_num = a[i]
    min_a_node_num = ceil(bottom_n_list[i + 1][0] / 2)
    max_a_node_num = min(bottom_n_list[i + 1][1], 2 ** i - leaf_num)
    if max_a_node_num < min_a_node_num:
        print(-1)
        exit()
    bottom_n_list[i] = (min_a_node_num + leaf_num, max_a_node_num + leaf_num)

top_n_list = [0]*(n+1)
if 1 < bottom_n_list[0][0] or bottom_n_list[0][1] < 1:
    print(-1)
    exit()
top_n_list[0] = 1
ans = 1
for i in range(1, n+1):
    top_n_list[i] = min(bottom_n_list[i][1], (top_n_list[i-1]-a[i-1])*2)
    ans += top_n_list[i]

print(ans)

Measured memory_bytes: 85532
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <sstream>
#include <cmath>
#include <climits>
#include <set>
#include <iostream>
#include <map>
#include <functional>
#include <cstdlib>
#include <numeric>
#include <queue>
#include <complex>
#include <sstream>
#include <stack>

using namespace std;

#define reep(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reep(i,0,n)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef complex<double> Point;

int main()
{
	char line[128];
	stack<double> st;
	while(fgets(line, 128, stdin)){
		istringstream sin(line);
		char str[128];
		while(sin >> str){
			if((strlen(str) > 1 && str[0] == '-') || isdigit(str[0])){
				st.push(atof(str));
			}else{
				double b = st.top();
				st.pop();
				double a = st.top();
				st.pop();
				if(str[0] == '+')
					st.push(a+b);
				else if(str[0] == '-')
					st.push(a-b);
				else if(str[0] == '*')
					st.push(a*b);
				else if(str[0] == '/')
					st.push(a/b);
			}
		}
		printf("%lf\n", st.top());
	}
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  int a[200000];
  int count = 1;
  int brokenBlocks = 0;
  for(int i=0; i!=n; i++){
    cin >> a[i];
    if(a[i] == count){
      count += 1;
    }else{
      brokenBlocks += 1;
    }
  }
  if(count == 1){
    cout << -1;
  }else{
    cout << brokenBlocks << '\n';
  }
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define eps (1e-5)

using namespace std;
const int N=100000+10;
il LL rd()
{
    re LL x=0,w=1;re char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
char cc[N];
int n,cnt;

int main()
{
  scanf("%s",cc+1);
  n=strlen(cc+1);
  for(int i=2;i<n;i++) cnt+=(cc[i-1]!=cc[i+1]);
  if(!cnt) puts("Second");
  else ((n-(cc[1]==cc[n]))&1)?puts("First"):puts("Second");
  return 0;
}


Measured memory_bytes: 384
N = int(input())
H = list(map(int, input().split()))

dp_list = [10**4+1]*len(H)

## DPに基づいて、各位置に行くまでの最小コストを計算する
dp_list[0]=0
dp_list[1]=abs(H[0]-H[1])
for idx,h in enumerate(H[2:],2):
  
  ## 1個前から行く場合のコスト
  cost_1 = abs(H[idx] - H[idx-1]) + dp_list[idx-1]
  
  ## 2個前から行く場合のコスト
  cost_2 = abs(H[idx] - H[idx-2]) + dp_list[idx-2]

  ## 最小コストを計算
  dp_list[idx] = min(cost_1, cost_2)


ans = dp_list[-1]
print(ans)

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

const int maxN = 410;

char str[maxN][maxN];

int main (){
	int h, w, i, j;
	scanf("%d%d", &h, &w);
	for(i = 1; i <= h; ++i) scanf("%s", str[i] + 1);
	for(i = 1; i <= h + h; ++i){
		for(j = 1; j <= w; ++j)
			printf("%c", str[(i + 1) / 2][j]);
		puts("");
	}
	return 0;
}


Measured memory_bytes: 3728
#include<iostream>
using namespace std;
int main()
{
    int n,k,ans=0;cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        if(x<=k/2) ans+=x*2;
        else ans+=(k-x)*2;
    }
    cout<<ans<<'\n';
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long double prob[n];
    for(int i=0;i<n;i++) cin>>prob[i];
    vector<vector<long double>> dp(n+1,vector<long double>(n+1,0));
    // i head and j tail
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n-i;j++)
        {
            if(i==0 && j==0) dp[i][j]=1;
            else if(i==0)
            {
                dp[i][j]=dp[i][j-1]*(1-prob[j-1]);
            }
            else if(j==0)
            {
                dp[i][j]=dp[i-1][j]*prob[i-1];
            }
            else
            {
                dp[i][j]=dp[i-1][j]*prob[j+i-1]+dp[i][j-1]*(1-prob[i+j-1]);
            }
        }
    }
    long double ans=0;
    for(int i=n/2+1;i<=n;i++)
    {
        ans+=dp[i][n-i];
    }
    cout<<setprecision(10)<<ans<<endl;
    return 0;
}

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

// n回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii;  // 2次元配列
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> PII;

template<typename T>
using vec = vector<T>;
template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

const ld Pi = std::acos(-1.0L);
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    // cout << fixed << setprecision(15);

    ll n,h; cin >> n >> h;
    vll a(n), b(n); rep(i,n) cin >> a[i] >> b[i];

    sort(b.rbegin(), b.rend());
    sort(a.rbegin(), a.rend());
    /**
     * bをどれだけ投げるかを全探索
     */
    vll csum(n+1); rep(i,n) csum[i+1] += csum[i] + b[i];

    ll ans = infll, times;
    for(int i = 0; i < n; ++i) {
        times = i + 1;
        ll H = h - (csum[i+1] - csum[0]);
//        debug(H);
        if(H > 0) times += (H+a[0]-1)/a[0];
//        debug(times);
        chmin(ans, times);
    }

    cout << ans << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 2560
H,W = map(int,input().split())
grid = []
for h in range(H):
    a = input()
    if '#' in a: #行がすべて白の行ははじめから除く
        grid.append(a)

white = set() #圧縮する列の数字を格納
for w in range(W):
    if all(l[w] == '.' for l in grid): #グリッドの列ごとに走査
        white.add(w)

for l in grid:
    print("".join(l[w] for w in range(W) if w not in white)) 

Measured memory_bytes: 39536
const main = arg => {
    let input = arg.trim();

    const a = BigInt(input.split(' ')[0]);
    const b = BigInt(input.split(' ')[1].replace('.', ''));
    let ret = a * b / BigInt(100)
    
    console.log(String(ret).replace('n', ''));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

Measured memory_bytes: 29628
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
{
    static void Main(string[] args)
    {
		int N = int.Parse(Console.ReadLine());
		int[] A = new int[N];
		string[] input = Console.ReadLine().Split(' ');
        for(int i = 0; i < N; i++)
		{
			A[i] = int.Parse(input[i]);
		}

		List<int> x = new List<int>();
		List<int> y = new List<int>();
		List<Tuple<int,int>> ans = new List<Tuple<int,int>>();
        for(int i = 0; i < N; i++)
		{
			if (A[i] >= 0)
			{
				x.Add(A[i]);
			}else { y.Add(A[i]); }
		}
		
		x.Sort();
		x.Reverse();
		y.Sort();
		int X;
		int Y;

		if (y.Count == 0)
		{
			int c = x.Count - 1;
			Y= x[c];
			x.RemoveAt(c);
			X = x[0];
			x.RemoveAt(0);

			while (x.Count > 0)
			{



				ans.Add(new Tuple<int, int>(Y, x[0]));
				Y = Y - x[0];
				x.RemoveAt(0);
			}
			int final = X - Y;
			ans.Add(new Tuple<int, int>(X, Y));

			Console.WriteLine(final);
			for (int i = 0; i < ans.Count; i++)
			{
				Console.WriteLine("{0}" + " " + "{1}", ans[i].Item1, ans[i].Item2);
			}
		}
		else if (x.Count == 0)
		{
			int d = y.Count - 1;
			 X = y[d];
			y.RemoveAt(d);
			while (y.Count > 0)
			{
				ans.Add(new Tuple<int, int>(X, y[0]));
				X = X - y[0];
				y.RemoveAt(0);

			}
			int final = X;
			

			Console.WriteLine(final);
			for (int i = 0; i < ans.Count; i++)
			{
				Console.WriteLine("{0}" + " " + "{1}", ans[i].Item1, ans[i].Item2);
			}
		}
		else
		{

			X = x[0];
			Y = y[0];
			x.RemoveAt(0);
			y.RemoveAt(0);



			while (y.Count > 0)
			{
				int c = y.Count - 1;

				ans.Add(new Tuple<int, int>(X, y[c]));
				X = X - y[c];
				y.RemoveAt(c);

			}
			while (x.Count > 0)
			{
				int d = x.Count - 1;

				ans.Add(new Tuple<int, int>(Y, x[d]));
				Y = Y - x[d];
				x.RemoveAt(d);
			}

			int final = X - Y;
			ans.Add(new Tuple<int, int>(X, Y));

			Console.WriteLine(final);
			for (int i = 0; i < ans.Count; i++)
			{
				Console.WriteLine("{0}" + " " + "{1}", ans[i].Item1, ans[i].Item2);
			}
		}
	}
}




Measured memory_bytes: 31044
use std::cmp::{max, min};

fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: i64 = read(&mut stdin_lock, &mut buf, b' ');
    let m: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut lrv = vec![(0i64, 0i64); m];
    for i in 0..m {
        lrv[i].0 = read(&mut stdin_lock, &mut buf, b' ');
        lrv[i].1 = read(&mut stdin_lock, &mut buf, b'\n');
    }

    let mut l: i64 = 1;
    let mut r: i64 = n;
    for i in 0..m {
        l = max(l, lrv[i].0);
        r = min(r, lrv[i].1);
    }
    let ans = max(0, r - l + 1);
    println!("{}", ans);
}


Measured memory_bytes: 6396
#include <iostream>

int main() {
    std::string s;
    std::cin >> s;

    int num = 0;

    for (auto it = s.rbegin(); it != s.rend(); ++it)
        num += ((int)*it - 48);

    std::cout << ((num % 9 == 0) ? "Yes" : "No");
}

Measured memory_bytes: 3676
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//ll MOD=1000000007LL;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;
//const ll MAX_V=114514LL;
//const ll MAX = 500010LL;
const ll mod=MOD;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={0,0,1,-1};
vl dy={1,-1,0,0};

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

// テーブルを作る前処理
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;
}

ll modpow(ll a, ll n, ll mod) {
  
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll N=2000010;
vl arr(N);
void Eratosthenes(){
	for(ll i = 0; i < N; i++){
		arr[i] = 1;
	}
        arr[1]=0;
	for(ll i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(ll j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}
}
//素数判定O(√n)
bool is_prime(ll n){
  for(ll i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return n!=1;
}


int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(10);
  /*--------------------------------*/
  ll q;cin>>q;
  vl l(q),r(q);
  rep(i,q)cin>>l[i]>>r[i];
  vl vec(100001,1);
  rep(i,100001){
    if(i%2==0)vec[i]=0;
  }
  rep(i,100001){
    if(vec[i]==0)continue;
    if(is_prime(i)&&is_prime((i+1)/2))vec[i]=1;
    else vec[i]=0;
  }
  vl sum(100001);
  sum[0]=0;
  rep(i,100000){
    sum[i+1]=sum[i]+vec[i+1];
  }
  rep(i,100001){
    //cout<<vec[i]<<" ";
  }
  rep(i,q){
    cout<<sum[r[i]]-sum[l[i]-1]<<endl;
  }
}

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


#define ALL(a) 		(a.begin() , a.end())
#define ll 			long long int
#define ff          first
#define ss          second
#define pb          push_back
#define ar 			array
#define mp 			make_pair
#define f(i,a,b)   	for(ll i =a;i<=b;i++)
#define inf 		INT_MAX
#define pll 		pair<ll,ll>
#define mat 		vector<vector<ll>>

const ll INF = 1e18;
void init(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE 
		freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
}
 
bool checkp2(ll n){
	return n && !(n & (n-1));
}

ll numsetbit(ll n){
	ll count = 0;
	for(;n;count++){
		n = n & (n-1);
	}
	return count;
}
 
ll power(ll x , ll n , ll mod){
    x = x % mod;
	ll po = 1;
	while(n){
		if(n & 1){
			po = (po*x) % mod;
		}
		n = n>>1;
		x = ((x % mod) * (x % mod)) % mod;
	}
	return po;
}
 
bool isPrime(ll x){
	if(x < 2)
		return 0;
	for(ll y = 2; y * y <= x; y++){
		if(x % y == 0){
			return 0;
		}
	}
	return true;
}
const ll mxn = 1e3;
ll H , W ,c1,c2,d1,d2;
string s[mxn];
vector<vector<ll>> d;
ll vis[mxn + 10][mxn+10];

bool e(ll i , ll j){
	return i >= 0 && i < H && j >= 0 && j < W && s[i][j] == '.';
}


void solve(){

		d= vector<vector<ll>> (mxn+10 , vector<ll>(mxn+10 , 3e9));
		cin>>H>>W;
		cin>>c1>>c2>>d1>>d2;
		--c1,--c2,--d1,--d2;

		for(ll i = 0;i<H;i++){
			cin>>s[i];
		}

		priority_queue<ar<ll,3> , vector<ar<ll,3>> , greater<ar<ll,3>> > pq;

		pq.push({0 , c1 , c2});		// move , starting , ending
		d[c1][c2] = 0;

		while(!pq.empty()){

			ar<ll,3> cur = pq.top();
			pq.pop();

			ll i = cur[1] , j = cur[2] , d1= cur[0];

			if(e(i-1 , j)){

					if(d[i-1][j] > d[i][j]){
							d[i-1][j] = d[i][j];
							pq.push({d[i-1][j] , i-1 , j});
					}


			}
			if(e(i+1 , j)){

					if(d[i+1][j] > d[i][j]){
							d[i+1][j] = d[i][j];
							pq.push({d[i+1][j] , i+1 , j});
					}


			}
			if(e(i , j-1)){
					if(d[i][j-1] > d[i][j]){
							d[i][j-1] = d[i][j];
							pq.push({d[i][j-1] , i , j-1});
					}
			}
			if(e(i , j+1)){
					if(d[i][j+1] > d[i][j]){
							d[i][j+1] = d[i][j];
							pq.push({d[i][j+1] , i , j+1});
					}
			}

			for(ll i1 = i-2;i1<=i+2;i1++){
				for(ll j1 = j-2;j1<=j+2;j1++){

						if(e(i1 , j1)){
							//cout<<"kdnv";
								if(d[i1][j1] > d[i][j] + 1){
									d[i1][j1] = d[i][j] + 1;
									pq.push({d[i1][j1] , i1 , j1});
								}
						}

				}
			}
		}

		
		
		if(d[d1][d2] >= 2e9 + 100){
			cout<<"-1\n";
		}
		else{
			cout<<d[d1][d2]<<endl;
			return;
		}



}

int main(){
	
	init();
	ll t = 1;
	//cin>>t;
	for(ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}

Measured memory_bytes: 12844
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if(n % 1000 == 0){
		System.out.println("0");
		return;
		}
		System.out.println(1000 - (n % 1000));
    }
}

Measured memory_bytes: 35660
def solve(string):
    s, q, *qs = string.split("\n")
    pre = []
    post = []
    preapp = lambda x:pre.append(x)
    postapp = lambda x:post.append(x)
    r = False
    for _q in qs[::-1]:
        if _q == "1":
            r = not r
            continue
        _, f, c = _q.split()
        if r and f == "2" or not r and f == "1":
            preapp(c)
        else:
            postapp(c)
    pre, post = "".join(pre), "".join(post[::-1])
    return pre + s[::-1] + post if r else pre + s + post

if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Measured memory_bytes: 20360
X, N = map(int, input().split())
p = list(map(int, input().split()))

mn = 999
ans = 0

for i in range(0, 102):
    a = abs(X-i)
    if i not in p:
        if a < mn:
            mn = a
            ans = i

    if a > mn:
        break

print(ans)

Measured memory_bytes: 9148
#include<bits/stdc++.h>
using namespace std;
int ans[200009];
int main()
{
    int a,i,n;
    cin >> n;
    for(i=2;i<=n;i++)
    {
        cin >> a;
        ans[a]++;
    }
    for(i=1;i<=n;i++) cout << ans[i] << endl;


}


Measured memory_bytes: 4332
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

// ABC044 C - 高橋くんとカード
// 2020.06.16
// dp[i][j][k] := i番目までのカードを見たときに、j枚選んで、合計kとなる組み合わせ

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, A; cin >> N >> A;
  vector<ll> X(N);
  ll sumX = 0;
  REPLL(i, N){
    cin >> X[i];
    sumX += X[i];
  }
  vector<vector<vector<ll> > > dp(N+5, vector<vector<ll> >(N+5, vector<ll>(N*A+5, 0)));
  dp[0][0][0] = 1;
  for(ll i = 0; i < N; i++){
    for(ll j = 0; j <= N; j++){
      for(ll k = 0; k <= N*A; k++){
        dp[i+1][j][k] += dp[i][j][k];
        if(k+X[i] <= N*A) dp[i+1][j+1][k+X[i]] += dp[i][j][k];
      }
    }
  }
  ll ans = 0;
  for(ll i = 1; i <= N; i++){
    ans += dp[N][i][i*A];
  }
  cout << ans << endl;
}

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

#define MAX_C_NUM 1000
#define MAX_K_NUM 3000

long long a[MAX_C_NUM], b[MAX_C_NUM], c[MAX_C_NUM];
long long ab[MAX_C_NUM * MAX_C_NUM];
long long abc[MAX_K_NUM * MAX_C_NUM];
vector<long long> vec;

int main() {
  int X, Y, Z, K;
  
  cin >> X >> Y >> Z >> K;
 
  for(int i=0; i<X; i++) cin >> a[i]; sort(a, a + X, greater<long long>());
  for(int i=0; i<Y; i++) cin >> b[i]; sort(b, b + Y, greater<long long>());
  for(int i=0; i<Z; i++) cin >> c[i]; sort(c, c + Z, greater<long long>());

  //解法その２
  //上からソートして，i_a * i_b * i_c > K の場合，上位K番目に入ることはない
  
  for(int i=0; i<X; i++) {
    for(int j=0; j<Y; j++) {
      for(int k=0; k<Z; k++) {
	if((i+1) * (j+1) * (k+1) <= K) {
	  vec.push_back(a[i] + b[j] + c[k]);
	} else {
	  break;
	}
      }
    }
  }

  sort(vec.begin(), vec.end(), greater<long long>());
  for(int i=0; i<K; i++) {
    cout << vec[i] << endl;
  }  

  return 0;
}


  
  
  


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define MAX std::numeric_limits<lld>::max();
#define MIN std::numeric_limits<lld>::min();
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main (){
    FastIO
    lld n, i;
    cin >> n;
    lld A[n+0];
    lld C[n+1];
	for(i = 0; i<n+1; i+= 1){
		C[i] = 0;
	}
	for(i = 0; i < n; i+= 1){
		cin >>  A[i];
		C[A[i]] += 1;
	}
    lld s = 0;
    for(i = 1; i <=n; i+= 1){
    	s+=(C[i]*(C[i]-1))/2;
    }
    for(i = 1; i <=n; i+= 1){ 	
   		s -= (C[A[i-1]]*(C[A[i-1]]-1))/2;
    	s += ((C[A[i-1]]-1)*(C[A[i-1]]-2))/2;
    	cout << s << "\n";
    	s -= ((C[A[i-1]]-1)*(C[A[i-1]]-2))/2;
    	s += (C[A[i-1]]*(C[A[i-1]]-1))/2;
    }
    return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstdlib>

using namespace std;

int main()
{
  int A, B;
  cin >> A >> B;

  int tap = 0;
  int i;
  for(i=1; i<1000000; i++)
    {
     tap += A;
     if(tap>=B)
       break;
     tap -= 1;
    }
  if(B==1)
    i=0;
  cout << i << endl;
  

  return 0;
}



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

long long gcd(long long n, long long m) { return m ? gcd(m, n % m) : n; }

long long lcm(long long x, long long y) { return x * y / gcd(x, y); }

int main() {
    //
    long long n, m;
    string s, t;
    long long kekka;
    long long tmpN, tmpM;
    long long g;

    cin >> n >> m >> s >> t;

    kekka = lcm(n, m);
    g = gcd(n, m);

    tmpN = n / g;
    tmpM = m / g;

    for (long long i = 0; i < g; i++) {
        if (s.at(i * tmpN) != t.at(i * tmpM)) {
            cout << -1;
            return 0;
        }
    }

    cout << kekka;
    //
}

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

using namespace std;

int main()
{
    string s,t;
    cin>>s>>t;
    int l=s.length()+1,r=t.length()+1;
    vector<vector<int>> x(l,vector<int>(r));
    for(int i=0;i<l;++i)
        for(int j=0;j<r;++j)
        {
            if(i==0||j==0)
                x[i][j]=0;
            else if(s[i-1]==t[j-1])
                x[i][j]=x[i-1][j-1]+1;
            else
                x[i][j]=max(x[i-1][j],x[i][j-1]);
        }
//    for(auto &i:x)
//    {
//        for(auto &j:i)
//            cout<<j<<' ';
//        cout<<'\n';
//    }
//    printf("%d\n",x[l-1][r-1]);
    string ans;
    int i=l-1,j=r-1;
    while(i&&j)
    {
        if(x[i][j-1]==x[i][j])
            --j;
        else if(x[i-1][j]==x[i][j])
            --i;
        else
        {
            --i;
            --j;
            ans+=s[i];
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<'\n';
}


Measured memory_bytes: 35584
n = int(input())
a = list(map(int,input().split()))
num = {}
cnt = 0
for i in range(n):
    i_minus_Ai = i-a[i]
    if i_minus_Ai in num:
        cnt += num[i_minus_Ai]

    i_plus_Ai = i+a[i]
    if i_plus_Ai in num:
        num[i_plus_Ai] += 1
    else:
        num[i_plus_Ai] = 1
print(cnt)

Measured memory_bytes: 40496
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <map>
#include <vector>
#include <cstdlib>
#include <stack>
#include <queue>
#include <list>
#include <set>

#define llong long long int

using namespace std;

int n;
llong x, p[51], l[51];

llong search (int n, llong cnt, llong ans) {
    //cout << cnt << endl;
    --cnt;
    //cout << cnt << endl;
    if (cnt == 0) return ans;
    if (cnt - l[n - 1] >= 0) {
        ans += p[n - 1];
        cnt -= l[n - 1];
    } else {
        return search(n - 1, cnt, ans);
    }
    if (cnt == 0) return ans;
    --cnt;
    ++ans;
    //cout << "hello" << endl;
    //cout << ans << " " << cnt << endl; 
    if (cnt == 0) return ans;
    if (cnt - l[n - 1] >= 0) {
        ans += p[n - 1];
        cnt -= l[n - 1];
    } else {
        return search(n - 1, cnt, ans);
    }
    if (cnt == 0) return ans;
    --cnt;
    if (cnt == 0) return ans;
}

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> x;
    p[0] = 1;
    l[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = 2 * p[i - 1] + 1;
        l[i] = 2 * l[i - 1] + 3;
    }

    cout << search(n, x, 0) << endl;
    return 0;
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (n == 1) {
    cout << 1 << endl;
    return 0;
  }
  int ans = 0;
  int f = (a[0] < a[1]);
  if (a[0] == a[1]) f = 2;
  for (int i = 1; i + 1 < n; i++) {
    if (f == 2) {
      f = (a[i] < a[i + 1]);
      if (a[i] == a[i + 1]) f = 2;
    }

    if (f) {
      if (a[i] > a[i + 1]) {
        f = 2;
        ans++;
      }
    } else {
      if (a[i] < a[i + 1]) {
        f = 2;
        ans++;
      }
    }
  }
  cout << ans + 1 << endl;

  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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 long long INF = 1LL << 60;

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

  cout << (x < 1200 ? "ABC" : "ARC") << endl;

  return 0;
}


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

typedef std::pair<double, int> P;

int main()
{
	int n, y;
	while( std::cin >> n, n )
	{
		std::cin >> y;

		P ans( 0, 0 );
		for( int i = 0; i != n; ++i )
		{
			int b, r, t;
			std::cin >> b >> r >> t;

			ans = std::max( ans, P( t - 1 ? pow( 1.0 + r / 100.0, y ) : 1.0 + y * r / 100.0, b ) );
		}

		std::cout << ans.second << std::endl;
	}

	return 0;
}

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

typedef long long int ll;

int main()
{
    ll n;
    cin >> n;

    ll ans = 1;

    for(ll i = 1;i <= n;i++){
        ans *= i;
        ans %= 1000000007;
    }

    cout << ans;

    return 0;
}

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

#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head=1, tail=1, n;
void initialize(){

}
bool isFull(){
    return head == (tail+1)%LEN;
}
bool isEmpty(){
    return head == tail;
}
void enqueue(P x){
    Q[tail] = x;
    if(tail+1==LEN) tail = 0;
    else tail++;
}

P dequeue(void){
    P x = Q[head];
    if(head+1==LEN) head = 0;
    else head++;
    return x; 
}


int main(){
    int c;
    int i, q;
    P u;
    scanf("%d %d", &n, &q);
    tail = n+1;
    for ( i = 1; i <= n; i++){
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].t);
    }
    int time = 0;
    while(!isEmpty()){
        P data = dequeue();
        if(data.t<=q){
            cout << data.name << " " << time+data.t << endl;
            time+=data.t;
        }
        else{data.t-=q;time+=q;enqueue(data);}
        
    }
    
  return 0;
}


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const double EPS = 1e-10;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int h = stoi(s.substr(0, 2)), m = stoi(s.substr(3, 2));
    double argh = 360. * h / 12 + 30. * m / 60, argm = 360. * m / 60;
    double diff = min(abs(argh - argm), 360 - abs(argh - argm));
    if (diff < 30) cout << "alert" << endl;
    else if (diff >= 90) cout << "safe" << endl;
    else cout << "warning" << endl;
  }

  return 0;
}


Measured memory_bytes: 3148
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String r=sc.next();
    String g=sc.next();
    String b=sc.next();
    int rgb=Integer.parseInt(r+g+b);

    if (rgb%4==0) {
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }
  }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

vector<ll> BPcnt(51);
vector<ll> Pat(51);
ll solve(ll L, ll X){
    if(X==BPcnt[L]){
        return Pat[L];
    }
    if(X==1){
        return 0;
    }
    if(L==0){
        return 1;
    }
    if(X<(BPcnt[L]+1)/2){
        return solve(L-1,X-1);
    }else if(X==(BPcnt[L]+1)/2){
        return 1+solve(L-1,X-1);
    }else{
        return 1+Pat[L-1]+solve(L-1,X-BPcnt[L-1]-2);
    }
}

int main(){
    ll N,X;
    cin >> N >> X;
    BPcnt[0] = 1;
    Pat[0] = 1;
    rep(i,50){
        BPcnt[i+1] = 2*BPcnt[i] + 3;
        Pat[i+1] = 2*Pat[i] + 1;
    }
    ll ans = solve(N,X);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,dep[N],fa[N][25];
struct data{
	int to,col,v;
};
vector<data>a[N];
int disx[N],disy[N],disz[N],X[N],Y[N],Z[N],Col[N],V[N],C[N];
int cnt[N],sum[N];
vector<int>Q[N];
void dfs(int x,int f){
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	for(int i=0;i<(int)a[x].size();i++){
		int y=a[x][i].to;
		if(y==f)continue;
		dfs(y,x);
	}
}
int Up(int x,int step){
	for(int i=0;i<=20;i++)
		if(step&(1<<i))x=fa[x][i];
	return x;
}
int LCA(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	y=Up(y,dep[y]-dep[x]);
	if(x==y)return x;
	for(int i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void dfs1(int x,int d){
	for(int i=0;i<(int)Q[x].size();i++){
		int y=Q[x][i];
		if(x==X[y])disx[y]=d-sum[Col[y]]+cnt[Col[y]]*C[y];
		if(x==Y[y])disy[y]=d-sum[Col[y]]+cnt[Col[y]]*C[y];
		if(x==Z[y])disz[y]=d-sum[Col[y]]+cnt[Col[y]]*C[y];
	}
	for(int i=0;i<(int)a[x].size();i++){
		int y=a[x][i].to,col=a[x][i].col,v=a[x][i].v;
		if(y==fa[x][0])continue;
		cnt[col]++;sum[col]+=v;
		dfs1(y,d+v);
		cnt[col]--;sum[col]-=v;
	}
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,col,v;
		scanf("%d%d%d%d",&x,&y,&col,&v);
		a[x].push_back((data){y,col,v});
		a[y].push_back((data){x,col,v});
	}
	dfs(1,0);
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&Col[i],&C[i],&X[i],&Y[i]);
		Q[X[i]].push_back(i);
		Q[Y[i]].push_back(i);
		Z[i]=LCA(X[i],Y[i]);
		Q[Z[i]].push_back(i);
	}
	dfs1(1,0);
	for(int i=1;i<=m;i++)printf("%d\n",disx[i]+disy[i]-2*disz[i]);
	return 0;
}

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

const int mod = 1000000007;
// const int mod = 998244353;

int main(){
    long long n,m;
    cin>>n>>m;
    vector<ll> v(m);
    rep(i,n){
      ll k;
      cin>>k;
      rep(j,k){
        ll p;
        cin>>p;
        v.at(p-1)+=1;
      }
    }

    ll a=0;
    rep(i,m){
      if(v.at(i)==n)a+=1;
    }
cout<<a;
}

Measured memory_bytes: 3592
import java.awt.*;
import java.lang.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;


public class Main {
    public void solve() throws IOException {
        int n = nextInt();
        int last = 0;
        int ans = 0;
        int a[] = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            a[i] = nextInt();
        }
        for (int i = 1; i < n + 2; i++) {
            ans += Math.abs(last - a[i]);
            last = a[i];
        }
        last = 0;
        for (int i = 1; i <= n; i++) {
            out.println(ans - Math.abs(last - a[i]) - Math.abs(a[i] - a[i + 1]) + Math.abs(last - a[i + 1]));
            last = a[i];
        }
    }

    BufferedReader br;
    StringTokenizer sc;
    PrintWriter out;

    public static void main(String[] args) throws IOException {
        Locale.setDefault(Locale.US);
        new Main().run();
    }

    void run() throws IOException {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
//            br = new BufferedReader(new FileReader("refrain.in"));
//            out = new PrintWriter(new File("refrain.out"));

            solve();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    String nextToken() throws IOException {
        while (sc == null || !sc.hasMoreTokens()) {
            try {
                sc = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return sc.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

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

// ??????????????§?????????????????????????????§???????????°??????????????§??£?¨???????
char field[1010][1010];
int J[1010][1010];
int O[1010][1010];
int I[1010][1010];

int main() {
  // ??\???
  int M, N, K;
  cin >> M >> N >> K;
  for (int y = 1; y <= M; y++) {
    for (int x = 1; x <= N; x++) {
      cin >> field[y][x];
    }
  }

  // ?????£?????°?????????????°??????¨????´????????????¨????????????????????????????????????????????°????¨?????????????????????????
  // ?´????????????¨?????????????????????
  for (int y = 1; y <= M; y++) {
    for (int x = 1; x <= N; x++) {
      if (field[y][x] == 'J') J[y][x] = 1;
      else if (field[y][x] == 'O') O[y][x] = 1;
      else I[y][x] = 1;
    }
  }
  // ?¨???????????´????????????¨???
  for (int y = 1; y <= M; y++) {
    for (int x = 2; x <= N; x++) {
      // J, O, I?????¨????´???????????¨??????????
      /* ********
         ********
         ******** */
      J[y][x] += J[y][x-1];
      O[y][x] += O[y][x-1];
      I[y][x] += I[y][x-1];
      
    }
  }
  // ?????????????´????????????¨???
  for (int x = 1; x <= N; x++) {
    for (int y = 2; y <= M; y++) {
      // ?¨?????????§?????£????????¨???????????????????????????
      /* ********
         ********
         ******** */
      J[y][x] += J[y-1][x];
      O[y][x] += O[y-1][x];
      I[y][x] += I[y-1][x];
      
    }
  }

  // ???????????\????????????????????????????´???????????????¨???????????°????????§?§£?????????
  int a, b, c, d;
  for (int i = 0; i < K; i++) {
    cin >> a >> b >> c >> d;
    cout << J[c][d] - J[a-1][d] - J[c][b-1] + J[a-1][b-1] << " ";
    cout << O[c][d] - O[a-1][d] - O[c][b-1] + O[a-1][b-1] << " ";
    cout << I[c][d] - I[a-1][d] - I[c][b-1] + I[a-1][b-1] << endl;
  }
  return 0;
}

Measured memory_bytes: 15788
#include <bits/stdc++.h>
using namespace std;
int INF = 1000000000;
int main(){
  string A;
  cin >> A;
  A = '$' + A;
  int N = A.size();
  vector<vector<int>> next(N, vector<int>(26, N));
  for (int i = N - 1; i >= 1; i--){
    next[i - 1] = next[i];
    next[i - 1][A[i] - 'a'] = i;
  }
  vector<int> dp(N + 1, INF);
  dp[N] = 0;
  for (int i = N - 1; i >= 0; i--){
    for (int j = 0; j < 26; j++){
      dp[i] = min(dp[i], dp[next[i][j]] + 1);
    }
  }
  string ans = "";
  int pos = 0;
  while (dp[pos] > 0){
    for (int i = 0; i < 26; i++){
      if (dp[next[pos][i]] == dp[pos] - 1){
        pos = next[pos][i];
        ans += 'a' + i;
        break;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 30912
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int N, K, A;
    cin >> N >> K;
    vector<int> count(N + 1, 0);

    REP(i, N){
        cin >> A;
        count[A]++;
    }

    SORT(count);
    reverse(count.begin(), count.end());

    int ans = 0;
    FOR(i, K, N + 1){
        ans += count[i];
    }

    cout << ans;
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
const long long INF = 1001001001;
const long long MOD = 1000000007;
const double EPS = 1e-10;

struct UnionFind {
    vector<int> d;
    int cc_cnt;
    UnionFind(int n): d(n, -1) { cc_cnt = n; }
    int find(int x) {
        if(d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        cc_cnt--;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};

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

    int n,m;
    cin>>n>>m;
    ll sum[n+1]={};
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+i;
    int a[m],b[m];
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        a[i]--; b[i]--;
    }
    ll ans[m];
    ll diff=0;
    UnionFind uf(n);
    for(int i=m-1;i>=0;i--){
        ans[i]=sum[n-1]-diff;
        if(i==0)break;
        if(uf.same(a[i],b[i]))continue;
        int x=uf.size(a[i]),y=uf.size(b[i]);
        diff-=(sum[x-1]+sum[y-1]);
        diff+=sum[x+y-1];
        uf.unite(a[i],b[i]);
    }
    for(int i=0;i<m;i++){
        cout<<ans[i]<<endl;
    }
}

Measured memory_bytes: 6112
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
 
n, m = map(int, input().split())
 
d = defaultdict(list)
for i in range(m):
  tx, ty = map(int, input().split())
  d[tx-1].append(ty-1)
  
dp = [0]*n
 
def dist(i):
  if dp[i] > 0:
    return dp[i]
  dp[i] = 0
  for ni in d[i]:
    dp[i] = max([dp[i], dist(ni)+1])
  return dp[i]
 
ans = 0
for i in range(n):
  ans = max(ans, dist(i))
    
print(ans)

Measured memory_bytes: 67824
# coding:utf-8

import sys
INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()
    A = LI()

    length = 40
    cnt = [0] * length
    for i in range(n):
        for j in range(length):
            if A[i] >> j & 1:
                cnt[j] += 1

    res = sum([k ^ a for a in A])
    for d in range(length):
        if k >> d & 1 == 0:
            continue

        t = 0
        for e in range(length):
            mask = 1 << e

            if e > d:
                if k & mask:
                    t += mask * (n - cnt[e])
                else:
                    t += mask * cnt[e]
            elif e == d:
                # e == dの時，X_iは必ず0
                t += mask * cnt[e]
            else:
                t += mask * max(cnt[e], n - cnt[e])

        res = max(res, t)

    return res


print(main())


Measured memory_bytes: 14748
from collections import  deque
import sys
import bisect
import math
import itertools
from queue import deque
from math import gcd

INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


N = inp()
A = [0] + inp_list()

ans_list = [0 for _ in range(N)]
for a in A:
    ans_list[a - 1] += 1
ans_list[-1] = 0
for ans in ans_list:
    print(ans)


Measured memory_bytes: 33720
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
typedef pair<int, int>P;
typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)
//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
map<ll, ll>ins;
void facterize(ll n) {
	ll a = 2;
	while (n >= a * a) {
		if (n % a == 0) {
			ins[a]++;
			ins[a] = ins[a] % 1000000007;
			n /= a;
		}
		else {
			a++;
		}
	}
	ins[n]++;
}

int keta(int x) {
	int y = 0;
	while (x > 0) {
		y++;
		x /= 10;
	}
	return y;
}

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

//long longしか使わない
int main() {
	string s;
	cin >> s;
	ll n = s.length() + 1;
	vector<ll>a(n);
	rep(i, n-1) {
		if (s[i] == '<')a[i + 1] = max(a[i + 1], a[i] + 1);
	}
	for (ll i = n - 2;i >= 0;--i) {
		if (s[i] == '>')a[i] = max(a[i], a[i + 1] + 1);
	}
	ll ans = 0;
	rep(i, n) {
		ans += a[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4740
S = input()
ss0 = []
ss1 = []
for i in range(len(S)):
    ss0.append(str(i%2))
    ss1.append(str((i+1)%2))

c0 = 0
c1 = 0
for s, s0, s1 in zip(S, ss0, ss1):
    if s != s0:
        c0 += 1
    if s != s1:
        c1 += 1

print(min(c0, c1))

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

#define times(n, i)      uptil(0, n, i)
#define rtimes(n, i)     downto((n) - 1, 0, i)
#define upto(f, t, i)    for(int _##i = (t), i = (f); i <= _##i; i++)
#define uptil(f, t, i)   for(int _##i = (t), i = (f); i <  _##i; i++)
#define downto(f, t, i)  for(int _##i = (t), i = (f); i >= _##i; i--)
#define downtil(f, t, i) for(int _##i = (t), i = (f); i >  _##i; i--)
typedef long double LD;
#define long long long

#if defined(EBUG) && !defined(ONLINE_JUDGE)
#define debug true
#define ln << endl
#else
#define debug false
#define ln << '\n'
#endif
#define tb << '\t'
#define sp << ' '



signed main() { // long: 64bit
    if(!debug) {
        cin.tie(0);
        ios::sync_with_stdio(0);
    }

    int N, T;
    scanf("%d%d",&N,&T);

    long ans = (long)N*T, before = -T;
    times(N, i) {
        int t;
        scanf("%d",&t);
        ans -= max(0LL, before + T - t);
        before = t;
    }

    cout << ans ln;

    return 0;
}


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

y = 0
for i in range(n):
    x = total /(4*m)
    if total //(4*m) == total /(4*m):
        if l[i] >= total //(4*m):
            y += 1
    else:
        if l[i] > total //(4*m):
            y += 1

if y >= m:
    print('Yes')
else:
    print('No')



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

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

#define F first
#define S second
#define MT make_tuple
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LBS 20
#define MOD ((long long)1e9+7) //1e9+9
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef double rat;
typedef long long bi;
typedef pair<int, int> ii;
typedef std::vector<ii> vii;
typedef std::map<int, int> mii;
typedef bitset<LBS> bis;
typedef std::vector<bis> vbs;

template<class T>
void in(T &a){
  for(auto &x: a)
    cin >> x;
}

template<class T>
void out(T &a, string sep=" "){
  for(auto x: a)
    cout << x<<sep;
  cout << '\n';
}

template<class T>
void err(T &a, string sep=" "){
  for(auto x: a)
    cerr << x <<sep;
  cerr << '\n';
}


int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n;
  std::vector<int> l(n); in(l);
  sort(ALL(l));
  ll cc=0;
  for(int i=0; i<n; i++)
    for(int j=i+1; j<n; j++){
      int a=lower_bound(ALL(l),l[i]+l[j])-l.begin();
      int b=upper_bound(ALL(l), abs(l[i]-l[j]))-l.begin();
      cc+=a-b;
      if(b<=i)
        cc--;
      if(b<=j)
        cc--;
      // cerr << i << " "<<j<<" "<<cc<<"\n";
    }
  cout << cc/3 << "\n";
}


Measured memory_bytes: 256