akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll unipar[4010];
ll unilen[4010];
vector<pll> vn[4010];
struct edge{
  ll len,from,to;
};
bool cmp(edge& a,edge& b){
  return a.len<b.len;
}
void uniinit(ll n){
  for(ll i=1;i<=n;i++){
    unipar[i]=i;
    unilen[i]=0;
  }
}
ll root(ll n){
  if(unipar[n]==n)return n;
  return unipar[n]=root(unipar[n]);
}
void unit(ll a,ll b){
  a=root(a);
  b=root(b);
  if(a==b)return;
  if(unilen[a]<unilen[b]){
    unipar[a]=b;
  }
  else{
    unipar[b]=a;
    if(unipar[b]==unipar[a])unilen[a]++;
  }
}
ll ne;
ll par[60][4010];
ll dep[4010];
void lcadfs(ll v,ll p,ll d){
  par[0][v]=p;
  dep[v]=d;
  for(ll i=0;i<vn[v].size();i++){
    if(vn[v][i].first!=p)lcadfs(vn[v][i].first,v,d+1);
  }
}
void lcainit(ll n){
  lcadfs(ne,-1,0);
  for(ll i=0;i<59;i++){
    for(ll j=1;j<=n;j++){
      if(par[i][j]<0)par[i+1][j]=-1;
      else par[i+1][j]=par[i][par[i][j]];
    }
  }
}
ll lca(ll u,ll v){
  if(dep[u]>dep[v])swap(u,v);
  for(ll i=0;i<60;i++){
    if((dep[v]-dep[u])>>i&1)v=par[i][v];
  }
  if(u==v)return u;
  for(ll i=59;i>=0;i--){
    if(par[i][u]!=par[i][v]){
      u=par[i][u];
      v=par[i][v];
    }
  }
  return par[0][u];
}
ll mae[60][4010];
void maedfs(ll v,ll p,ll dis){
  mae[0][v]=dis;
  for(ll i=0;i<vn[v].size();i++){
    if(vn[v][i].first!=p)maedfs(vn[v][i].first,v,vn[v][i].second);
  }
}
void maeinit(ll n){
  maedfs(ne,-1,-1);
  for(ll i=0;i<59;i++){
    for(ll j=1;j<=n;j++){
      if(par[i][j]<0)mae[i+1][j]=-1;
      else mae[i+1][j]=max(mae[i][j],mae[i][par[i][j]]);
    }
  }
}
ll maxedge(ll u,ll v){
  ll r=lca(u,v);
  ll ret=0;
  for(ll i=59;i>=0;i--){
    if((dep[u]-dep[r])>>i&1){
      ret=max(ret,mae[i][u]);
      u=par[i][u];
    }
  }
  for(ll i=59;i>=0;i--){
    if((dep[v]-dep[r])>>i&1){
      ret=max(ret,mae[i][v]);
      v=par[i][v];
    }
  }
  return ret;
}
int main(){
  ll n,m;cin>>n>>m;
  vector<edge> v;
  for(ll i=0;i<m;i++){
    ll a,b,c;cin>>a>>b>>c;
    v.push_back((edge){c,a,b});
  }
  sort(v.begin(),v.end(),cmp);
  uniinit(n);
  ll now=0;
  ll sum=0;
  for(ll i=0;i<m;i++){
    edge e=v[i];
    ll a=e.from,b=e.to;
    if(root(a)!=root(b)){
      unit(a,b);
      sum+=e.len;
      vn[a].push_back(make_pair(b,e.len));
      vn[b].push_back(make_pair(a,e.len));
      now++;
    }
    if(now==n-1)break;
  }
  ne=1;
  lcainit(n);
  maeinit(n);
  ll q;cin>>q;
  for(ll i=0;i<q;i++){
    ll s,t;cin>>s>>t;
    ll dd=maxedge(s,t);
    cout<<sum-dd<<endl;
  }
  //cout<<maxedge(5,7)<<endl;
  //for(ll i=0;i<10;i++){
    //for(ll j=1;j<=7;j++)cout<<par[i][j]<<" ";
    //cout<<endl;
  //}
}

Measured memory_bytes: 16616
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef vector<lint> LIV;
#define rep(i,n) for(int i=0;i<n;++i)
#define MAXN 100010
#define MAXM 1100000
#define all(v) v.begin(),v.end()
#define inf 2147483647
#define linf 1152921504606846976

#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef vector<lint> LIV;
#define rep(i,n) for(int i=0;i<n;++i)
#define MAXN 100010
#define MAXM 1100000
#define all(v) v.begin(),v.end()
#define inf 2147483647
#define linf 1152921504606846976
#define MAX_N 100010

lint digs(lint a){//各桁の和
	lint re=0;
	while(a)re+=a%10,a/=10;
	return re;
}

int main(){
	lint n;cin>>n;
	lint m=linf;
	rep(i,n-1){
		m=min(m,digs(i+1)+digs(n-i-1));
	}cout<<m<<endl;
}

//int main(){//平方数を1<k<=nで割ったあまりを求める
//	lint n;cin>>n;
//	LIV ans(n);
//	for(int i=1;i<=n;++i){
//		set<int> s;
//		rep(x,i)s.insert(x*x%i);
//		cout<<i<<": ";
//		for(auto x:s)cout<<x<<",";cout<<endl;
//		ans[i-1]=s.size();
//	}rep(i,n)cout<<ans[i]<<endl;
//	getchar();
//	getchar();
//}

//sub-EOF


Measured memory_bytes: 256
import java.io.*
import java.util.*

val pw = PrintWriter(System.out)
const val YES = "Yes"
const val NO = "No"
fun solve(H: Long, N: Long, A: LongArray){
    if (A.sum() >= H) println(YES) else println(NO)
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val H = sc.next().toLong()
    val N = sc.next().toLong()
    val A = LongArray(N.toInt())
    for (i in 0 until N.toInt()) {
        A[i] = sc.next().toLong()
    }
    solve(H, N, A)
}



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

#define _PI 60.*M_PI/180.

typedef struct{
  double x, y;
} Point;

Point add(Point,Point);
Point sub(Point,Point);
Point mul(Point,double);
Point div(Point,double);
void solve(Point,Point,int);

int main(){
  int n;
  Point p1, p2;

  p1.x = p1.y = p2.y = 0;
  p2.x = 100;

  scanf("%d" ,&n);
  solve(p1,p2,n);
  printf("%.8f %.8f\n" ,p2.x ,p2.y);

  return 0;
}

Point add(Point a,Point b){
  Point c;

  c.x = a.x + b.x;
  c.y = a.y + b.y;

  return c;
}

Point sub(Point a,Point b){
  Point c;

  c.x = a.x - b.x;
  c.y = a.y - b.y;

  return c;
}

Point mul(Point a,double k){
  Point c;

  c.x = a.x * k;
  c.y = a.y * k;

  return c;
}

Point div(Point a,double k){
  Point c;

  c.x = a.x / k;
  c.y = a.y / k;

  return c;
}

void solve(Point a,Point b,int rem){
  Point c = div(sub(b,a),3.), d = mul(c,2.);
  Point s = add(a,c), t = add(a,d), u;

  if(rem == 0){
    printf("%.8f %.8f\n" ,a.x ,a.y);
    return;
  }

  u.x = s.x + (t.x - s.x) * cos(_PI)
    - (t.y - s.y) * sin(_PI);

  u.y = s.y + (t.x - s.x) * sin(_PI)
    + (t.y - s.y) * cos(_PI);

  solve(a,s,rem-1);
  solve(s,u,rem-1);
  solve(u,t,rem-1);
  solve(t,b,rem-1);
}

Measured memory_bytes: 640
# coding: utf-8
# Your code here!
import heapq

N,M=map(int,input().split())
l=[[0] for _ in range(M)]
ans=[]
count=0

for _ in range(N):
    A,B=map(int,input().split())
    if A>M:
        continue
    else:
        l[A-1].append(B*(-1))

for lis in l:
    for item in lis:
        heapq.heappush(ans,item)
    count-=heapq.heappop(ans)

print(count)

Measured memory_bytes: 19264
#include <iostream>
#define rep(a,i,n) for(int i=(a);i<(n);i++)

using namespace std;

int main(){
	int n,k,count=0;
	cin >> n >> k;
	int d[k];
	int a[k][n];
	rep(0,i,k){
		cin >> d[i];
		rep(0,j,d[i]){
			cin >> a[i][j];
		}
	}

	rep(1,temp,n+1){
		rep(0,i,k){
			rep(0,j,d[i]){
				if(temp == a[i][j]){
					goto Exit;
				}
			}
		}
		count++;
		Exit:
		;
	}
	cout << count << endl;
}

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

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

  vector<int64_t> c(27,0);
  for(int i=1;i<=26;++i) cin>>c[i];

  vector<vector<int64_t>> s(D+1,vector<int64_t>(27,0));
  for(int i=1;i<=D;++i){
    for(int j=1;j<=26;++j){
      cin>>s[i][j];
    }
  }

  vector<int> t(D+1);

  int64_t score=0;
  vector<vector<int>> last(D+1,vector<int>(27,0));

  for(int i=1;i<=D;++i){

    int ind=0;
    int64_t sum=-1e10;
    
    for(int j=1;j<=26;++j){
      int64_t cmp=s[i][j]+c[j]*(i-last[i-1][j]);
      if(cmp>sum){
        sum=cmp;
        ind=j;
      }
    }
    
    t[i]=ind;
    
    for(int j=1;j<=26;++j){
      if(j==t[i]) last[i][j]=i;
      else last[i][j]=last[i-1][j];
    }

    score += s[i][t[i]];
    
    for(int j=1;j<=26;++j){
      score -= c[j]*(i-last[i][j]);
    }
    
  }

  for(int i=1;i<=D;++i){
    cout<<t[i]<<endl;
  }

}

Measured memory_bytes: 3780
#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define scs(x) scanf("%s",x)
#define pr(x) printf("%d",x)
#define prn(x) printf("%d\n",x)
#define memc(x,y) memcpy(&x,&y,sizeof(x))
#define mems(x,y) memset(x,y,sizeof(x))
#define fli() freopen("in.txt","r",stdin)
#define flo() freopen("out.txt","w",stdout)
#define rep(i,v) for(int i=0;i<v;i++)
#define repe(i,v) for(int i=0;i<=v;i++)
#define Rep(i,x,v) for(int i=x;i<v;i++)
#define Repe(i,x,v) for(int i=x;i<=v;i++)
#define repv(i,x) for(auto i=x.begin();i!=x.end();i++)
#define reprv(i,x) for(auto i=x.rbegin();i!=x.rend();i++)
#define dbg(x) cout << #x << " : " << x << endl
#define pb push_back
#define bl putchar('\n')
#define gcc getchar()
#define pcc putchar
#define si size
#define fi first
#define se second
#define MAX 300000
typedef long long ll;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef std::pair<int,int> ii;
using namespace std;

long long int cm_sum[MAX] = {0};
long long int MM=1000000000+7;

int main(){
  // fli();
  int n;
  long long int a[MAX];
  long long int ans = 0;
  mems(cm_sum, 0);
  sc(n);
  rep(i,n){
    cin>>a[i];
    if(i){
      cm_sum[i] = (cm_sum[i-1] + a[i]) % MM;
      ans += (cm_sum[i-1]%MM * a[i]%MM) % MM;
      ans%=MM;
      // cout<<(cm_sum[i-1]) << " with " << a[i] << " : "<<((cm_sum[i-1]%MM * a[i]%MM) % MM)<<endl;
    }else{
      cm_sum[i] = a[i];
    }
  }
  // bl;
  // rep(i,n){
  //   cout<<cm_sum[i]<<' ';
  // }
  // bl;

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


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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

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

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    int a, b, c, k; cin >> a >> b >> c >> k;
    int count = 0; 
    while(a >= b){
        b *= 2;
        count++;
    }
    while(b >= c){
        c *= 2;
        count++;
    }
    if(count <= k){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,A,B;
int X[111111];

signed main(){
    cin>>N>>A>>B;
    rep(i,N)cin>>X[i];

    int ans=0;
    for(int i=0;i+1<N;i++){
        ans+=min((X[i+1]-X[i])*A,B);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
var
  ch:char;
  st:string; 
begin
  while not eof do  
   begin
     read(ch);  
     if (ch='1') or (ch='0') then 
      st:=st+ch;  
     if (ch='B') and (length(st)>0) then  
      delete(st,length(st),1);  
   end;
  writeln(st);  
end.

Measured memory_bytes: 128
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    let n = read::<usize>();
    let mut v = vec![];
    for _ in 0..n { v.push(read::<u32>()); }

    let mut v2 = v.clone();
    v2.sort();
    let max1 = v2.pop().unwrap();
    let max2 = v2.pop().unwrap();

    for i in 0..n {
        if v[i] == max1 {
            println!("{}", max2);
        } else {
            println!("{}", max1);
        }
    }
}


Measured memory_bytes: 7676
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

void rec(int v, int p, int& index, vector<int>& ans, const vi& val,
	 const vector<vi>& tree) {
  if (ans[v] >= 0) {
    return;
  }
  ans[v] = val[index++];

  for (int u : tree[v]) {
    if (u == p) continue;
    rec(u, v, index, ans, val, tree);
  }
  return;
}

int main(){
  int n;
  cin >> n;
  vector<vi> tree(n);
  rep(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    tree[a].push_back(b);
    tree[b].push_back(a);    
  }
  vector<int> c(n);
  rep(i, n) {
    cin >> c[i];
  }
  sort(all(c));

  ll sum = 0;
  rep(i, n-1) {
    sum += c[i];
  }
  cout << sum << endl;

  reverse(all(c));
  vector<int> ans(n, -1);
  int index = 0;
  rec(0, -1, index, ans, c, tree);
  rep(i, n) {
    cout << ans[i] << " \n"[i==n-1];
  }
}


Measured memory_bytes: 1664
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		if (B%A==0) {
			System.out.println(A+B);
		}else {
			System.out.println(B-A);
		}
	}
}

Measured memory_bytes: 24276
fun main(){
    var (hpOfTakahashi,attackOfTakahashi,hpOfAoki,attackOfAoki) = readLine()?.split(" ")!!.map { it.toInt() }
    var result = buttle(hpOfTakahashi,attackOfTakahashi,hpOfAoki,attackOfAoki)
    println(result)
}

fun buttle(hpOfTakahashi : Int,attackOfTakahashi : Int, hpOfAoki : Int,attackOfAoki :Int) : String{
    var turnOfTakahashi : Boolean = true
    var hpOfTakahashi = hpOfTakahashi
    var hpOfAoki = hpOfAoki
    while (hpOfTakahashi > 0 && hpOfAoki > 0){
        if (turnOfTakahashi){
            hpOfAoki -= attackOfTakahashi
            turnOfTakahashi = false
        }else{
            hpOfTakahashi -= attackOfAoki
            turnOfTakahashi = true
        }
    }
    if (hpOfTakahashi <= 0){
        return "No"
    }else{
        return "Yes"
    }
}


Measured memory_bytes: 36376
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define mk make_pair
using namespace std;
int n,m,h,w,x2,y2;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
string s[1001];
bool b[1001][1001];
bool bfs(int y3,int x3){
  int y=0,x=0;
  b[0][0]=1;
  queue<pair<int,int> >q;
  q.push(mk(x3,y3));
  while(!q.empty()){
    pair<int,int>p=q.front();q.pop();
    int xx=p.first,yy=p.second;
    r(i,4){
      int x1=xx+dx[i],y1=yy+dy[i];
      if(x1<0||y1<0||x1>=w||y1>=h)continue;
      if(!b[y1][x1]&&s[y1][x1]!='#'){
	if(s[y1][x1]=='t')return 1;
	b[y1][x1]=1;
	q.push(mk(x1,y1));
      }
      else b[y1][x1]=1;
    }
  }
  return 0;
}
int main(){
  cin>>w>>h;
  r(i,h)cin>>s[i];
  cin>>m;
  if(bfs(0,0)){
    cout<<0<<endl;
    return 0;
  }
  r(i,m){
    cin>>x2>>y2;
    if(s[y2][x2]=='.')continue;
    s[y2][x2]='.';
    if(b[y2][x2])if(bfs(y2,x2)){
      cout<<i+1<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
}

Measured memory_bytes: 5092
#include<cstdio>
using namespace std;
int K,N,ans;
int main(){
	scanf("%d%d",&N,&K);
	if(K==2)ans=N-1;
	else if(K>=N)ans=1;
	else {
		N-=K;
		ans=1;
		if(N%(K-1)==0)ans+=N/(K-1);
		else ans+=N/(K-1)+1;
	}
	printf("%d",ans);
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdbool.h>
 
#define MAX 100001
 
typedef struct {
  int id, time;
} State;
 
State queue[MAX];
int head, tail;
 
void push(int id,int tm) {
  queue[tail].id = id, queue[tail].time = tm;
  tail = ((tail+1==MAX)?0:tail+1);
}
 
State pop() {
  State v = queue[head];
  head = ((head+1==MAX)?0:head+1);
  return v;
}
 
inline bool empty() { return (tail - head) == 0; }
 
int n, q;
char P[MAX][200];
 
void exec() {
  int total_time = 0;
  while( !empty() ) {
    if( queue[head].time > q ) {
      queue[head].time -= q;
      State tmp = pop();
      push(tmp.id,tmp.time);
      total_time += q;
    } else {
      total_time += queue[head].time;
      printf("%s %d\n",P[queue[head].id],total_time);
      pop();
    }
  }
}
 
int main() {
  int i, T;
  scanf("%d %d",&n,&q);
  for(i=0;i<n;++i) {
    scanf(" %s %d",&P[i][0],&T);
    push(i,T);
  }
  exec();
  return 0;
}


Measured memory_bytes: 12248
#include<stdio.h>
#include<math.h>
#include<algorithm> 
#define reg register
#define ri reg int
#define rep(i, x, y) for(ri i = x; i <= y; ++i)
#define nrep(i, x, y) for(ri i = x; i >= y; --i)
#define DEBUG 1
#define ll long long
#define max(i, j) (i) > (j) ? (i) : (j)
#define min(i, j) (i) < (j) ? (i) : (j)
struct IO {
	#define MAXSIZE (1 << 20)
	#define isdigit(x) (x >= '0' && x <= '9')
	char buf[MAXSIZE], *p1, *p2;
	char pbuf[MAXSIZE], *pp;
	#if DEBUG
	#else
		IO() : p1(buf), p2(buf), pp(pbuf) {}
		~IO() {
			fwrite(pbuf, 1, pp - pbuf, stdout);
		}
	#endif
	inline char gc() {
		#if DEBUG
    		return getchar();
		#endif
    	if(p1 == p2)
			p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    	return p1 == p2 ? ' ' : *p1++;
	}
	inline bool blank(char ch) {
    	return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
	}
	template <class T>
	inline void read(T &x) {
    	register double tmp = 1;
    	register bool sign = 0;
    	x = 0;
    	register char ch = gc();
    	for(; !isdigit(ch); ch = gc())
    		if(ch == '-') sign = 1;
    	for(; isdigit(ch); ch = gc())
			x = x * 10 + (ch - '0');
    	if(ch == '.')
			for(ch = gc(); isdigit(ch); ch = gc())
        		tmp /= 10.0, x += tmp * (ch - '0');
    	if(sign) x = -x;
	}
	inline void read(char *s) {
		register char ch = gc();
		for(; blank(ch); ch = gc());
		for(; !blank(ch); ch = gc())
			*s++ = ch;
    	*s = 0;
	}
	inline void read(char &c) {
    	for(c = gc(); blank(c); c = gc());
	}
	inline void push(const char &c) {
		#if DEBUG
    		putchar(c);
		#else
    		if(pp - pbuf == MAXSIZE) {
				fwrite(pbuf, 1, MAXSIZE, stdout);
				pp = pbuf;
			}
    		*pp++ = c;
		#endif
	}
	template <class T>
	inline void write(T x) {
    	if(x < 0) {
			x = -x;
			push('-');
		}
    	static T sta[35];
    	T top = 0;
    	do{
			sta[top++] = x % 10;
			x /= 10;
    	}while(x);
    	while(top)
			push(sta[--top] + '0');
	}
	template <class T>
	inline void write(T x, char lastChar) {
    	write(x);
		push(lastChar);
	}
} io;
int aa[1000010], cnt[1000010], belong[1000010];
int n, m, size, bnum, now, ans[1000010];
struct query { /*询问*/
	int l, r, id;
} q[1000010];

int cmp(query a, query b) {
	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r); /*奇偶优化后的排序*/
}
int main() {
	io.read(n), io.read(m);
	size = sqrt(n);
	bnum = ceil((double)n / size);
	rep(i, 1, bnum) 
		rep(j, (i - 1) * size + 1, i * size) {
			belong[j] = i; /*依旧不知道所以然的离散化*/
		}
	rep(i, 1, n) io.read(aa[i]); 
	rep(i, 1, m) {
		io.read(q[i].l), io.read(q[i].r);
		q[i].id = i; /*读入每一个询问*/
	}
	std::sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	rep(i, 1, m) {
		int ql = q[i].l, qr = q[i].r; /*莫队主体*/
		while(l < ql) now -= !--cnt[aa[l++]]; /*需要移动就移,在移的过程中更新答案*/
		while(l > ql) now += !cnt[aa[--l]]++;
		while(r < qr) now += !cnt[aa[++r]]++;
		while(r > qr) now -= !--cnt[aa[r--]];
		ans[q[i].id] = now;
	}
	rep(i, 1, m) io.write(ans[i], '\n');
}

Measured memory_bytes: 17356
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self.width * (h + 2) + w + 2

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2])

        unsearched = -1
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            if x == self.goal:
                break
            cur_dist = dist[x]

            for dx in move:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] == unsearched or dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)

            for dx in warp:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] == unsearched or dist[nx] > cur_dist + 1:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        return dist[self.goal]

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


if __name__ == "__main__":
    main()


Measured memory_bytes: 219852
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>

using ll = unsigned long long;
using namespace std;

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

    int ans = 0;
    for ( int i = 1; i <= n; ++i) {
        if (to_string(i).size() & 1) {
            ans++;   
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
def dfs(i, f):
    if i == n-1: #もし枝が最後のけたに到達したら、という条件式
        return sum (list(map(int, f.split('+'))))
    
    #式fの末尾に'+'を追加する/追加しないをして次の数字を追加
    return dfs(i+1, f+s[i+1]) + dfs(i+1, f+'+'+s[i+1])
s = input()
n = len(s)
print(dfs(0, s[0]))


Measured memory_bytes: 9112
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // double
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ios::sync_with_stdio(false);
  int n;
  scanf("%d", &n);
  vi data(n);
  rep(i,n) scanf("%d", &data[i]);
  reverse(data.begin(), data.end());
  rep(i,n - 1) cout << data[i] << " ";
  cout << data[n - 1] << "\n";
}


Measured memory_bytes: 3204
/*I MAY NOT GET THE SUCCESS IMMEDIATELY BUT I WILL GET IT FOR SURE*/
#include<bits/stdc++.h>
#define opt std::ios_base::sync_with_stdio(false)
#define I int
#define li      int32_t
#define lli     long long
#define ulli unsigned long long

#define pn           printf("\n")
#define nl           cout<<'\n'
#define sf(N)        scanf("%lld",&N)
#define pf(N)        printf("%lld",N)
#define sf1(N1,N2)    scanf("%lld %lld",&N1,&N2)
#define pf1(N1,N2)    printf("%lld %lld",N1,N2)
#define sf2(N1,N2,N3) scanf("%lld %lld %lld",&N1,&N2,&N3)
#define pf2(N1,N2,N3) printf("%lld %lld %lld",N1,N2,N3)

#define sl          cout<<' '
#define ps          printf(" ")

#define rep(i,a,b)  for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>b;i--)
#define elif        else if
#define mset(a,b)   memset(a,b,sizeof(a))

#define pb      push_back
#define pob     pop_back
#define itr     iterator
#define sz()    size()
#define szof    sizeof
#define lb      lower_bound
#define ub      upper_bound
#define mp      make_pair
#define vlli    vector<lli>
#define plli    pair<lli,lli>
#define vplli   vector<plli >
#define F       first
#define S       second
#define Dup     erase(unique(V.begin(),V.end()),V.end())

#define bs      binary_search
#define ub      upper_bound
#define lb      lower_bound

#define ALL(V)  V.begin(),V.end()

#define MX1     100000
#define MX2     1000000
#define MX3     10000
#define mod     1000000007
#define Inf     1000000000000000
using namespace std;

lli Power(lli a,lli b)
{
    lli result=1;

    while(b)
    {
        if(b%2)
        {
            result=(result*a)%mod;
        }

        b=b>>1;
        a=(a*a)%mod;
    }

 return result;
}

lli Count[MX2+1];

int main()
{
    opt;
    
    /*#ifndef ONLINE_JUDGE
    freopen("double_squares.txt","r",stdin);
    freopen("double_squares_out.txt","w",stdout);
    #endif // */
    
    lli N,i;
    cin>>N;
    
    vlli V(N+1);
    
    rep(i,0,N)
    {
        cin>>V[i+1];
    }
    
    lli Number=0;
    rep(i,1,N+1)
    {
        if(V[i]==i)
        {
            Number++;
            i++;
        }
    }
    
    cout<<Number;

    


    
    
    

 return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(x) begin(x),end(x)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
	int N, M;
	cin >> N >> M;

	vector<int> e( M );
	for( auto &x : e )
	{
		cin >> x;
	}

	reverse( ALL( e ) );

	vector<int> vc, flag( N + 1, 0 );
	REP( i, M )//O(n)
	{
		if( flag[ e[ i ] ] == 0 )//O(1)
		{
			vc.emplace_back( e[ i ] );//O(1)
			flag[ e[ i ] ] = 1;
		}
	}

	//move
	for( const auto &x : vc )
	{
		cout << x << endl;
	}

	sort( ALL( vc ) );

	//not move
	REP2( i, 1, N + 1 )//O(n)
	{
		if( flag[ i ] != 0 )//O(1)
		{
			continue;
		}
		cout << i << endl;
	}

	return 0;
}

Measured memory_bytes: 4636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using ll = long long;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<ll> VLL;
typedef vector<string> VS;

int main() {
  int n; cin >> n;
  VI A(n); rep(i, n)cin >> A.at(i);

  int p = 0;
  int x = A.at(n-1);
  rep(i, n-1) {
    if(A.at(i) <= x) {
      swap(A.at(p), A.at(i));
      p++;
    }
  }
  swap(A.at(p), A.at(n-1));
  rep(i, n-1) {
    if (i == p) {
      cout <<  "[" << A.at(i) << "]" << " ";
    } else {
      cout << A.at(i) << " ";
    }
  }
  if (n-1 == p) {
    cout <<  "[" << A.at(n-1) << "]" << endl;
  } else {
    cout << A.at(n-1) << endl;
  }
}



Measured memory_bytes: 3156
N = int(input())
A = []
B = []
s = 0
for x in range(N):
    a, b = input().split()
    a = int(a)
    b = int(b)
    A.append(a)
    B.append(b)
for i in range(N):
    if A[i] == B[i]:
        s = s+1
    else:
        if s >= 3:
            s = s + 0
        else:
            s = 0
if s >= 3:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9224
def abc160c_traveling_salesman_around_lake():
    k, n = map(int, input().split())
    a = list(map(int, input().split()))
    total = 0
    max_distance = 0
    for i in range(n - 1):
        total += a[i + 1] - a[i]
        max_distance = max(max_distance, a[i + 1] - a[i])
    total += k - a[n - 1] + a[0]
    max_distance = max(max_distance, k - a[n - 1] + a[0])
    print(total-max_distance)
abc160c_traveling_salesman_around_lake()

Measured memory_bytes: 32348
#include <bits/stdc++.h>
#include <tr1/unordered_map>
#define ri register int
#define ptf printf
using namespace std;
typedef double db;
typedef long double ld;
typedef long long ll;
typedef vector <int> poly;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef unsigned long long ulll;
typedef unsigned int uii;
typedef string strr;
#define fi first
#define se second
#define pb push_back
#define ppp pop_back
#define rez resize
const ll Inf = 2e18;
const int rlen = 1 << 20, inf = 0x3f3f3f3f;
char buf[rlen], *ib = buf, *ob = buf;
#define gc() getchar()//(((ib == ob) && (ob = (ib =  buf) + fread(buf, 1, rlen, stdin)), ib == ob) ? -1 : *ib++)
inline int read() {
  static int ans, f;
  static char ch;
  ans = 0, ch = gc(), f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = gc();
  while (isdigit(ch)) ans = (ans << 3) + (ans << 1) + (ch ^ 48), ch = gc();
  return f ? ans: -ans;
}
inline ll readl() {
  static ll ans;
  static char ch;
  for (ans = 0, ch = gc(); !isdigit(ch); ch = gc());
  while (isdigit(ch)) ans = ((ans << 2) + ans << 1) + (ch ^ 48), ch = gc();
  return ans;
}
inline int Read(char *s) {
  static int top;
  static char ch;
  top = 0, ch = gc();
  while (!isalpha(ch) && !isdigit(ch)) ch = gc();
  while (isalpha(ch) || isdigit(ch)) s[++top] = ch, ch = gc();
  return top;
}
namespace modular {
  const int mod = 998244353;//= 1e9 + 7;
  //int mod;
  int ret;
  inline int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
  inline int dec(int a, int b) { return a < b ? a - b + mod : a - b; }
  inline int mul(int a, int b) { return (ll) a * b % mod; }
  inline void Add(int &a, int b) { a = a + b < mod ? a + b : a + b - mod; }
  inline void Dec(int &a, int b) { a = a < b? a - b + mod : a - b; }
  inline void Mul(int &a, int b) { a = (ll) a * b % mod; }
  inline int ksm(int a, int p) {
    for (ret = 1; p; p >>= 1, Mul(a, a)) (p & 1) && (Mul(ret, a), 1);
    return ret;
  }
  inline int Inv(int a) { return ksm(a, mod - 2); }
  inline int sqr(int a) { return (ll) a * a % mod; }
  inline int cub(int a) { return (ll) a * a % mod * a % mod; }
} using namespace modular;
template <typename T> inline void ckmax(T &a, T b) { a < b ? a = b : 0; }
template <typename T> inline void ckmin(T &a, T b) { a > b ? a = b : 0; }
template <typename T> inline T Abs(T a) { return a < 0 ? -a : a; }
template <typename T> inline T gcd(T a, T b) {
  T t;
  while (b) t = a, a = b, b = t - t / a * a;
  return a;
}
template <typename T> inline void exgcd(T a, T b, T &x, T &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a - a / b * b, y, x);
  y -= a / b * x;
}
const int N = 1e6 + 5;
int n;
pii a[N];
char s[N];
bool vs[N];
int main() {
  #ifdef ldxcaicai
  freopen("lx.in", "r", stdin);
  #endif
  int X = read();
  n = read();
  for (ri i = 1; i <= n; ++i) {
    vs[read() + 200] = 1;
  }
  int tot = 0;
  for (ri i = -200; i <= 200; ++i) if (!vs[i + 200]) a[++tot] = pii(Abs(i - X), i);
  sort(a + 1, a + tot + 1);
  cout << a[1].se;
  return 0;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

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

	string s; cin >> s;
	string t;

	FOR(i,0,sz(s)) {
		if (s[i] == 'A') t += '0';
		else if (s[i] == 'B') {
			if (i+1 < sz(s) && s[i+1] == 'C') t += '1', i++;
			else t += ' ';
		} else if (s[i] == 'C') t += ' ';
		else assert(0);
	}
	
	//cout << t << endl;

	ll res = 0;
	stringstream ss(t);
	while (ss >> s) {
		ll count = 0;
		for (char c: s) {
			if (c == '0') count++;
			else res += count;
		}
	}
	cout << res << endl;
}



Measured memory_bytes: 916
#include <algorithm>
#include <cstdio>

using namespace std;

int main(void)
{
    int n, m, a, b;
    scanf("%d %d", &n, &m);
    int dist = 0;
    for(int i=0; i<m; i++) {
        scanf("%d %d", &a, &b);
        dist = min(a-1, n - a);
        dist = min(dist, min(b-1, n-b));
        printf("%d\n", dist % 3 + 1);
    }
    return 0;
}

Measured memory_bytes: 1024
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <boost/lexical_cast.hpp>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

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

  int answer = 0;
  for (int i = A; i <= B; i++) {
    string s = boost::lexical_cast<string>(i);
    const string t = s;
    reverse(ALL(s));
    if (s == t) {
      answer++;
    }
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 3560
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pII;
#define pb push_back
#define X first
#define Y second
#define mp make_pair
#define clr(x,y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1e6+5;
//ll fmod(ll x,ll y){ll res=1;while(y){if(y&1)res=res*x%mod;y>>=1;x=x*x%mod;}return res;}
//ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
int main()
{
int n,m;
while(cin>>n>>m)
{
    int ans = 1;
    for(int i = 1; i*i <= m; ++i)
    {
        if((m%i) == 0)
        {
            if(m/i >= n)
                ans = max(i,ans);
            if(m/(m/i) >= n)
                ans = max(ans,(m/i));
                //cout<<i<<"  "<<ans<<endl;
        }
    }
    cout<<ans<<endl;
}
}












Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
#define rep(i,n) for(i=0; i<n; i++)

int main(void)
{
	char s[7];
	scanf("%s", s);
	if(s[2]==s[3] && s[4]==s[5]) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define G() Cr=getchar()
int Xr;char Cr;
inline int rd(){
	Xr=0, G();
	while(Cr<'0'||Cr>'9')G();
	while(Cr>='0'&&Cr<='9')Xr=(Xr<<3)+(Xr<<1)+Cr-'0', G();
	return Xr;
}
int n,m;
int va[1000],sum;
int main(){
	n=rd(), m=rd();
	for(int i=1;i<=n;i++)va[i]=rd(), sum+=va[i];
	sort(va+1,va+1+n);
	for(int i=n;i>=n-m+1;i--){
		if(va[i] < sum*1.0/4/m){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
}

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


int main() {
    int H, W;
    cin >> H >> W;

    int dist[1010][1010];
    REP(i, H) { REP(j, W) dist[i+1][j+1] = -1; };

    char c;
    queue<pair<int, int> > q;
    for (int i=1; i<=H; i++) {
        for (int j=1; j<=W; j++) {
            cin >> c;
            if (c=='#') {
                dist[i][j] = 0;
                q.push(make_pair(i, j));
            }
        }
    }

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        REP(i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (1 <= ny && ny <= H && 1 <= nx && nx <= W && dist[ny][nx] == -1) {
                dist[ny][nx] = dist[y][x] + 1;
                q.push(make_pair(ny, nx));
            }
        }
    }

    int ans = 0;
    REP(i, H) {
        REP(j, W) {
            ans = max(ans, dist[i+1][j+1]);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 12432
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
//	int k;
//	for(k=min(a,b);k<=2;k--){
//		if(a%k==0&&b%k==0)return k;
//	}
//	return 1;
//	int c;
//	c=a%b;
//	if(c==0)return b;
//	a=b;b=c;
//	return gcd(a,b);
	if(b==0)return a;
	return gcd(b,a%b);
}
int main() {
	int x,y;
	cin>>x>>y;
	cout<<gcd(x,y)<<endl;
	return 0;
}

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

int n, k;


int arr[2001][2001];
int arr_doubled[4002][4002];
int get(int y, int x){ 
  return arr_doubled[y+k-1][x+k-1]+arr_doubled[y-1][x-1]-arr_doubled[y-1][x+k-1]-arr_doubled[y+k-1][x-1];
}
int main() {
  /*int n = 2;
  int m = 4;
  int sum = 0;
  for (int i=1; i<=n; i++){
    int x = m*(m+1)/2;
    sum += n*m*m-n*x+m*n-i*m*m+i*x-m*i+m*m-x+m;
  }
  cout << sum;*/
  cin >> n >> k;
 
  for (int i=0; i<n; i++){
    int x, y;
    char c;
    cin >> x >> y >> c;
    if (c == 'W'){
      x += k;
    }
   
    arr[y%(2*k)][x%(2*k)]++;
  }
  
  for (int i=1; i<=4*k; i++){
    for (int j=1; j<=4*k; j++){
      arr_doubled[i][j] = arr_doubled[i][j-1]+arr[(i-1)%(2*k)][(j-1)%(2*k)];
    }
  }

 
  for (int i=1; i<=4*k; i++){
    for (int j=2; j<=4*k; j++){
      arr_doubled[j][i] += arr_doubled[j-1][i];
    }
  }
  int biggest = -1;
  for (int i=1; i<=2*k; i++){
    for (int j=1; j<=2*k; j++){
      biggest = max(get(i, j)+get(i+k, j+k), biggest);
      
    }
  }
  cout << biggest;
  return 0;
}

Measured memory_bytes: 78464
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;
int g[15][15];

int main() {
  int n;
  cin >> n;
  rep(i, n)rep(j, n) g[i][j] = -1;
  rep(i, n) {
    int m;
    cin >> m;
    rep(j, m) {
      int a, x;
      cin >> a >> x;
      --a;
      g[i][a] = x;
    }
  }

  int ans = 0;
  rep(i, 1<<n) {
    vector<int> d(n);
    rep(j, n) if (i>>j&1) {
      d[j] = 1;
    }
    bool ok = true;
    rep(j, n) {
      if (d[j]) {
        rep(k, n) {
          if (g[j][k] == -1) continue;
          if (g[j][k] != d[k]) ok = false;
        }
      }
    }
    if (ok) ans = max(ans, __builtin_popcount(i));
  }
  cout << ans << endl;

  return 0;
}


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

/*struct pair {
	int x;
	int y;
};*/


int main() {
	int k;
	std::cin >> k;
	if (k < 10) {
		std::cout << k << std::endl;
		return 0;
	}
	long long int a[100000];
	long long int ima[100000];
	for (int i = 0; i < 100000; i++) {
		a[i] = -1;
		ima[i] = -1;
	}
	for (int i = 0; i < 9; i++) {
		a[i] = i + 1;
	}
	a[10] = -1;
	int count = 9;
	bool flug = true;

  	int j=0;
	while (flug) {
		j = 0;
		for (int i = 0; a[i] > -1; i++) {
			if (a[i] % 10 == 0) {
				ima[j] = a[i] * 10 + 0;
				count++;
				if (count == k) { std::cout << ima[j] << std::endl; flug = false; break; }
				ima[j + 1] = a[i] * 10 + 1;
				count++;
				if (count == k) { std::cout << ima[j+1] << std::endl; flug = false; break; }
				j += 2;
			}
			else if (a[i] % 10 == 9) {
				ima[j] = a[i] * 10 + 8;
				count++;
				if (count == k) { std::cout << ima[j] << std::endl; flug = false; break; }
				ima[j + 1] = a[i] * 10 + 9;
				count++;
				if (count == k) { std::cout << ima[j+1] << std::endl; flug = false; break; }
				j += 2;
			}
			else {
				ima[j] = a[i] * 10 + a[i] % 10 - 1;
				count++;
				if (count == k) { std::cout << ima[j] << std::endl; flug = false; break; }
				ima[j + 1] = a[i] * 10 + a[i] % 10;
				count++;
				if (count == k) { std::cout << ima[j+1] << std::endl; flug = false; break; }
				ima[j + 2] = a[i] * 10 + a[i] % 10 + 1;
				count++;
				if (count == k) { std::cout << ima[j+2] << std::endl; flug = false; break; }
				j += 3;
			}
		}
		for (int i = 0; ima[i] > -1&&flug; i++) {
			a[i] = ima[i];
		}

	}
	/*for (int i = j-100; ima[i] > -1; i++) {
		std::cout << ima[i] << std::endl;
	}*/

}


Measured memory_bytes: 1792
#include<iostream>
#include<math.h>
#include<float.h>
#include<cstdio>
#include<vector>
using namespace std;
#define EPS (1e-10)
#define equals(a,b) fabs((a)-(b))<DBL_EPSILON*fmax(1,fmax(fabs(a),fabs(b)))
//点のクラス
class Point{
    public:
        double x,y;
        Point(double x=0,double y=0):x(x),y(y){}

        Point operator + (Point p){return Point(x+p.x,y+p.y);}
        Point operator - (Point p){return Point(x-p.x,y-p.y);}
        Point operator * (double a){return Point(a*x,a*y);}
        Point operator / (double a){return Point(x/a,y/a);}

        double norm(Point p){return p.x*p.x+p.y*p.y;}
        double abs(Point p){return sqrt(norm(p));}    
        bool operator < (const Point &p)const{
            return x!=p.x?x<p.x:y<p.y;
        }
        bool operator == (const Point &p)const{
            return equals(x,p.x)&&equals(y,p.y);
        }
};
typedef Point Vector;
double norm(Vector v){return v.x*v.x+v.y*v.y;} 
double abs(Vector v){return sqrt(norm(v));}    
//円
class Circle{
    public:
        Point c;
        double r;
        Circle(Point c=Point(),double r=0.0):c(c),r(r){}
};
double arg(Vector p){ return atan2(p.y,p.x); }
Vector polar(double a,double r){ return Point(cos(r)*a,sin(r)*a);}
pair<Point,Point> getCrossPoints(Circle c1,Circle c2){
    //assert(intersect(c1,c2));
    double d=abs(c1.c-c2.c);
    double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
    double t=arg(c2.c-c1.c);
    return make_pair(c1.c+polar(c1.r,t+a),c1.c+polar(c1.r,t-a));
}
int main(){ 
    Circle c1,c2;
    cin>>c1.c.x>>c1.c.y>>c1.r;
    cin>>c2.c.x>>c2.c.y>>c2.r;
    pair<Point,Point> pp;
    pp=getCrossPoints(c1,c2);
    if(pp.first.x>pp.second.x)
        swap(pp.first,pp.second);
    else if(pp.first.x==pp.second.x&&pp.first.y>pp.second.y)
        swap(pp.first,pp.second);

    printf("%.10f %.10f %.10f %.10f\n",pp.first.x,pp.first.y,pp.second.x,pp.second.y);    
    return 0;
}



Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define ll long long int
#define vi vector<ll>
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define iiii pair<ii,ii>
#define pb push_back
#define fi first
#define se second
using namespace std;
int mm[10][10];
int tem[10][10];
int a[(int)105];
int datar(){
	for(int i  = 0;i<3;i++){
		int ga = 0;
		for(int j = 0;j<3;j++){
			if(!tem[i][j]) ga = 1;
		}
		if(!ga) return 1;
	}
	for(int j = 0;j<3;j++){
		int ga = 0;
		for(int i = 0;i<3;i++) if(!tem[i][j]) ga = 1;
		if(!ga) return 1;
	}
	int ga = 0;
	for(int i = 0;i<3;i++){
		if(!tem[i][i]) ga = 1;
	}
	if(!ga) return 1;
	if(tem[0][2] && tem[1][1] && tem[2][0]) return 1;
	return 0;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	for(int i = 0;i<3;i++) for(int j = 0;j<3;j++) cin>>mm[i][j];
	int n;
	cin>>n;
	for(int i = 0;i<n;i++){
		int b;cin>>b;
		a[b] = 1;
	}
	for(int i = 0;i<3;i++) for(int j = 0;j<3;j++) if(a[mm[i][j]]) tem[i][j] = 1;
//	for(int i = 0;i<3;i++) for(int j = 0;j<3;j++) cout<<tem[i][j]<<" ";cout<<"\n";
	if(datar()) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

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

using namespace std;

int main()
{
	int X,Y;
	scanf("%d%d",&X,&Y);
	for(int i = 0;i <= X; ++ i)
		if(i * 2 + (X - i) * 4 == Y)
		{
			printf("Yes\n");
			return 0;
		}
	printf("No\n");
}

Measured memory_bytes: 3764
import itertools
import math

N = int(input())

q = []
for i in range(N):
    q.append(list(map(int, input().split())))

a = []

for i in range(1,N+1):
    a += [i]

b = []

for v in itertools.permutations(a, N):
    b.append(list(v))

ancerL = []

for i in range(len(b)):
    ancer = 0
    for j in range(N-1):
        
        combined1 = [x - y for (x, y) in zip(q[b[i][j+1]-1], q[b[i][j]-1])]
        
        ancer += math.sqrt(combined1[0]**2 + combined1[1]**2)
       
    ancerL.append(ancer)
    
print(sum(ancerL) / len(ancerL))


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

typedef long long int ll;

int main()
{
	string t;
	cin>>t;
	for(int i=0;i<t.size();i++)
	{
		if(t[i]=='?')
			t[i]='D';
	}
	cout<<t<<endl;
}



Measured memory_bytes: 3732
#include <algorithm>
#include <iostream>
#include <vector>

namespace multiset
{

class multiset
{
  private:
    std::vector<int> tree;
    int MSB;

    void add(int i, int x)
    {
        for (; i < tree.size(); i += i & -i) {
            tree[i] += x;
        }
    }

    int sum(int i)
    {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }

    int bisect(int w)
    {
        int i = 0;
        for (int k = MSB; k > 0; k /= 2) {
            if (i + k < tree.size() && tree[i + k] < w) {
                w -= tree[i + k];
                i += k;
            }
        }
        return i + 1;
    }

    int get_MSB(int N)
    {
        int i = 1;
        while (i < N) {
            i *= 2;
        }
        return i / 2;
    }

  public:
    multiset(int N) : tree(N + 1), MSB(get_MSB(N)) {}
    void insert(int x) { add(x, 1); }
    void erase(int x) { add(x, -1); }
    int lower_bound(int x)
    {
        int s = sum(x);
        return (s == 0) ? 0 : bisect(s);
    }

    size_t size() { return sum(tree.size() - 1); }
};

} // namespace multiset

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

    std::vector<int> A(N);
    for (auto &&a : A) {
        std::cin >> a;
    }

    std::vector<int> B = A;

    std::sort(begin(B), end(B));
    B.erase(std::unique(begin(B), end(B)), end(B));

    auto f = [&](int val) -> int {
        return std::lower_bound(begin(B), end(B), val) - begin(B) + 1;
    };

    multiset::multiset ms(B.size());
    for (auto a : A) {
        auto i = ms.lower_bound(f(a) - 1);
        if (i != 0) {
            ms.erase(i);
        }
        ms.insert(f(a));
    }

    std::cout << ms.size() << '\n';
}


Measured memory_bytes: 1408
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#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>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

int main(int argc, char **argv) {
	int a, b, c;
	cin >> a >> b >> c;
	cout << min(a + b, min(a + c, b + c)) << endl;
	return 0;
}


Measured memory_bytes: 256