akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int N,T,L,B;
    cout<<fixed;
    cout.precision(6);
    while(cin>>N>>T>>L>>B,N){
        double dp[T+1][N+1];
        fill(dp[0],dp[T+1],0);
        dp[0][0]=1.0;
        bool isLose[N+1];
        fill(isLose,isLose+N+1,false);
        for(int i=0;i<L;i++){
            int l;
            cin>>l;
            isLose[l]=true;
        }
        bool isBack[N+1];
        fill(isBack,isBack+N+1,false);
        for(int i=0;i<B;i++){
            int b;
            cin>>b;
            isBack[b]=true;
        }
        for(int t=0;t<T;t++){
            for(int i=0;i<N;i++){
                for(int d=1;d<=6;d++){
                    int ni=i+d;
                    if(ni>N)ni=2*N-ni;
                    if(isBack[ni]){
                        dp[t+1][0]+=dp[t][i]/6;
                    }else if(isLose[ni]){
                        if(t+2<=T)dp[t+2][ni]+=dp[t][i]/6;
                    }else{
                        dp[t+1][ni]+=dp[t][i]/6;
                    }
                }
            }
            dp[t+1][N]+=dp[t][N];
        }
        cout<<dp[T][N]<<endl;
    }

    return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
map<ll,ll>dp;
ll solve(ll x)
{
    if(dp[x])
         return dp[x];
    else
         return dp[x]=((solve(x/2)%mod+solve((x-1)/2)%mod+solve((x-2)/2))%mod)%mod;
}
int main()
{
    dp[0]=1;
    dp[1]=2;
    ll n;
    cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}

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

int main(){
	int N,Q;
	cin>>N>>Q;
	int t[N];
	for(int i=0;i<N-1;++i)t[i]=0;
	string S;
	cin>>S;
	for(int i=0;i<N;++i){
		if((S[i]=='A') && (S[i+1]=='C')){
			t[i+1]=t[i]+1;
		}
		else{
			t[i+1]=t[i];
		}
	}
	int l[Q],r[Q];
	for(int i=0;i<Q;++i)cin>>l[i]>>r[i];
	for(int i=0;i<Q;++i){
		cout<<t[r[i]-1]-t[l[i]-1]<<endl;
	}
}


Measured memory_bytes: 2240
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    cout << N / 2 + (N % 2) << endl;
    return 0;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll mod = 1e9+7;
ll n, k;

ll func(int now, int parent, const vii &tree) {
  ll res = 1;
  ll can_use;
  if(parent == -1) {
    res *= k;
    can_use = k-1;
  }
  else can_use = k-2;
  for(int child : tree[now]) {
    if(child == parent) continue;
    res = res * can_use % mod;
    res = res * func(child, now, tree) % mod;
    can_use--;
  }
  return res;
}

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

  cin >> n >> k;
  vii tree(n);
  rep(i,n-1) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  ll ans = func(0, -1, tree);
  cout << ans << endl;
}

Measured memory_bytes: 11648
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int cnt=0;
    int sum=0;
    for(int i=1;i<10000000;i++){
        sum+=a;
        if(i%7==0){
            sum+=b;
        }
        cnt++;
        if(sum>=c){
            break;
        }
    }
    cout << cnt << endl;
}


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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define int long long
typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int N = 2e6 + 5;

long long n, a[N], sum;

map<int, int> mymap;

int ok = 0;

signed main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= 2;
        if(a[i] == 1)
            ok = 1;
    }
    if(ok == 0) {
            cout << "second";
            //cout << "first";
    }
    else
        cout << "first";
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  double ans,a,b,c,n;
  cin>>n;
  vector<vector<double>> vec(n,vector<double>(2));
  for(int i=0; i<n; i++ ){
    cin>>vec.at(i).at(0);
    cin>>vec.at(i).at(1);
  }
  ans=0;
  for(int i=0; i<n-1; i++){
    for(int j=i+1; j<n; j++){
      a=vec.at(i).at(0)-vec.at(j).at(0);
      b=vec.at(i).at(1)-vec.at(j).at(1);
      a=a*a;
      b=b*b;
      ans=ans+sqrt(a+b);
    }
  }
  ans=ans*2/n;
  cout << fixed << setprecision(8);
  cout<<ans;
}

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

int a[301][301];
bool d[301][301];
int n;
long long ans=0;

void search(){
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(k!=i&&k!=j&&i!=j){
          if(a[i][j]>a[i][k]+a[k][j]){
            ans = -1;
            return;
          }
          if(a[i][j]==a[i][k]+a[k][j])
            d[i][j]=true;
        }
      }
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<i;j++)
      if(!d[i][j])ans+=a[i][j];
  }
}






int main(){

  cin>>n;

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>a[i][j];
    }
  }

  search();

  cout<<ans<<endl;

  return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    int a, b;
    cin >> a >> b;
    int x = 0, y = 0;
    for (int i = 0; i < a; ++i) {
        x = x * 10 + b;
    }
    for (int i = 0; i < b; ++i) {
        y = y * 10 + a;
    }
    cout << max(x, y);
    
    return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  int f=0;
  
  for(int i=a;i<b+1;i++){
    if( i/10000 == i%10 && (i/1000)%10 == (i/10)%10)
      f +=1;
    else
      f =f;
  }

  	cout << f << endl;

}


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

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



Measured memory_bytes: 256
fun main(args: Array<String>) {
    Program().solve()
}

class Program {
    fun solve() {
        val sc = MyScanner()
        val a = sc.nextInt();
        val b = sc.nextInt()
        val ans = Math.max(a * b, Math.max(a - b, a + b))
        println(ans)
    }
}


class MyScanner() {
    private var index = 0
    private var line = listOf<String>()

    fun next(): String {
        while (line.size <= index) {
            line = readLine()!!.split(' ')
            index = 0
        }
        return line[index++]
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextDouble() = next().toDouble()
    fun nextCharArray() = next().toCharArray()
    fun nextChar() = next()[0]
}

Measured memory_bytes: 38240
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};
 
int main(){
  int n,m;
  cin>>n>>m;
  vector<string> a(n),b(m);
  REP(i,n){
    cin>>a[i];
  }
  REP(i,m){
    cin>>b[i];
  }
  
  bool flag=true;
  bool found=false;
  REP(i,n-m+1){
    REP(j,n-m+1){
      REP(k,m){
        REP(l,m){
          if(a[i+k][j+l]==b[k][l]){
            continue;
          }else{
            flag=false;
          }
        }
      }
      if(flag){
        found=true;
      }else{
        flag=true;
      }
    }
  }
  
  if(found){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define hii cout << "hii" << endl
#define int long long
#define endl '\n'
#define all(s) s.begin(), s.end()
 
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE

const int N = 5e5 + 5;
const int MAX = 250000 + 5;
const int M = 1e6 + 5;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int INF = 1e18 + 8;
const int LG = 21;

int arr[N];
int DP[M][2][2];

int f(int idx, bool f1, bool f2)
{
	if(idx == 0)
	{
		return (f1 & f2);
	}
	int & ret = DP[idx][f1][f2];
	if(~ret) return ret;
	int ans1 = 8 * f(idx - 1, f1, f2);
	int ans2 = f(idx - 1, 1, f2);
	int ans3 = f(idx - 1, f1, 1);
	return ret = (ans1 + ans2 + ans3) % mod;
}

void solve()
{
	int n;
	cin >> n;
	memset(DP, -1, sizeof(DP));
	cout << f(n, 0, 0) << endl;
}


 
int32_t main() 
{	
	ios_base:: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	    int t = 1;
	    // cin >> t;
	while(t--)solve();
	return 0;
}

Measured memory_bytes: 112920
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = list2d(N, 10, 0)
for i in range(N):
    A[i] = LIST()
B = list2d(N, 11, 0)
for i in range(N):
    B[i] = LIST()

ans = -INF
# 全時間帯でビット全探索(全0以外)
for S in range(1, 1<<10):
    sm = 0
    for i in range(N):
        cnt = 0
        for j in range(10):
            if S & 1<<j and A[i][j]:
                cnt += 1
        sm += B[i][cnt]
    ans = max(ans, sm)
print(ans)


Measured memory_bytes: 43628
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<string>


using namespace std;

int main(void)
{
	int n, sum, max, flag, ans;
	 sum = 0;
	 max = 0;
	 flag = 100;
	cin >> n;
	vector<int> num(n);
	vector<int> sumt(n+2);
	int i,t;
	for (i = 0; i < n; i++)
	{
		cin >> num[i];
	}
	sort(num.begin(), num.end());
	for (i = 0; i < n; i++)
	{
		max = max + num[i];
	}
	if (max % 10 != 0)
	{
		flag = 1;
		ans = max;
	}
	if (max % 10 == 0)
	{
		for (t =1;t<=n;t++)
		{
			if (t == 1)
			{
				sumt[t] = max;
			}
			for (i = 0; i < n-t+1; i++)
			{
				if ((sumt[t] - num[i] )% 10 != 0)
				{
					ans = sumt[t]-num[i];
					flag = 1;
					break;
				}
				
			}
			sumt[t + 1] = sumt[t] - num[t-1];
			if (flag == 1)
			{
				break;
			}
		}
	}
	if (flag == 1)
	{
		cout << ans<< endl;
	}
	else
	{
		cout << 0 << endl;
	}
	return 0;
}


Measured memory_bytes: 256
from sys import stdin
import itertools
#stdin = open("input.txt")

if __name__ == "__main__":
  N = int(stdin.readline())
  P = tuple([int(i) for i in stdin.readline().split()])
  Q = tuple([int(i) for i in stdin.readline().split()])
  # print(P, Q)

  for i, perm in enumerate(sorted(list(itertools.permutations(range(1, 1+N))))):
    # print(perm)
    if perm == P:
      indexP = i
    if perm == Q:
      indexQ = i

  print(abs(indexP-indexQ))

Measured memory_bytes: 46320
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] L = new int[N+1];
        L[0] = 0;
        for(int i = 1; i < N+1; i++) {
            L[i] = sc.nextInt();
        }
        sc.close();

        System.out.println(Bounding(N+1, X, L, 0, 0));
    }
    public static int Bounding(int N, int X, int[] L, int index, int sum) {
        if (N <= index) {
            return 0;
        }
        if (sum + L[index] <= X) {
            return 1 + Bounding(N, X, L, index + 1, sum + L[index]);
        }
        return 0;
    }
}


Measured memory_bytes: 22868
import java.util.Scanner;
  
class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int number = sc.nextInt();
    boolean[][] cards = new boolean[4][13];
  
    for(int x = 0; x < number; x++){
      String pattern = sc.next();
      int rank = sc.nextInt();
      if(pattern.equals("S")){
        cards[0][rank-1] = true;
      }else if(pattern.equals("H")){
        cards[1][rank-1] = true;
      }else if(pattern.equals("C")){
        cards[2][rank-1] = true;
      }else{
        cards[3][rank-1] = true;
      }
    }
  
    for(int y = 0; y < 13; y++){
      if(cards[0][y]){
      }else{
        System.out.println("S "+(y+1));
      }
    }
    for(int y = 0; y < 13; y++){
      if(cards[1][y]){
      }else{
        System.out.println("H "+(y+1));
      }
    }
  	for(int y = 0; y < 13; y++){
      if(cards[2][y]){
      }else{
        System.out.println("C "+(y+1));
      }
    }
    for(int y = 0; y < 13; y++){
      if(cards[3][y]){
      }else{
        System.out.println("D "+(y+1));
      }
    }
  }
}


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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; ++i) cin >> P[i];
    vector<int> Q(N);
    for (int i = 0; i < N; ++i) cin >> Q[i];
    vector<int> V(N);
    for (int i = 0; i < N; ++i) V[i] = i+1;
    int count = 0;
    int a = 0;
    int b = 0;
    do {
        ++count;
        if (V == P) a = count;
        if (V == Q) b = count;
    } while (next_permutation(V.begin(), V.end()));
    cout << abs(a - b) << endl;
    return 0;
}

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

string rot(string s, int r) {
    string res(s.size(), '0');
    REP(i, s.size()) {
        res[(i + r)%s.size()] = s[i];
    }
    return res;
}

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    REP(i, s.size()) {
        if(rot(s, i) == t) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}



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

maxlength = 0
length = 0
for i in range(n-1):
    if h[i]>=h[i+1]:
        length += 1
    else:
        if maxlength < length:
            maxlength = length
        length = 0
if maxlength < length:
    maxlength = length
print(maxlength)

Measured memory_bytes: 14224
package main

import (
	"fmt"
	//	"os"
	"strconv"
)

const (
	LARGE_NUM = 1000000007
)

func stringToint(s string) int {
	i, _ := strconv.ParseInt(s, 10, 64)
	return int(i)
}

type division struct {
	value int
	num   int
}

func getDivisor(origNum int) {
	num := origNum
	for i := 2; i <= origNum; i++ {
		for num%i == 0 {
			if _, ok := divisor[i]; !ok {
				divisor[i] = 0
			}
			divisor[i]++
			num = num / i
		}
	}
}

var divisor map[int]int

func main() {
	var N int
	fmt.Scan(&N)
	//num := stringToint(os.Args[1])
	divisor = make(map[int]int)
	/*
		for i := 2; i <= originNum/2; i++ {
			for num%i == 0 {
				if _, ok := divisor[i]; !ok {
					divisor[i] = 0
				}
				divisor[i]++
				num = num / i
			}
		}
	*/

	nums := make([]int, 0, 0)
	for i := 1; i <= N; i++ {
		nums = append(nums, i)
	}

	for _, num := range nums {
		getDivisor(num)
	}

	remain := 1
	for _, num := range divisor {
		remain = (remain * (num + 1)) % LARGE_NUM
	}
	fmt.Println(remain)
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(n);++i)
#define ALL(v)     (v).begin(),(v).end()
#define debug(x)   cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF=1e9;
constexpr double EPS=1e-9;
constexpr int    MOD=1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

template<typename Type>
struct Dinic{
	struct Edge{				//Edge:=(辺の情報を表す構造体).
		int to;//to:=(行先). 
		Type cap;//cap:=(容量).
		int rev;//rev:=(逆辺).
	};
	
	vector<vector<Edge> > g;	//g[i]:=(ノードiの隣接リスト).
	vi level;					//level[i]:=(sからiまでの距離).
	vi iter;					//iter[i]:=(ノードiの隣接ノードをどこまで調べたか).
	Type inf;
	
	Dinic(int vn):g(vn),level(vn),iter(vn){//constructor.
		if(typeid(Type)==typeid(int)) inf=1e9;
		else if(typeid(Type)==typeid(long long)) inf=1e18;
	}
	
	void add_egde(int from,int to,Type cap){//fromからtoへ向かう容量capの辺をグラフに追加する.
		g[from].push_back((Edge){to,cap,(int)g[to].size()});
		g[to].push_back((Edge){from,0,(int)g[from].size()-1});
	}
	void bfs(int s){//sからの最短距離を計算する.
		fill(ALL(level),-1);
		level[s]=0;
		queue<int> que;
		que.push(s);
		while(!que.empty()){
			int v=que.front();
			que.pop();
			REP(i,g[v].size()){
				Edge &e=g[v][i];
				if(e.cap>0 and level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}	
	}
	Type dfs(int v,int t,Type f){//増加パスを探す.
		if(v==t) return f;
		for(int &i=iter[v];i<g[v].size();++i){
			Edge &e=g[v][i];
			if(e.cap>0 and level[v]<level[e.to]){
				Type d=dfs(e.to,t,min(f,e.cap));
				if(d>0){
					e.cap-=d;
					g[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
	Type max_flow(int s,int t){//sからtへの最大流を求める. O(|E|*(|V|^2)).
		Type flow=0;
		while(1){
			bfs(s);
			if(level[t]<0) return flow;
			fill(ALL(iter),0);
			Type f;
			while((f=dfs(s,t,inf))>0) flow+=f;
		}
	}
};

int main(){//Refering other editorials.
	int h,w;
	cin>>h>>w;
	
	vector<string> a(h);
	REP(i,h) cin>>a[i];
	
	int sy,sx,ty,tx;
	REP(y,h)REP(x,w){
		if(a[y][x]=='S') sy=y, sx=x;
		else if(a[y][x]=='T') ty=y, tx=x;
	}
	if(sy==ty or sx==tx){//sからtへ一跳び!
		cout<<-1<<endl;
		return 0;
	}
	
	Dinic<int> ob(h+w+2);//(s,t):=(h+w,h+w+1).
	ob.add_egde(h+w,sy,INF);
	ob.add_egde(h+w,h+sx,INF);
	ob.add_egde(ty,h+w+1,INF);
	ob.add_egde(h+tx,h+w+1,INF);
	REP(y,h)REP(x,w){
		if(a[y][x]=='o'){
			ob.add_egde(y,h+x,1);
			ob.add_egde(h+x,y,1);
		}
	}
	
	cout<<ob.max_flow(h+w,h+w+1)<<endl;
	return 0;
}

Measured memory_bytes: 4196
#include <stdio.h>
#include <stdlib.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_N 100

int n,time,head,tail;
int *queue;
int *dist;
int *color;
int **matrix;

void enqueue(int);
int dequeue(void);
void bfs(void);

int main(){
  int i,j,u,k,v;

  scanf("%d",&n);

  queue = malloc(MAX_N * sizeof(int));
  color = malloc(n * sizeof(int));
  dist = malloc(n * sizeof(int));

  matrix = malloc(n * sizeof(int *));
  for(i = 0 ; i < n ; i++){
    matrix[i] = malloc(n * sizeof(int));
 }
 for(i = 0 ; i < n ; i++){
   dist[i] = -1;
 }
 for(i = 0 ; i < n ; i++){
   for(j = 0 ; j < n ; j++){
     matrix[i][j] = 0;
   }
 }

 for(i = 0 ; i < n ; i++){
    scanf("%d",&u); u--;
    scanf("%d",&k);
    for(j = 0 ; j < k ; j++){
      scanf("%d",&v); v--;
      matrix[u][v] = 1;
    }
  }

  bfs();
  for(i = 0 ; i < n ; i++){
    printf("%d %d\n",i+1,dist[i]);
  }

  for(i = 0 ; i < n ; i++){
    free(matrix[i]);
  }
  free(matrix);
  free(queue);
  free(dist);
  free(color);
  return 0;
}

void bfs(){
  int u,i;

  head = tail = 0;
  color[0] = GRAY;
  dist[0] = 0;
  enqueue(0);

  while(head != tail){
    u = dequeue();
    for(i = 0 ; i < n ; i++){
      if(matrix[u][i] == 1 && color[i] == WHITE){
        color[i] = GRAY;
        dist[i] = dist[u] + 1;
        enqueue(i);
      }
    }
    color[u] = BLACK;
  }
}

void enqueue(int q){
  queue[tail] = q;
  if(++tail == n+1) tail = 0;
}

int dequeue(){
  int v = queue[head];
  if(++head == n+1) head = 0;
  return v;
}

Measured memory_bytes: 636
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
    v=q.pop(0)
    coor=m[''.join(v)][0]
    x=coor%X
    y=coor//X
    depth=m[''.join(v)][1]
    nextstr=''.join(v)
    if 0<x:
        v[coor],v[coor-1]=v[coor-1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'R']
        v[coor],v[coor-1]=v[coor-1],v[coor]
    if x<X-1:
        v[coor],v[coor+1]=v[coor+1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'L']
        v[coor],v[coor+1]=v[coor+1],v[coor]
    if 0<y:
        v[coor],v[coor-X]=v[coor-X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'D']
        v[coor],v[coor-X]=v[coor-X],v[coor]
    if y<Y-1:
        v[coor],v[coor+X]=v[coor+X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'U']
        v[coor],v[coor+X]=v[coor+X],v[coor]

try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    pass

Measured memory_bytes: 16236
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    int a, b;
    cin >> a >> b;
    int tmp = 1;
    int ans = 0;
    while (tmp < b) {
        tmp += a - 1;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
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; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

int main(){
    int N,K; cin>>N>>K;
    vector<int> a(N);
    rep(i,N)cin>>a[i];
    vector<bool> dp(K+10,false);
    rep1(k,K){
        auto iter = upper_bound(a.begin(),a.end(),k) - a.begin();
        rep(n,(ll)iter){
            dp[k] =  dp[k] || !dp[k-a[n]];
        }
    }
    if(dp[K])cout<<"First"<<endl;
    else cout<<"Second"<<endl;
}

Measured memory_bytes: 3600
package main
 
import (
	"fmt"
)

func main() {
  var n, k, x, y int
  fmt.Scanf("%d", &n)
  fmt.Scanf("%d", &k)
  fmt.Scanf("%d", &x)
  fmt.Scanf("%d", &y)
  
  ans := 0
  for i := 1; i <= n; i++{
    if i <= k{
      ans += x
    }
    if i > k{
      ans += y
    }
  }
  
  fmt.Printf("%d", ans)
}

Measured memory_bytes: 1832
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {
			var inputArray = retreiveLongArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long X = inputArray[0];


			//B < 0を想定
			long maxA = 100;

			for (long a = 0; a <= maxA; a++) {

				var target = X - a * a * a * a * a;//B^5が満たすべき数(正負反転すみ) 
				if(target < 0) {
					break;
				}
				//B=0
				if (target == 0) {
					Console.WriteLine($"{a} {0}");
					return;
				}
				//2分探索で条件を満たすBが存在するか探す
				long max = 100;
				long min = 1;
				long mid = (max + min) / 2;
				while (true) {
					mid = (max + min) / 2;

					var result = target - mid * mid * mid * mid * mid;
					if (result == 0) {
						Console.WriteLine($"{a} {-mid}");
						return;
					}

					if(result > 0) {//midが小さすぎる
						min = mid;
					}
					if (result < 0) {//midがおおきすぎる
						max = mid;
					}

					if (min+1 == max) {//minとmaxが1違いなのに見つからないときはあきらめる
						var result2 = target - min * min * min * min * min;
						if (result2 == 0) {
							Console.WriteLine($"{a} {-min}");
							return;
						}
						var result3 = target - max * max * max * max * max;
						if (result3 == 0) {
							Console.WriteLine($"{a} {-max}");
							return;
						}
						break;
					}
				}
			}
			// B >0を想定 aはどこまでも大きい可能性ある
			///////////////////////////////////////////////////////////////////////
			for (long a = 0; a <= 100000000000000; a++) {

				var target = a * a * a * a * a-X;//B^5が満たすべき数
				if (target < 0) {
					continue;
				}
				//B=0
				if (target == 0) {
					Console.WriteLine($"{a} {0}");
					return;
				}
				//2分探索で条件を満たすBが存在するか探す
				long max = a;
				long min = 1;
				long mid = (max + min) / 2;
				while (true) {
					mid = (max + min) / 2;

					var result = target - mid * mid * mid * mid * mid;
					if (result == 0) {
						Console.WriteLine($"{a} {mid}");
						return;
					}

					if (result > 0) {//midが小さすぎる
						min = mid;
					}
					if (result < 0) {//midがおおきすぎる
						max = mid;
					}

					if (min + 1 == max) {//minとmaxが1違いなのに見つからないときはあきらめる
						var result2 = target - min * min * min * min * min;
						if (result2 == 0) {
							Console.WriteLine($"{a} {min}");
							return;
						}
						var result3 = target - max * max * max * max * max;
						if (result3 == 0) {
							Console.WriteLine($"{a} {max}");
							return;
						}
						break;
					}
				}
			}

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}


Measured memory_bytes: 28184
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 2000000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<long long, long long> pl;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool debug=false;
/*---------------------------------------------------*/
struct edge{int to;int cost;};
vector<edge> g[100005];
ll d_k[100005];
ll d_x[100005];

void dijkstra_k(int s){
  priority_queue<pi,vector<pi> ,greater<pi> >que;
  fill(d_k,d_k+100005,LINF);
  d_k[s]=0;
  que.push(mp(0,s));
  while(!que.empty()){
    pi p=que.top();que.pop();
    int v=p.second;    if(d_k[v]<p.first)continue;
    for(int i=0;i<int(g[v].size());i++){
      edge e=g[v][i];
      if(d_k[e.to]>d_k[v]+e.cost){
	d_k[e.to]=d_k[v]+e.cost;
	que.push(mp(d_k[e.to],e.to));
      }
    }
  }
}
/*
void dijkstra_x(int s){
  priority_queue<pi,vector<pi> ,greater<pi> >que;
  fill(d_x,d_x+100000,LINF);
  d_x[s]=0;
  que.push(mp(0,s));
  while(!que.empty()){
    pi p=que.top();que.pop();
    int v=p.second;
    if(d_x[v]<p.first)continue;
    for(int i=0;i<int(g[v].size());i++){
      edge e=g[v][i];
      if(d_x[e.to]>d_x[v]+e.cost){
	d_x[e.to]=d_x[v]+e.cost;
	que.push(mp(d_x[e.to],e.to));
      }
    }
  }
}
*/

int main(){
  int n,a,b,c;
  int q,x,k,y;
  edge tmp;
  cin>>n;
  rep(i,n-1){
    cin>>a>>b>>c;
    tmp.to=b;tmp.cost=c;
    g[a].pb(tmp);
    tmp.to=a;tmp.cost=c;
    g[b].pb(tmp);
  }
  
  cin>>q>>k;
  dijkstra_k(k);
  
  rep(i,q){
    cin>>x>>y;
    cout<<d_k[x]+d_k[y]<<endl;
  }
  
  
  return 0;
}


Measured memory_bytes: 8820
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace A
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var s = Console.ReadLine();
            var result = true;
            for (var i = 1; i < s.Length; i++)
            {
                if (s[i - 1] == s[i])
                {
                    result = false;
                    break;
                }
            }
            Console.WriteLine(result ? "Good" : "Bad");
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n,k;
  cin>>n>>k;
  vi A(200020,0);
  rep(i,n){
    int a;
    cin>>a;
    a--;
    A[a]++;
  }
  int cnt = 0;
  rep(i,200020){
    if(A[i])cnt++;
  }
  sort(rng(A));
  int ans = 0;
  rep(i,200020){
    if(cnt<=k) break;
    if(A[i]){
      cnt--;
      ans+=A[i];
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <random>

using ll = long long;

//vector
template <class T>
using vec = std::vector<T>;

//namespace std
//{
//    template<>
//    class hash<Key>
//    {
//    public:
//        size_t operator() (const Key& key) const
//        {
//            size_t seed = 0;
//            auto i_hash = hash<int>()(key.i_th);
//            auto w_hash = hash<int>()(key.W);
//
//            seed ^= i_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
//            seed ^= w_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
//
//            return seed;
//        }
//    };
//}


void solve()
{
    using namespace std;
    int n;
    cin >> n;

    if (n < 1000)
        cout << "ABC" << endl;
    else
        cout << "ABD"<< endl;


}

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

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

int main() {
  int N;
  cin>>N;
  int dt=0,dx=0,dy=0;
  bool f=true;
  for (int i=0; i<N; i++) {
    int t,x,y;
    cin>>t>>x>>y;
    dt=abs(t-dt),dx=abs(x-dx),dy=abs(y-dy);
    if (dt<dx+dy || (dx+dy-dt)%2!=0) {
      f=false;
    }
  }
  cout<<(f?"Yes":"No")<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
char ss[200005];
int n,cc;
long long ans;
int main() {
	scanf("%s",&ss[1]);
	n = strlen(ss+1);
	for(int i=n;i>=1;i--){
		if(ss[i]=='W') ++cc;
		else ans += cc;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int f(int a)
{
	int i,s=0;
	for(i=1;i<=a;i++)
		s+=i;
	return s;
}
int main()
{
	int a,b,snow;
	scanf("%d %d",&a,&b);
	snow=f(b-a)-b;
	printf("%d",snow);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
const int N  = 2e3+5;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+7;
typedef pair<int ,int >pii;
struct Edge{
  int v,next;
}edge[N<<1];
int head[N],tot,n,k;
void add(int u,int v){
  edge[tot].v=v;
  edge[tot].next=head[u];
  head[u]=tot++;
}
bool vis[N];
int d[N];
void bfs(int s,int f){
  queue<int>q;
  while(!q.empty())q.pop();
  d[s]=0;vis[s]=true;
  q.push(s);
  while(!q.empty()){
     int u=q.front();
     q.pop();
     for(int i = head[u];~i;i=edge[i].next){
      int v=edge[i].v;
      if(vis[v]||v==f)continue;
      d[v]=d[u]+1;
      vis[v]=true;
      q.push(v);
     }
  }
}
int solveodd(int u,int v){
   memset(d,INF,sizeof(d));
   memset(vis,0,sizeof(vis));
   bfs(u,v);bfs(v,u);
   int ret=0;
   for(int i=1;i<=n;++i)
    if(d[i]>k)++ret;
   return ret;
}
int solveeven(int u){
   memset(d,INF,sizeof(d));
   memset(vis,0,sizeof(vis));
   bfs(u,0);
   int ret=0;
   for(int i=1;i<=n;++i)
    if(d[i]>k)++ret;
   return ret;
}
int main(){
  scanf("%d%d",&n,&k);
  memset(head,-1,sizeof(head));
  for(int i=1;i<=n-1;++i){
    int u,v;
    scanf("%d%d",&u,&v);
    add(u,v);add(v,u);
  }
  int ret=INF;
  if(k&1){
    k>>=1;
    for(int i=0;i<tot;i+=2)
      ret=min(ret,solveodd(edge[i].v,edge[i+1].v));
  }
  else{
    k>>=1;
    for(int i=1;i<=n;++i)
      ret=min(ret,solveeven(i));
  }
  printf("%d\n",ret);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int a, s, h, m;

		cin >> a;

	h = a / 3600;

	m = a % 3600 / 60;

	s = a % 3600 % 60;
	
	cout << h << ':' << m << ':' << s << endl;
	

	}

Measured memory_bytes: 3092
using System;

class Program
{
    static string S;
    static int n; // Sの文字数

    static void Main()
    {
        S = Console.ReadLine();
        n = S.Length;

        for (int i = 0; i < n - 8; i++)
            Console.Write(S[i]);
        Console.WriteLine();
    }
}

Measured memory_bytes: 11092
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int x;
    cin>>x;
    if(1<=x<=9)
    {

      if(x==7 or x==5 or x==3 )
      {
          cout<<"YES";
      }
      else
      {
          cout<<"NO";
      }
    }


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF (1LL<<57)
#define MV 200001
#define LMV 21
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define emp emplace
#define whoami(x) cerr<<#x<<" "<<x<<"\n";
#define mp make_pair
#define ins insert
#define sz size

void FLASH() {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
void SETF() {cout.ios_base::setf(ios_base::fixed);}
void UNSETF() {cout.ios_base::unsetf(ios_base::fixed);}

typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<PII, int> PPII;
typedef pair<PLL, ll> PPLL;
typedef map<int, int> MII;

struct h_llint {
  static uint64_t splitmix64(uint64_t x) {    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

struct h_pair{
  size_t operator()(const PLL&x)const{
    return hash<ll>()(((ll)x.ff)^(((ll)x.ss)<<32));
  }
};

typedef map<ll, ll> MLL;
typedef map<PII, int> MPII;
typedef map<PLL, ll> MPLL;
typedef set<int> SI;
typedef set<ll> SL;
typedef unordered_map<ll, int, h_llint> UMLI;
typedef unordered_map<ll, ll, h_llint> UMLL;
typedef unordered_map<PLL, int, h_pair> UMPI;
typedef unordered_map<PLL, ll, h_pair> UMPL;

int ar[MV];
ll arr[MV];
int BIT[MV];

class fentree
{
	public: void update(int i, int n);
			int query(int i);
};

void fentree::update(int i, int n)
{
	for( ;i<=n;i+=(i & (-i)))
	BIT[i]++;	
	return;
}

int fentree::query(int i)
{
	int ans = 0;
	for( ;i>0;i-=(i & (-i)))
	ans += BIT[i];
	return ans;	
}

void solve(int T)
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>ar[i];
	fentree D;
	int res = 0;
	for(int i=1;i<=n;i++)
	{
		D.update(ar[i], n);
		if((D.query(n) - D.query(ar[i]-1)) == i)
		res++;
	}	
	cout<<res<<"\n";
	return;
}

int main(void)
{
	FLASH();
	int T;
	T = 1;

// #ifndef ONLINE_JUDGE
// 	time_t time_t1, time_t2;
// 	time_t1 = clock();
// #endif

	while(T--)
	solve(T);

// #ifndef ONLINE_JUDGE
// 	time_t2 = clock();
// 	SETF();
// 	cout<<"Time taken: "<<setprecision(7)<<(time_t2 - time_t1)/(double)CLOCKS_PER_SEC<<"\n";
// 	UNSETF();
// #endif

	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    string s;
    cin>>s;
    REP(i,s.size()){
        if(s[i]==',')printf(" ");
        else printf("%c",s[i]);
    }
    cout<<endl;
}

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

int mod = pow(10,9) + 7;
int MAXK = 1e5 + 10; 
int MAXN = 1e3 + 10;
int N , K;
vector<int> dp(MAXK, -1);
vector<int> a(MAXN);


int solve(int k){
    if(dp[k] != -1) return dp[k];

    if(k == 0) return dp[k]=0;
    int ans = 0;
    for(int i = 0 ; i < N; i++){
        if(a[i] > k) continue;
        if(solve(k-a[i]) == 0){
            ans = 1;
            break;
        }
    }
    return dp[k] = ans;
}

int main() {
    
    cin >> N >> K;
    
    for(int i = 0 ; i < N ; i++){
        cin >> a[i];
    }

    
    if(solve(K) ) cout << "First";
    else cout << "Second";

    return 0;
}

Measured memory_bytes: 8180
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ---------------------------------------------- "<<endl
#define LL long long
#define uint unsigned int 
#define ULL unsigned long long
#define LDB long double
#define DB double
#define pii pair<int,int>
#define pli pair<LL,int>
#define mp make_pair
#define pb push_back
using namespace std;
inline LL read(){
	LL nm=0; bool fh=true; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return fh?nm:-nm;
}
#define mod 1000000007
namespace  CALC{
	inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
	inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
	inline int mul(LL x,LL y){return x*y%mod;}
	inline void upd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
	inline void dec(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
	inline int qpow(int x,int sq){int res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
}using namespace CALC;
#define M 10000200
int n,m,ans;
int fac[M],ifac[M],iv[M];
inline int C(int N,int K){return (N<K||K<0)?0:mul(fac[N],mul(ifac[N-K],ifac[K]));}
inline int G(int A,int B,int C){return mul(fac[A+B+C],mul(A,iv[A+C]));}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read(),fac[0]=ifac[0]=fac[1]=ifac[1]=iv[1]=1;
	for(int i=2;i<=n;i++) fac[i]=mul(fac[i-1],i),iv[i]=mul(mod-mod/i,iv[mod%i]),ifac[i]=mul(ifac[i-1],iv[i]);
	for(int i=0,w;i<=m;i++) w=mul(C(m,i),G(m-i,0,n-m)),(i&1)?dec(ans,w):upd(ans,w);
	for(int i=2,w;i<=m;i++) for(int j=0;j<i;j++)
		w=mul(C(i-1,j),G(i-1-j,m-i,n-m)),(j&1)?dec(ans,w):upd(ans,w);
	printf("%d\n",ans);
	return 0;
}

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

using namespace std;

template <typename T>
class WeightedUnionFind {
 private:
  std::vector<int> parent;
  std::vector<T> weight;

 public:
  WeightedUnionFind(int n) : parent(n, -1), weight(n, 0) {}

  int root(int x) {
    if (parent[x] < 0) return x;
    int rx = root(parent[x]);
    weight[x] += weight[parent[x]];
    return parent[x] = rx;
  }

  bool is_same(int x, int y) { return root(x) == root(y); }

  int size(int x) { return -parent[root(x)]; }

  T diff(int x, int y) {
    root(x), root(y);
    return weight[y] - weight[x];
  }

  bool unite(int x, int y, T w) {
    int rx = root(x), ry = root(y);
    w += weight[x] - weight[y];
    if (rx == ry) return false;
    if (parent[rx] > parent[ry]) std::swap(rx, ry), w *= -1;
    weight[ry] = w;
    parent[rx] += parent[ry];
    parent[ry] = rx;
    return true;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  WeightedUnionFind<int> uf(N);
  for (int i = 0; i < M; i++) {
    int l, r, d;
    cin >> l >> r >> d;
    l--, r--;
    if (!uf.unite(l, r, d)) {
      if (uf.diff(l, r) != d) {
        cout << "No" << '\n';
        return 0;
      }
    }
  }
  cout << "Yes" << '\n';
  return 0;
}


Measured memory_bytes: 3956
X,K,D = map(int,input().split())
if X < 0:
	X = -X

if X // D >= K:
	print(X-D*K)
else:
	if (K - (X//D)) % 2 == 0:
		print(X-D*(X//D))
	else:
		print(abs(X-D*((X//D)+1)))


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

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int N=1e5+5;

int n,m,a[N],k,p,b[N];

signed main()
{
	n=read();
	m=read();
	k=read();
	p=read();
	for ( int i=1;i<=n;i++ ) 
		a[i]=read();
	sort(a+1,a+n+1); 
	reverse(a+1,a+n+1);
	for ( int i=1;i<=n;i++ ) b[i]=b[i-1]+a[i];
	int ans=p;
	int i;
	for ( i=p+1;i<=n;i++ )
	{
		if(a[i]+m<a[p]) continue;
		int j=i;
		while(a[j]==a[i]&&j<=n) j++;
		j--;
		int sum=(n-i+1)+(p-1); 
		if(sum>=k) ans+=(j-i+1);
		else 
		{
			int alb=b[i-1]-b[p-1];
			int need=(k-((n-i+1)+(p-1)))*m;
			if(abs(alb-(a[i]+m)*(i-p))>=need) ans+=(j-i+1);
		}
		i=j;
	}
	printf("%lld\n",ans);
	return 0;
}

			
			
		
	

Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10**9)
s1 = "maerd"
s2 = "remaerd"
s3 = "esare"
s4 = "resare"

i = input()
s = ''
for c in reversed(i):
    s += c

l = len(s)

i = 0


def dfs(i):
    if i == l:
        print("YES")
        exit()
    if i+5 <= l and s[i:i+5] == s1:
        dfs(i+5)
    elif i+7 <= l and s[i:i+7] == s2:
        dfs(i+7)
    elif i+5 <= l and s[i:i+5] == s3:
        dfs(i+5)
    elif i+6 <= l and s[i:i+6] == s4:
        dfs(i+6)
    else:
        print("NO")
        exit()


dfs(0)


Measured memory_bytes: 18140
fun main(args: Array<String>) {
    val (n, a, b, c, d) = readIntList()
    val s = readString()

    if (c < d) {
        for (i in a - 1..d - 1) {
            if (i + 1 < n && s[i] == '#' && s[i + 1] == '#') {
                println("No")
                return
            }
        }
        println("Yes")
        return
    } else {

        for (i in a - 1..c - 1) {
            if (i + 1 < n && s[i] == '#' && s[i + 1] == '#') {
                println("No")
                return
            }
        }

        var ok = false
        for (i in b - 1..d - 1) {
            if (i + 1 < n && s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
                ok = true
            }
        }
        if (ok) {
            println("Yes")
        } else {
            println("No")
        }
        return
    }
}

// read
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)


Measured memory_bytes: 41316