akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Washoum
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        inputClass in = new inputClass(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        GLongestPath solver = new GLongestPath();
        solver.solve(1, in, out);
        out.close();
    }

    static class GLongestPath {
        static GLongestPath.Node[] graph;
        static boolean[] visited;
        static int ans;

        static int dfs(int a) {
            visited[a] = true;
            int res = 0;
            int tmp;
            boolean d5al = false;
            for (int i : graph[a].edges) {
                d5al = true;
                if (!visited[i]) {
                    tmp = dfs(i);
                    res = Math.max(tmp, res);
                } else {
                    res = Math.max(res, graph[i].nb);
                }
            }
            graph[a].nb = res;
            if (d5al) {
                graph[a].nb++;
            } else {
                graph[a].nb = 0;
            }
            ans = Math.max(graph[a].nb, ans);
            return graph[a].nb;
        }

        public void solve(int testNumber, inputClass sc, PrintWriter out) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            ans = 0;
            graph = new GLongestPath.Node[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new GLongestPath.Node();
                graph[i].edges = new ArrayList<>();
            }

            visited = new boolean[n];
            int x, y;
            for (int i = 0; i < m; i++) {
                x = sc.nextInt() - 1;
                y = sc.nextInt() - 1;
                graph[x].edges.add(y);
            }
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    dfs(i);
                }
            }
            out.println(ans);

        }

        static class Node {
            ArrayList<Integer> edges;
            int nb;

        }

    }

    static class inputClass {
        BufferedReader br;
        StringTokenizer st;

        public inputClass(InputStream in) {

            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 61824
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int N;
void dfs(int cur, string& ans) {
    if (cur == N) {
        cout << ans << endl;
        return;
    }
    char mi = 'a';
    REP(i, cur) chmax(mi, ans[i]);
    for (char c = 'a'; c <= mi + 1; c++) {
        ans[cur] = c;
        dfs(cur + 1, ans);
    }
}

int main(void) {
    cin >> N;

    auto tmp = string(N, 'a');
    dfs(1, tmp);
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(a>b){
        cout<<"a > b"<<endl;
    }
    else if(a==b){
        cout<<"a == b"<<endl;
    }
    else if(a<b){
        cout<<"a < b"<<endl;
    }
}


Measured memory_bytes: 3092
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

int n, v1, v2, sum;
bool ok = 0;

int main()
{
    cin >> n >> v1;
    sum += v1;
    for (int i = 2; i <= n - 1; ++i)
    {
        cin >> v2;
        sum += min(v1, v2);
        v1 = v2;
    }
    sum += v2;
    if (n == 2) sum += v1;
    cout << sum;
	return 0;
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define debug_print(var) cerr << #var << "=" << var <<endl;
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "
#define fi first
#define se second

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  ll b=mod, u=1, v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a, b);
    u-=t*v; swap(u, v);
  }
  u%=mod;
  if(u<0)u+=mod;
  return u;
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

struct UnionFind{
  ll N;
  llvec p;
  llvec cnt;
  UnionFind(ll n){
    N = n;
    p=llvec(N);
    cnt=llvec(N, 0);
    rep(i, N){
      p[i] = i;
      cnt[i] = 1;
    }
  }

  void con(ll a, ll b){
    P at = root(a);
    P bt = root(b);
    if(at.second!=bt.second){
      if(at.first>bt.first){
        swap(at, bt);
        swap(a, b);
      }
      p[at.second] = bt.second;
      cnt[bt.second]+=cnt[at.second];
      p[a]=bt.second;
    }
  }

  P root(ll a){
    ll atmp = a;
    ll c=0;
    while(atmp!=p[atmp]){
      atmp = p[atmp];
      c++;
    }
    p[a] = atmp;
    return {c, atmp};
  }

  bool is_con(ll a, ll b){
    P at=root(a);
    P bt=root(b);
    return at.second == bt.second;
  }
  
};

struct dijkstra{
  ll N;
  llvec d;
  vector<vector<edge>> e;
  dijkstra(ll n){
    N = n;
    //d = llvec(N, 1e18);
    e = vector<vector<edge>>(N);
  }

  void add_edge(ll from, ll to, ll cost){
    e[from].push_back({to, cost});
  }

  void run(ll start){
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    d = llvec(N, 1e18);
    d[start]=0;
    while(!que.empty()){
      P q = que.top();que.pop();
      ll dc = q.first;
      ll x = q.second;
      if(dc>d[x]){
        continue;
      }else{
        for(auto ip: e[x]){
          if(d[ip.x]<=d[x]+ip.c){
            continue;
          }else{
            d[ip.x]= d[x]+ip.c;
            que.push({d[ip.x], ip.x});
          }
        }
      }
    }
  }  
};


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N;
  cin >> N;
  llvec A(N);
  rep(i, N){
    cin >> A[i];
  }

  llvec S(N+1, 0);
  rep(i, N){
    S[i+1] = mod(S[i] + A[i], MOD);
  }
  ll ans = 0;
  rep(i, N){
    ans = mod(ans + A[i]*(S[N]-S[i+1]), MOD);
  }
  cout << ans << endl;
  
  
  return 0;
}


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

int intpow(int x,int y){
  double a=x,b=y;
  return pow(a,b);
}//(x,y) xをy乗する

int intfabs(int x){
  double a=x;
  return fabs(a);
}//(x) の絶対値

int in(){
  int a;
  cin >> a;
  return a;
}//int型関数の受け取り

void forin(int* x,int y){
  for (int i=0;i<y;i++){
    cin >> x[i];
  }
}//配列の受け取り

main(){
  int n=in(),s=0;
  vector<int> l(n);
  for (int i=0;i<n;i++) cin >> l[i];
  sort(l.begin(),l.end());
  for (int i=0;i<n-1;i++){
    s+=l[i];
  }
  if (s>l[n-1]) cout << "Yes";
  else cout << "No";
  cout << endl;
}


Measured memory_bytes: 256
data = input().split(" ")

M = int(data[0])
D = int(data[1])


# 結果用変数
count = 0

# 1月からm月
for i in range(M):
    i += 1
    # 1日からd日
    for j in range(D):
        j += 1
        # 二桁チェック
        if j >= 10:
            d_1 = int(str(j)[:1])
            d_10 = int(str(j)[1:])
            if d_1 >= 2 and d_10 >= 2:
                if d_1 * d_10 == i:
                    count += 1
print(count)

Measured memory_bytes: 3064
N = int(input())
A = [int(x) for x in input().split()]  
A.sort(reverse=True)

if A[-1]==0:
  print(0)
  exit()
  
mul = A[0]
i = 1
while mul<=10**18 and i<N:
  mul*=A[i]
  i += 1
  
if mul>10**18:
  print(-1)
else:
  print(mul)


Measured memory_bytes: 88684
N = int(input())
V = [int(num) for num in input().split()]


def minIdx(li):
    min = 0
    for num in li:
        min = li.index(num) if num < li[min] else min
    return min


while len(V) != 1:
    x = (V.pop(minIdx(V)) + V.pop(minIdx(V))) / 2
    V.append(x)

print(V[0])


Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
//#define vi vector<int>
#define all(a) a.begin(),a.end()
typedef pair<int,int> P;
const long long mod=998244353;
const long long inf=1ll<<61;
double a[200006];

int pow10(int a){
	if(!a)return 1;
	return 10*pow10(a-1);
}
int divx(int a,int div){
	if(a%div)return 0;
	return 1+divx(a/div,div);
}

int gcd(int a,int b){
	if(!b)return a;
	return gcd(b,a%b);
}

int cnt[40][40][44][20];

signed main(){
	int n;cin>>n;
	vector<P>V;
	rep(i,n){
		string s;cin>>s;
		string x,y;
		int flg=0;
		rep(i,s.size()){
			if(s[i]=='.')flg++;
			else if(flg==0){
				x.push_back(s[i]);
			}
			else {
				y.push_back(s[i]);
			}
		}
		if(y=="")y="0";
		int u=stoll(x+y),v=pow10(y.size());
		int G=gcd(u,v);
		u/=G;v/=G;
//		cout<<u<<' '<<v<<endl;
		V.push_back(P(u,v));
		cnt[divx(u,2)][divx(u,5)][divx(v,2)][divx(v,5)]++;
	}
	int ans=0;

	rep(i,n){
		int vi=divx(V[i].first,2),vj=divx(V[i].first,5),vk=divx(V[i].second,2),vl=divx(V[i].second,5);
		for(int p=0;p<=vi;p++){
			for(int q=0;q<=vj;q++){
				for(int r=vk;r<=43;r++){
					for(int s=vl;s<=18;s++){
						ans+=cnt[r][s][p][q];
					}
				}
			}
		}
	}

	rep(i,n){
		if(V[i].second==1)ans--;
	}
	cout<<ans/2<<endl;
}

Measured memory_bytes: 7608
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(int i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(int i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,map<S,T> a){
  os << "{";
  for (auto &&i : a)
  {
    os << i.first << ":" << i.second << " ";
  }
  os << "}";
  return os;
}

const long long MOD = 1000000007;

void solve(long long N, long long K){
  set<ll> p;
  for(long long i = 1; i*i <= N; i++){
    p.insert(i);
    p.insert(N/i);
  }
  vector<ll> pp(p.begin(),p.end());
  vector<vector<ll>> dp(K,vector<ll>(p.size()));
  ll S=p.size();
  for (int i=0; i<(long long)pp.size();i++)
  {
    dp[0][i]=pp[i];
  }
  REP(K-1){
    for (int j=0;j< (long long)pp.size();j++)
    {
      if(j==0){
        dp[i+1][j]=dp[i][S-1]%MOD;
      }else{
        dp[i+1][j]=dp[i][S-1-j]*(pp[j]-pp[j-1])%MOD;
        dp[i+1][j]+=dp[i+1][j-1];
        dp[i+1][j]%=MOD;
      }
    }
  }
  cout<<dp[K-1][S-1]<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 53760
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;

#define ARRAY_MAX 505

int main(){

    ll n;
    cin >> n;
    map<ll,ll> mp;
    REP(i,n){
        ll tmp;
        cin >> tmp;
        mp[tmp]++;
    }

    ll ans = 0;
    for(auto itr:mp){
        if(itr.second % 2 != 0){
            ans++;
        }
    }
    cout << ans << endl;


    return 0;
}

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

#define rep3(i, s, n ,a) for (int i = (s); i < (int)(n); i+=a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

int main(){
    int k, a, b, flag=0;
    cin >> k;
    cin >> a >> b;
    //int start = a / k, end = b / k;
    rep2(i, a, b+1){
        if(i%k==0){
            cout << "OK" << endl;
            flag = 1;
            break;
        }
    }
    if(!flag){
        cout << "NG" << endl;
    }
    return 0;
}

Measured memory_bytes: 3588
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(I, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ll = long long;

int main() {
  string s;
  cin >> s;
  int n = s.size(),m = 0;
  if(s[0] != 'A'){
    cout << "WA" << endl;
    return 0;
  }
  REP(i,n){
    if(i > 1 && i < n-1){
      if(s[i] == 'C'){
        m = i;
        break;
      }
    }
  }
  if( m == 0 ){
    cout << "WA" << endl;
    return 0;
  }    
  REP(i,n){
    if(i != 0 && i != m){
      if(s[i] < 'a' || s[i] > 'z'){
        cout << "WA" << endl;
        return 0;
      }
    }
  }
  cout << "AC" << endl;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807/2;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
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;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll m;
ll ans=-1;
ll d,c;
ll sum=-1;

int main(){
	cin>>m;
	REP(i,m){
		cin>>d>>c;
		ans+=c;
		sum+=(d*c);
	}
	sum/=9;
	cout<<sum+ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int n,cnt,mp[300005],ans[300005],del[300005],siz[300005];
int main()
{
	scanf("%d",&n);
	for(int i=1,a;i<=n;i++)
	{
		scanf("%d",&a);
		if(!mp[a])mp[a]=++cnt;
		siz[mp[a]]++;
	}
	for(int i=1;i<=cnt;i++)del[1]++,del[siz[i]+1]--;
	for(int i=1,nw=0;i<=n;i++)nw+=del[i],ans[i]=ans[i-1]+nw;
	for(int k=1,te=n;k<=n;k++)
	{
		while(ans[te]<te*k)te--;
		printf("%d\n",te);
	}
}

Measured memory_bytes: 4480
#include<iostream>
#include<stdio.h>
#include<algorithm>

using namespace std;

int A[1000000], n;

int main(){
    cin >>n;
    for(int i = 0; i < n; i++){
        scanf("%d", &A[i]);
    }
    
    int q, k, sum = 0;
    cin >>q;
    for(int i = 0; i < q; i++){
        scanf("%d", &k);
        //標準ライブラリのlower_boundを使用
        if(*lower_bound(A, A + n, k) == k)sum++;
    }
    
    cout << sum << endl;
    
    return 0;
}


Measured memory_bytes: 3540
import java.util.Scanner;

public class Main {

	static Scanner scanner;
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int a= gi();
	    int b= gi();
	    int h= gi();


	    System.out.print((a+b)*h/2);
	   
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}
}

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

int main(void){

char p[4];
scanf("%s",p);
int a = p[0] - '0';
int b = p[1] - '0';
int c = p[2] - '0';
int d = p[3] - '0';


int *q = malloc(sizeof(int)*2);
q[0] = b; q[1] = (-1)*b;
int *r = malloc(sizeof(int)*2);
r[0] = c; r[1] = (-1)*c;
int *s = malloc(sizeof(int)*2);
s[0] = d; s[1] = (-1)*d;


int flag=0;

	for(int j=0;j<2;j++){
		if(flag==1) break;
		for(int k=0;k<2;k++){
			if(flag==1) break;
			for(int l=0;l<2;l++){
				if(a+q[j]+r[k]+s[l] == 7){
					printf("%d",a);
					if(j==0) printf("+%d",b);
					else printf("-%d",b);
					if(k==0) printf("+%d",c);
					else printf("-%d",c);
					if(l==0) printf("+%d",d);
					else printf("-%d",d);
					printf("=7\n");
					flag = 1;
					break;
				}

			}
		}

	}





}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

ll n;
vector<lvector> G(n);
lvector dist;

void dfs(ll v, ll d=0, ll p=-1) {
  dist[v]=d;
  for(ll u:G[v]) {
    if(u==p) continue;
    dfs(u,d+1,v);
  }
  return;
}

lvector get_distance(ll s) {
  dist=lvector(n,0);
  dfs(s);
  return dist;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll u,v,a,b,ans=0;cin>>n>>u>>v;
  u--; v--;
  G.resize(n);
  rep(i,n-1) {
    cin>>a>>b; a--; b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  lvector distT=get_distance(u);
  lvector distA=get_distance(v);
  rep(i,n) if(distT[i]<distA[i]) ans=max(ans,distA[i]);
  print(ans-1);
  return 0;
}

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

typedef long long ll;

#define reg register 
#define rep(a,b,c) for(reg int a=b,a##end=c;a<=a##end;++a)
#define drep(a,b,c) for(reg int a=b,a##end=c;a>=a##end;--a)

char IO;
int rd(){
	int s=0,f=0;
	while(IO=getchar(),IO<'0'||IO>'9')if(IO=='-')f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(IO=getchar(),IO>='0'&&IO<='9');
	return f?-s:s;
}

const int N=10000;

int n,m;

int main(){
	n=rd(),m=rd();
	int mi=1e9,ans=0,s=0;
	rep(i,1,n){
		int x=i+m-1;
		s+=x;
		if(mi>abs(x)) mi=abs(x),ans=x;
	}
	printf("%d\n",s-ans);
}







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

int main() {
  string s;
  cin >> s;
  
  int ans = 0, i;
  for(i = 0; i < s.size() - 1; i++){
    if(s.at(i) != s.at(i + 1)){
      ans++;
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 512
from functools import reduce

S = input()

# 末尾から各あまりについてDP
M = 13
MOD = 10**9 + 7
ans = reduce(
    lambda acc, c: (
        [
            sum(
                acc[0][(i - acc[1] * j) % M]
                for j in range(10)
            ) % MOD
            for i in range(M)
        ] if c == '?' else
        [
            acc[0][(i - acc[1] * int(c)) % M]
            for i in range(M)
        ],
        (10 * acc[1]) % M
    ),
    S[::-1],
    (
        [
            1 if i == 0 else
            0
            for i in range(M)
        ],
        1
    )
)[0][5]

print(ans)


Measured memory_bytes: 46060
#include<iostream>
using namespace std;
#define A 80
#define B 65
#define C 50
#define D 30

int main()
{
	int m,f,r;

	while(1)
	{
		cin >> m >> f >> r ;
		if((m==-1)&&(f==-1)&&(r==-1)) break;
		if((m==-1)||(f==-1)){
			cout << 'F' << endl ;
			continue;
		}
		if((m+f)>=A) cout << 'A' << endl;
		if(((m+f)>=B)&&(m+f)<A) cout << 'B' << endl ;
		if(((m+f)>=C)&&(m+f)<B) cout << 'C' << endl ;
		if(((m+f)>=D)&&(m+f)<C)
		{
			if(r>=C) cout << 'C' << endl ;
			else cout << 'D' << endl ;
		}
		if((m+f)<D) cout << 'F' << endl ;

	}
	
	return 0;
}

Measured memory_bytes: 1152
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */

#include <bits/stdc++.h>
//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>
#include <utility>

template<typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template<typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<class X, class Y>
std::ostream &operator<<(std::ostream &os, std::pair<X, Y> const &p) {
    return os << p.first << " " << p.second;
}

template<class Ch, class Tr, class Container>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, Container const &x) {
    bool first = true;
    for (auto &y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}

using namespace std;

class BROTN {
    const int N = 26;

public:
    void solve(std::istream &in, std::ostream &out) {
        int n;
        in >> n;
        string str;
        in >> str;
        for (char &c: str) {
            c = 'A' + (c - 'A' + n) % N;
        }
        out << str << "\n";
    }

    void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
    BROTN solver;
    solver.setup();
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	char str[15];
	int a[10][10];
	int i, j;
	
	while (scanf("%s", str) != EOF){
		
		for (i = 0; i < 10; i++){
			a[0][i] = str[i] - '0';
		}
		for (i = 1; i < 10; i++){
			for (j = 0; j < 10 - i; j++){
				a[i][j] = (a[i - 1][j] + a[i - 1][j + 1]) % 10;
			}
		}
		
		printf("%d\n", a[9][0]);
	}
	
	return (0);
}

Measured memory_bytes: 540
ALPHABET = ["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"]

s = input()
for i in range(26):
    if s.count(ALPHABET[i]) == 0:
        print(ALPHABET[i])
        break
else:
    print("None")


Measured memory_bytes: 3188
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let S: String = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().chars().collect()
    };

    let ans = if S.contains("AC") { "Yes" } else { "No" };

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define ll int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll x;
	cin>>x;
	ll g=__gcd(x,360);
	cout<<(360)/g<<"\n";
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
using namespace std;
int main() {
	string s;
	cin >> s;

	int x = 0;
	for (char c : s) {
		x += (c - '0');
	}

	if (x % 9 == 0) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

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

ll mean(ll a, ll b){
	return (a + b) / 2;
}

int main(){
	int n;
	cin >> n;
	vector<ll> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	ll ans = v[0];
	for(int i = 1; i < n; i++){
		ans = mean(ans, v[i]);
	}
	cout << fixed << ans << endl;                      
	return 0;
}

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

def solve():
    INF = float('inf')
    idEle = -INF
    def _binOpe(x, y):
        return x if x >= y else y
    def makeSegTreeLazy(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        lazy = [0] * (2*numPow2)
        return data, lazy, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iST, A):
        vIfSet = _getVIfSet(iST, A)
        data[iST] += vIfSet
        lazy[iST] += A
    def _getVIfSet(iST, A):
        return A
    def _getIndices(iSt, iEn):
        iSTs = []
        L = iSt + numPow2
        R = iEn + numPow2
        L0 = L // (L & -L)
        R0 = R // (R & -R)
        while L < R:
            if L < L0:
                iSTs.append(L)
            if R < R0:
                iSTs.append(R)
            L >>= 1
            R >>= 1
        while L:
            iSTs.append(L)
            L >>= 1
        return iSTs
    def _propagate(iST):
        v = lazy[iST]
        if v:
            _update1(2*iST, v)
            _update1(2*iST+1, v)
            lazy[iST] = 0
    def update(iSt, iEn, A):
        iSTs = _getIndices(iSt, iEn)
        for iST in reversed(iSTs):
            _propagate(iST)
        L = iSt + numPow2
        R = iEn + numPow2
        while L < R:
            if L & 1:
                _update1(L, A)
                L += 1
            if R & 1:
                R -= 1
                _update1(R, A)
            L >>= 1
            R >>= 1
        for iST in iSTs:
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        iSTs = _getIndices(iSt, iEn)
        for iST in reversed(iSTs):
            _propagate(iST)
        ans = idEle
        L = iSt + numPow2
        R = iEn + numPow2
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


    N, M = map(int, input().split())
    LRs = [[] for _ in range(N+1)]
    for _ in range(M):
        L, R, A = map(int, input().split())
        LRs[R].append((L, A))

    data, lazy, numPow2 = makeSegTreeLazy(N+1)
    setInit([0]*(N+1))

    for R in range(1, N+1):
        v = getValue(0, R)
        v0 = getValue(R, R+1)
        update(R, R+1, v-v0)
        for L, A in LRs[R]:
            update(L, R+1, A)

    ans = getValue(0, N+1)
    print(ans)


solve()


Measured memory_bytes: 125260
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <vector>
#include <bitset>
#include <cmath>
#include <utility>
#define Maxn 100005
#define Maxm 1000005
#define lowbit(x) x&(-x)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PI acos(-1.0)
#define LL long long 
#define Inf (1LL<<62)
#define inf 0x3f3f3f3f
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
using namespace std;
const int Mod=1e9+7;
LL find(LL x)  
{  
    LL k=Mod-2,ans=1;  
    while(k)  
    {  
        if (k&1) 
            ans=ans*x%Mod;  
        x=x*x%Mod;  
        k>>=1;  
    }  
    return ans;  
} 
LL factorial[Maxn];  
void init(LL p)  
{  
    factorial[0] = 1;  
    for(int i = 1;i <= p;i++)  
        factorial[i] = factorial[i-1]*i%Mod;  
}  
LL Lucas(LL a,LL k,LL p) //求C(n,m)%p p最大为10^5。a,b可以很大！  
{  
    LL re = 1; 
    if(a==0&&k==0)
    	return 1;
    else if(a==0)
    	return 0; 
    while(a && k)  
    {  
        LL aa = a%p;
        LL bb = k%p;  
        if(aa < bb) return 0; //这个是最后的改动！  
        re = re*factorial[aa]*find(factorial[bb]*factorial[aa-bb]%p)%p;//这儿的求逆不可先处理  
        a /= p;  
        k /= p;  
    }  
    return re;  
}  
int main()
{
	//input;output;
	int arr[Maxn],n,flag,prefix,suffix;
	bool vis[Maxn];
	init(Maxn);
	while(~scanf("%d",&n))
	{
		prefix=suffix=0;
		memset(vis,false,sizeof(vis));
		for(int i=0;i<=n;i++)
		{
			scanf("%d",arr+i);
			if(!vis[arr[i]])
				vis[arr[i]]=true;
			else
				flag=arr[i];
		}
		for(int i=0;i<=n;i++)
		{
			if(arr[i]!=flag)
				prefix++;
			else
				break;
		}
		for(int i=n;i>=0;i--)
		{
			if(arr[i]!=flag)
				suffix++;
			else
				break;
		}
		for(int i=1;i<=n+1;i++)
			printf("%lld\n",(Lucas(n+1,i,Mod)-Lucas(prefix+suffix,i-1,Mod)+Mod)%Mod);
	}
	return 0;
}

Measured memory_bytes: 2432
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>
 
 
int main()
{
    long int h, n; std::cin >> h >> n;
    long int sum = 0;
    for(int i=0; i<n; i++)
    {
        long int temp;
        std::cin >> temp;
        sum += temp;
    }
    if(h<=sum) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back


int main() {
    vi a;
    int ans = 0;
    for (int i = 0; i < 5; i++) {
        int c;
        cin >> c;
        a.pb(c);
    }


    int sRem = 10;
    for (int i = 0; i < a.size(); i++) {
        ans += ((a[i] + 9) / 10) * 10;
        int cRem = a[i] % 10;
        if(cRem != 0){
            sRem = min(sRem, cRem);
        }
    }

    ans -= 10 - sRem;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{int sum=0;
  string s;
  cin>>s;
  for(int i=0;i<s.length();i++)
  {
    sum+=s[i]-'0';
  }
 if(sum%9==0)
 {cout<<"Yes";}
 else{cout<<"No";}
return 0;
}

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

int main()
{
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  int SUM = 0;
  rep(i, N)
  {
    cin >> A.at(i);
    SUM += A.at(i);
  }
  int cnt = 0;
  rep(i,N){
    if((double)A.at(i)>=(double)SUM/(double)(4*M))
      cnt++;
  }

  if(cnt>=M)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
  }


Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <cstdlib>
#include <map> // pair
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>

using namespace std;
int A;
int B;

int main()
{
    scanf("%d\n",&A);
    if (A%2==0)
    {
        int x;
        x=pow(A/2,2);
        printf("%d\n",x );
    }
    else{
        int y;
        y=((A+1)/2)*((A-1)/2);
        printf("%d\n",y );
    }
}


Measured memory_bytes: 256
#include <iostream>
#include  <stdio.h>
#include  <algorithm>
#include  <math.h>
#include  <vector>
#include  <string>
#include  <sstream>
#include  <numeric>
#include  <set>
#include <map>

#define rep(i, j) for(int i = 0; i < j; i++)
#define all(i) i.begin(), i.end()
#define ll long long

using namespace std;

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

	int num = 0;
	while (cin >> num && num != 0)
	{
		vector<vector<int>> gem(22, vector<int>(22, 0));
		rep(i, num)
		{
			int tmp[2] = { 0 };
			cin >> tmp[0] >> tmp[1];
			gem[tmp[0]][tmp[1]] = 1;
		}
		int num2 = 0;  cin >> num2;
		int x = 10, y = 10, ans = 0;
		rep(i, num2)
		{
			char dir = 0; int m = 0;
			cin >> dir >> m;
			rep(j, m)
			{
				switch (dir)
				{
				case 'N': y++; break;
				case 'E': x++;  break;
				case 'S': y--;  break;
				case 'W': x--;  break;
				}
				num -= gem[x][y];
				gem[x][y] = 0;
			}
		}
		if (num == 0) { printf("Yes\n"); }
		else { printf("No\n"); }
	}
	return 0;
}

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

int main(){
	int n,t=0;
	cin>>n;
	int a[52];
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]!=i)t++;
	}
	if(t==1||t>2)printf("NO\n");
	else printf("YES\n");				
	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)

leaf = [False for _ in range(n)]

for i in range(n):
	if len(adj[i]) == 1:
		leaf[i] = True

stack = [i for i in range(n) if leaf[i]]
while stack:
	l = stack.pop()
	for v in adj[l]:
		if len(adj[v]) < 3 and not leaf[v]:
			leaf[v] = True
			stack.append(v)

ans = 0
def dfs(x, p):
	global ans
	cnt = 0
	for v in adj[x]:
		if v == p:
			continue
		if leaf[v]:
			cnt += 1
		else:
			dfs(v, x)
	ans += max(0, cnt-1)

if sum(leaf) == n:
	print(1)
else:
	for i in range(n):
		if not leaf[i]:
			root = i
			break
	dfs(root, -1)
	print(ans)

Measured memory_bytes: 75632
//#include <bits/stdc++.h>
#include <stack>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	//入力
	long A[100001], B[100001], x[100001] = {};
	long N, K, M = 1000000000, ans = 0, l = 0, r = 0, sum = 0, a = 0, b = 0, c = 0;
	cin >> a >> b >>c;
	/*for (int i = 0; i < N; i++) {
		cin >> a[i];
	}*/
	//処理
	if (a <= b) ans = min(b / a, c);
	//出力
	cout << ans << endl;
}

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

int main(){
  int n;
  int cake;
  
  while(cin >> n, n){
    int ans = 0;
    for(int i = 0 ; i < n*(n-1)/2 ; i++){
      cin >> cake;
      ans += cake;
    }
    cout << ans/(n-1) << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll x;
    cin >> x;
    ll ans = 0;
    ans += (x / 500) * 1000;
    x %= 500;
    ans += (x / 5) * 5;
    cout << ans << endl;
}


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

using namespace std;

int main()
{
    set<int> A;
    int N;
    int a;
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> a;
        auto itr=A.find(a);
        if(itr==A.end()) {
            A.insert(a);
        } else {
            A.erase(a);
        }
    }
    cout << A.size() << endl;
}


Measured memory_bytes: 4864
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int lMax = 0;
    int lSum = 0;
    for (int i = 0; i < n; i++){
        int l;
        scanf("%d", &l);
        lSum += l;
        if(l > lMax){
            lMax = l;
        }
    }
  
    if(lSum <= lMax * 2){
        printf("No");
    } else {
        printf("Yes");
    }
      
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
//author wjl

using namespace std;
#define LL long long
#define Rint register int
#define U unsigned
#define forn(i,a,b) for(int i = a;i <= b;++i)
#define nfor(i,a,b) for(int i = a;i >= b;--i)
#define pii pair<int ,int>
#define MS0(X) memset(X,0,sizeof(X))
#define MSf(X) memset(X,false,sizeof(X))
#define MS1(X) memset(X,-1,sizeof(X))
#define BR printf("--------------------\n")
#define pb push_back
#define rep(i,a,b) for(Rint i=a;i<=b;++i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const double PI=atan(1.)*4.;
const int maxn=1e6+5;
const int inf = 0x3f3f3f3f;
const int mod=1e9+7;
const double e=2.71828182845904523536;
int dirx[8]={1,0,-1,0,1,-1,-1,1};
int diry[8]={0,1,0,-1,1,1,-1,-1};
struct node
{
    double x,y;
}a[maxn];
double dis(node a,node b)
{
    double x=a.x-b.x;
    double y=a.y-b.y;
    return sqrt(x*x+y*y);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;
    //double jie=1;
    for(int i=0;i<n;i++)
    {
        //jie*=(i+1);
        cin>>a[i].x>>a[i].y;
    }
    //double ans;
    //cin>>ans;
    double sum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            sum+=dis(a[i],a[j]);
        }
    }
    //DEBUG(sum/ans);
    //DEBUG(ans/sum);
    cout<<fixed<<setprecision(10)<<sum*2/n<<endl;
    return 0;
}
/*
2 1
3 1.5
8 4
3
0 0
1 0
0 1
2.2761423749
2
-879 981
-866 890
91.9238815543
8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310
7641.9817824387
*/

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<long long> a(n),b(n);
	vector<pair<long long,int> > c(n);
	for(int i=0;i<n;i++)
	{
		cin >> a[i] >> b[i];
		c[i]=make_pair(a[i]+b[i],i);
	}
	sort(c.begin(),c.end());
	reverse(c.begin(),c.end());

	long long ans=0;

	for(int i=0;i<n;i++)
	{
		if(i%2==0)
			ans+=a[c[i].second];
		else
			ans-=b[c[i].second];
	}

	cout << ans << endl;
}


Measured memory_bytes: 3328
/*
[dwacon5th-prelims] C - k-DMC
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 1e6;
const int C = 3;
const char m[C] = {'D', 'M', 'C'};

int N;
string S;
int Q;

ll solve(int k) {
    ll ans = 0;
    ll cnt_d = 0, cnt_m = 0, cnt_dm = 0;
    for (int i = 0; i < N; i++) {
        if (i - k >= 0) {
            if (S[i - k] == 'M') {
                cnt_m--;
            } else if (S[i - k] == 'D') {
                cnt_d--;
                cnt_dm -= cnt_m;
            }
        }
        if (S[i] == 'C') {
            ans += cnt_dm;
        } else if (S[i] == 'M') {
            cnt_m++;
            cnt_dm += cnt_d;
        } else if (S[i] == 'D') {
            cnt_d++;
        }
    }

    return ans;
}

int main() {
    cin >> N;
    cin >> S;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int k;
        cin >> k;
        cout << solve(k) << endl;
    }

    return 0;
}


Measured memory_bytes: 1412
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, a[200005] = {}, b[200005] = {};
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    sort(a, a + n); sort(b, b + n);
    if (n % 2) cout << b[n / 2] - a[n / 2] + 1;
    else cout << b[n / 2] + b[n / 2 - 1] - a[n / 2] - a[n / 2 - 1] + 1;
}


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

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

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

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL INF = 1e9;
const LL MOD = 1e9+7;

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

//memo
// setprecision()

int main() {
  int N;
  cin >> N;
  
  cout << "ABC" << N << endl;
  
  return 0;
}


Measured memory_bytes: 256
from collections import deque
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)

    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = deque([self.node_list[0]])
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)

            if not stack:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])

Measured memory_bytes: 181072
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main()
{
    ll n,i,ans,l,k,j;
    string s;
    cin>>n;
    if(n<10){
        cout<<n<<endl;
        return 0;
    }
    vector<vector<ll>>a(11,vector<ll>(11));
    for(i=1;i<=n;i++){
      s=to_string(i);
      l=s.size();
      if(s[l-1]!='0'){
        j=s[0]-48;
        k=s[l-1]-48;
        a[j][k]++;
      }
    }
    ans=0;

    for(i=1;i<=9;i++){
        for(j=1;j<=9;j++)
         ans+=a[i][j]*a[j][i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3692
#include "bits/stdc++.h"

using namespace std;

void solve(void)
{
	string s;
	cin >> s;
	int a = (s[0] - '0') * 10 + (s[1] - '0');
	int b = (s[2] - '0') * 10 + (s[3] - '0');
	bool ym = 1 <= b && b <= 12;
	bool my = 1 <= a && a <= 12;
	if (ym && my)
	{
		cout << "AMBIGUOUS" << endl;
	}
	else if (ym)
	{
		cout << "YYMM" << endl;
	}
	else if (my)
	{
		cout << "MMYY" << endl;
	}
	else
	{
		cout << "NA" << endl;
	}
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

typedef long long lli;

lli n, m[100], l[100], d[100], dp[2][1<<16];

main(){
  while(cin >> n && n){
    for(int i=0;i<n;i++){
      cin >> m[i] >> l[i];
      d[i] = 0;
      for(int j=0;j<m[i];j++){
        lli a, b;
        cin >> a >> b;
        for(int k=a-6;k<b-6;k++) d[i] |= 1 << k;
      }
    }
    fill(dp[0], dp[2], -1);
    dp[0][0] = 0;
    for(int i=0;i<n;i++){
      for(int j=0;j<(1<<16);j++){
        if(dp[i%2][j] == -1) continue;
        dp[(i+1)%2][j] = max(dp[(i+1)%2][j], dp[i%2][j]);
        if((d[i] & j) == 0) dp[(i+1)%2][j|d[i]] = max(dp[(i+1)%2][j+d[i]], dp[i%2][j] + l[i]);
      }
    }
    lli ans = 0;
    for(int i=0;i<(1<<16);i++) ans = max(ans, dp[n%2][i]);
    cout << ans << endl;
  }
}

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

const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const int MOD=1000000007;

int t[200000],a[200000];
ll s[8][200000];

int main(){
	int n;cin>>n;
	vector<int>xs;
	rep(i,n){
		scanf("%d%d",&t[i],&a[i]);
		rep(j,8){
			s[j][i+1]=s[j][i];
			if(j==a[i])s[j][i+1]++;
		}
		xs.push_back(t[i]);
	}
	int q;cin>>q;
	rep(i,q){
		int l,r;scanf("%d%d",&l,&r);
		int R=lower_bound(xs.begin(),xs.end(),r)-xs.begin();
		int L=lower_bound(xs.begin(),xs.end(),l)-xs.begin();
		double ans=1e9;
		rep(j,8){
			int cnt=s[j][R]-s[j][L];
			ans*=pow((10-j)/10.,cnt);
		}
		printf("%.12lf\n",ans);
	}
}


Measured memory_bytes: 10736
#!python3.4.3

a = []
result = []

for i in range(3):
  a.append(list(map(int, input().split(' '))))
  
a_flat = sum(a, [])
n = int(input())

for _ in range(n):
  b = int(input())
  
  if b in a_flat:
    result.append(a_flat.index(b))

# print(a_flat)
score = 'No'
result = set(result)

if result:
  if set([0, 1, 2]) <= result:
    score = 'Yes'
  if set([3, 4, 5]) <= result:
    score = 'Yes'
    
  if set([6, 7, 8]) <= result:
    score = 'Yes'
    
  if set([0, 3, 6]) <= result:
    score = 'Yes'
    
  if set([1, 4, 7]) <= result:
    score = 'Yes'
    
  if set([2, 5, 8]) <= result:
    score = 'Yes'
    
  if set([0, 4, 8]) <= result:
    score = 'Yes'
    
  if set([2, 4, 6]) <= result:
    score = 'Yes'

print(score)
  

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <string>
#include <utility>

#define repd(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
	int a;
	cin >> a;
	return a;
}

void inputArray(int *p,int a){
	rep(i,a){
		cin >> p[i];
	}
}

void inputVector(vector<int> *p,int a){
	rep(i,a){
		int input;
		cin >> input;
		p -> push_back(input);
	}
}

template <typename T>
void output(T a,int precision){
	if(precision > 0){
		cout << setprecision(precision) << a << "\n";
	}else{
		cout << a << "\n";
	}
}

int main(){
	//source
	int num[3];
	int ans=0;
	rep(i,3){
		cin>>num[i];
		ans+=num[i];
	}
	int result=0;
	rep(i,3){
		result=max(ans+num[i]*9,result);
	}
	cout << result << endl;
	return 0;
}


Measured memory_bytes: 256