akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int N, M;
int L, R;
ll D;
int pre[100000 + 10];
int rk[100000 + 10];
ll dist[100000 + 10];
ll dmax[100000 + 10];
ll dmin[100000 + 10];
int cfind(const int x) {
  if (pre[x] != x) {
    int root = cfind(pre[x]);
    dist[x] += dist[pre[x]];
    pre[x] = root;
  }
  return pre[x];
}
ll cdist(const int x) {
  cfind(x);
  return dist[x];
}
void cunion(const int a, const int b, const ll d) {
  const int h1 = cfind(a);
  const int h2 = cfind(b);
  const ll d1 = cdist(a);
  const ll d2 = cdist(b);
  const ll dd = d + d1 - d2;
  if (rk[h1] < rk[h2]) {
    pre[h1] = h2;
    dist[h1] = -dd;
  } else if (rk[h1] > rk[h2]) {
    pre[h2] = h1;
    dist[h2] = dd;
  } else {
    pre[h1] = h2;
    dist[h1] = -dd;
    rk[h2]++;
  }
}
bool sol () {
  cin >> N >> M;
  fill(dmax, dmax + N + 1, LLONG_MIN);
  fill(dmin, dmin + N + 1, LLONG_MAX);
  
  iota(pre, pre + N + 1, 0);
  for(int i = 0; i < M; ++i) {
    cin >> L >> R >> D;
    if (L > N || R > N) return false;
    int h1 = cfind(L);
    int h2 = cfind(R);
    if (h1 == h2) {
      if (cdist(R) - cdist(L) != D) return false;
    } else {
      cunion(L, R, D);
    }
  }
  /*
  for(int i = 1; i <= N; ++i) {
    const int h = cfind(i);
    ll d = cdist(i);
    dmax[h] = max(dmax[h], d);
    dmin[h] = min(dmin[h], d);
    if (dmax[h] - dmin[h] > 1000000000) return false;
  }
  */
  return true;
}
int main () {
  ios::sync_with_stdio(false);
  if (sol()) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 3328
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, x, y;
int main() {
  cin>>n>>k>>x>>y;
  if (n <= k) cout<<n*x<<endl;
  else {
  	cout<<x * k + y * (n-k)<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
n,w = map(int ,input().split())
dp = [[0] * (w+1)  for _ in range(n)]
ll = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(w+1):
        tmp_w = ll[i][1] + j
        if tmp_w <= w:
            dp[i][tmp_w] = max(dp[i][tmp_w], dp[i-1][j] + ll[i][0])
        dp[i][j] = max(dp[i][j], dp[i-1][j])
print(max(dp[n-1]))


Measured memory_bytes: 41988
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define prtd(var, i) cout << fixed << setprecision(i) << var << endl;
#define ll long long
using namespace std;

int main(){
    char a;
    cin >> a;
    if(a >= 'A' && a <= 'Z') cout << 'A' << endl;
    else cout << 'a' << endl;
}

Measured memory_bytes: 3584
s=int(input())
a=[0,s]
i=1
while 1:
    i+=1
    if a[i-1]%2==0:
        a.append(a[i-1]//2)
    else:
        a.append(3*a[i-1]+1)
    if a.count(a[i])==2:
        print(i)
        exit()

Measured memory_bytes: 3060
#include<iostream>
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 {
    cout << "a < b" << endl;
  }
  return 0;
}

Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
#define MAXN	5005
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
long long func(long long a, long long b, long long x, long long y) {
	if (x > b) return b - a + 1 + y - x + 1;
	else return max(y, b) - a + 1;
}
int main() {
	long long a, b, r, t;
	read(a), read(b);
	if (a == b) {
		printf("1\n");
		return 0;
	}
	for (long long i = 63; i >= 0; i--) {
		long long tmp = 1ll << i;
		if ((tmp & a) ^ (tmp & b)) {
			r = i; t = tmp;
			break;
		}
		if (tmp & a) a ^= tmp;
		if (tmp & b) b ^= tmp;
	}
	long long c = t;
	for (long long i = r - 1; i >= 0; i--) {
		long long tmp = 1ll << i;
		if (tmp & b) {
			c += tmp * 2 - 1;
			break;
		}
	}
	cout << func(a, c, t + a, 2 * t - 1) << endl;
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 100000000
 
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
 
static const double EPS = 1e-8;
 
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};
 
struct Data{
	int start;
	int end;
};
 
int main(){
	int N,M;
	while(~scanf("%d %d",&N,&M)){
		Data data[101];
		for(int i=0;i<M;i++){
			int s,e;
			scanf("%d %d",&s,&e);
			data[i].start = s;
			data[i].end = e;		
		}
 
		int stime = 1;
		
		bool used[101];
		memset(used,0,sizeof(used));
		int res = 0;
		while(1){
			int etime = stime;
			int idx = -1;
			for(int i=0;i<M;i++){
				if(!used[i] && data[i].start <= stime){
					if(etime <= data[i].end){
						etime = data[i].end;
						idx = i;
					}
				}
			}
 
			if(idx != -1 && etime < N) {
				used[idx] = true;
				stime = etime+1;
				res++;
			}
		
			else if(idx != -1 && etime >= N){
				res++;
				printf("%d\n",res);
				break;
			}
 
			else if(idx == -1){
				printf("Impossible\n");
				break;
			}
		}
 
	}
}

Measured memory_bytes: 1192
#include <cstdio>
#include <cmath>
int n;
double x[1005], y[1005], X, Y, d, e;
double dist(double a, double b) {
	return a*a + b*b;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lf %lf", &x[i], &y[i]);
		X += x[i]; Y += y[i];
	}
	X /= n; Y /= n;
	double P = 0.1;
	for (int i = 0; i < 30000; i++) {
		int f = 0;
		d = dist(X - x[0], Y - y[0]);
		for (int j = 1; j < n; j++) {
			e = dist(X - x[j], Y - y[j]);
			if (d < e) { d = e; f = j; }
		}
		X += (x[f] - X)*P;
		Y += (y[f] - Y)*P;
		P *= 0.999;
	}
	printf("%.10lf\n", sqrt(d));
}

Measured memory_bytes: 128
n,a,b=map(int,input().split())
ans=0

def sum(k):
  s=0
  for j in range(len(k)):
  	s+=int(k[j])
  return s
  
for i in range(1,n+1):
  if a<=sum(str(i))<=b:
    ans+=i
    
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n; cin>>n;
	vector<int> v(n+1);
	for(int i=1;i<=n;i++)
		cin>>v[i];
	vector<int> cost(n+1);
	cost[2]=abs(v[2]-v[1]);
	for(int i=3;i<=n;i++)
		cost[i]=min(cost[i-1]+abs(v[i]-v[i-1]),cost[i-2]+abs(v[i]-v[i-2]));
	cout<<cost[n];
}

Measured memory_bytes: 1024
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int a[114];
int main()
{
	int out=1145141919,n;
	cin>>n;rep(i,n) cin>>a[i];
	REP(i,-114,114){
		int sum=0;
		rep(j,n) sum+=(i-a[j])*(i-a[j]);
		out=min(out,sum);
	}
	cout<<out<<endl;
}


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

#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

typedef long long int64;

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
    string s;
	cin >> s;
	int n = s.size();
	int ans = 0;
	for (int i = 0; i < n / 2; ++i) {
	    if (s[i] != s[n - i - 1]) {
		    ++ans;
		}
	}
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    l,r,d = map(int,input().split())
    ans = r//d - l//d
    if l%d == 0:
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 72984
import sys
import copy
import math
import itertools
import numpy as np

N = int(input())
S = input()
x = 0
max = 0
for i in range(N):
    if S[i] == "I":
        x+=1
    elif S[i] == "D":
        x-=1
    
    if max < x:
        max = x

print(max)

Measured memory_bytes: 26888
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 

i64 count(VI vis){
    i64 mi = INF;
    rep(i, 0, 24) rep(j, 0, 24) if (vis[i] && vis[j] && i != j){
        i64 d1 = abs(i - j);
        i64 d2 = 24 - d1;
        i64 d = min(d1, d2);
        mi = min(mi, d);
    }
    return mi;
}

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

int N; cin >> N;
VI cnt(13, 0), vis(24), v;
rep(i, 0, N){
    int d; cin >> d;
    ++cnt[d];
}
if (cnt[0]) {
    cout << "0\n";
    return 0;
}
vis[0] = 1;

rep(i, 1, 12){
    if (cnt[i] == 1) v.push_back(i);
    else if (cnt[i] == 2) vis[i] = vis[24 - i] = 1;
    else if (2 < cnt[i]) {
        cout << "0\n";
        return 0;
    }
}
if (cnt[12] == 1) vis[12] = 1;
else if (2 <= cnt[12]){
    cout << "0\n";
    return 0;
}

int M = v.size();
if (M == 0){
    cout << count(vis) << "\n";
    return 0;
}

i64 ans = 0;
rep(msk, 0, 1<<M){
    rep(i, 0, M){
        if (msk & (1 << i)) vis[v[i]] = 1, vis[24 - v[i]] = 0;
        else vis[v[i]] =0, vis[24 - v[i]] = 1;
    }
    ans = max(ans, count(vis));
}

cout << ans << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int Min(int a, int b, int c) {
	if (a <= b) { return std::min(a, c); }
	else return std::min(b, c);
}
int Max(int a, int b, int c) {
	if (a >= b) { return std::max(a, c); }
	else return std::max(b, c);
}
int main(void) {
	int a, b, x; cin >> x;
	a = x / 100; b = x % 100;
	if (a >= 1 && a <= 12) {
		if (b >= 1 && b <= 12)
			cout << "AMBIGUOUS" << endl;
		else
			cout << "MMYY" << endl;
	}
	else {
		if (b >= 1 && b <= 12)
			cout << "YYMM" << endl;
		else
			cout << "NA" << endl;
	}
	return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define EPS (1e-8)

int main() {
	double x1, y1, x2, y2, xq, yq;
	while (scanf("%lf,%lf,%lf,%lf,%lf,%lf", &x1, &y1, &x2, &y2, &xq, &yq) != EOF) {
		double v1x = x2 - x1, v1y = y2 - y1;
		double l = -10000000.0, r = 10000000.0;
		
		REP(i, 100) {
			double mid = (l + r) / 2.0;
			double cx = x1 + v1x * mid, cy = y1 + v1y * mid;
			double v2x = cx - xq, v2y = cy - yq;
			
			
			double dot = v1x * v2x + v1y * v2y;
			if (dot > 0) r = mid; 
			else l = mid;
			
			if (abs(dot) < EPS) {
				printf("%f %f\n", 2.0 * cx - xq, 2.0 * cy - yq);
				break;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) reverse((a).begin(), (a).end())
#define rep(i, a, b) for (int64_t i = (a); i < (b); ++i)
const int MOD = 1e9 + 7;
typedef long long ll;
const long long INF = 1LL << 60;

int n, m;

struct UnionFind {
  vector<int> par;

  UnionFind(int N) : par(N) {
    for (int i = 0; i < N; i++) par[i] = i;
  }

  int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx == ry) return;
    par[rx] = ry;
  }

  bool same(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};

int main() {
  cin >> n >> m;
  vector<int> a(m);
  vector<int> b(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  int ans = 0;
  for (int i = 0; i < m; i++) {
    UnionFind d(n);
    for (int j = 0; j < m; j++) {
      if (j != i) d.unite(a[j], b[j]);
    }
    bool bridge = false;
    for (int j = 0; j < m; j++) {
      if (!d.same(a[j], b[j])) bridge = true;
    }
    if (bridge) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n,m = gets.split.map(&:to_i)
dig = Array.new(n+1,0)
m.times do
  a,b = gets.split.map(&:to_i)
  dig[a] += 1
  dig[b] += 1
end
puts dig.all?{|i|i%2 == 0} ? "YES" : "NO"

Measured memory_bytes: 2556
#include <iostream>

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 
      cout << "a == b" << endl;
}



Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int llu;
typedef long double ld;
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define pb push_back
#define pf push_front
#define mp map<ll,ll>
#define INF 1000000000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
ll gcd(ll a,ll b)
{
    if(a==0)
    {
        return b;
    }
    else
    {
        return gcd(b%a,a);   
    }
}
ll lcm(ll a,ll b)
{
    return a*b/gcd(a,b);
}
int f(char c)
{
    return (int)c-96;
}
/**********************************************************************
***********************************************************************
*********************ACTUAL CODE BEGINS HERE***************************/
int main()
{   
    fast;
    ll mod=1e9+7;
    ll n;
    cin>>n;
    ll sum=1,sum1=1,a=1;
    for(int i=1;i<=n;i++)
    {
        sum=(sum*10)%mod;
        sum1=(sum1*8)%mod;
        a=(a*9)%mod;
    }
    ll ans=(sum+(sum1-2*a))%mod;
    if(ans<0)
    {
        cout<<ans+mod;
    }
    else
    {
        cout<<ans;   
    }
    return 0;
}

Measured memory_bytes: 3640
import collections
def main():

    N = int(input())
    dh = collections.defaultdict(set)
    dl = collections.defaultdict(set)
    for i in range(1, N+1):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            if y == 1:
                dh[i].add(x)
            else:
                dl[i].add(x)

    case = [[0], [1]]
    for _ in range(N-1):
        temp = []
        for lv in case:
            temp.append(lv + [0])
            temp.append(lv + [1])
        case = temp

    ans = 0
    for lv in case:
        h = set()
        l = set()
        # print(h)
        # print(lv)
        for i in range(len(lv)):
            if lv[i] == 1:
                h.add(i+1)
                h |= dh[i+1]
                l |= dl[i+1]

        prevh = len(h)
        prevl = len(l)
        while  True:
            addh = set()
            addl = set()
            for i in h:
                addh |= dh[i]
                addl |= dl[i]
            h |= addh
            l |= addl
            if prevh == len(h) and prevl == len(l):
                break
            prevh = len(h)
            prevl = len(l)

        # print(h.intersection(l), h, l)
        if len(h.intersection(l)) == 0:
            ans = max(ans, len(h))
    return ans



if __name__ == '__main__':
    print(main())

Measured memory_bytes: 14320
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
ll choose2(ll n)
{
  return n * (n - 1) / 2;
}

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  rep(i, n) a[i]--;
  vector<int> cnt(n);
  rep(i, n) cnt[a[i]]++;
  ll tot = 0;
  rep(i, n)
  {
    tot += choose2(cnt[i]);
  }
  rep(i, n)
  {
    ll ans = tot;
    ans -= choose2(cnt[a[i]]);
    ans += choose2(cnt[a[i]] - 1);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 4096
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld  double
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppi pair<pii,int> 
#define ppp pair<pii,pii>
#define pb push_back
#define N 200003
#define inf (ll)1e9+11
#define warmup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int mod=1e9+7;
vector<int> g[N];
int n,ct;
int a[N];
bool done[N];

void dfs(int i,int p,bool f)
{
    ct+=(!f);
    
    for(auto j:g[i])
        if(j!=p)
            dfs(j,i,f^1);
}   

void dfs1(int i,int p,bool f)
{
    if(!f)
    {
        ct+=3;
        if(ct>n)
            ct=3;
        a[i]=ct;
        done[ct]=1;
    }
    
    for(auto j:g[i])
        if(j!=p)
            dfs1(j,i,f^1);
}   

signed main()
{
    warmup
    
    cin>>n;
    int i,j,x,b;
    for(i=1;i<=n-1;++i)
        cin>>x>>b, g[x].pb(b), g[b].pb(x);
    
    dfs(1,1,0);
    if(ct<=n/3 or n-ct<=n/3)
    {
        if(ct<=n/3)
            ct=0, dfs1(1,1,0);
        else
            ct=0, dfs1(1,1,1);
        for(i=1;i<=n;++i)
            if(!a[i])
            {
                ct+=3;
                if(ct>n)
                    ct=((ct%3==0) ? 1:2);
                a[i]=ct;
            }   
    }   
    else
    {
        ct=-2;
        dfs1(1,1,0);
        for(i=1;i<=n;++i)
            if(!a[i])
            {
                ct+=3;
                if(ct>n)
                    ct=2;
                a[i]=ct;
            }   
    }   
    for(i=1;i<=n;++i)
        cout<<a[i]<<' ';
    
    return 0;
}


Measured memory_bytes: 15104
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include "set"
#include "map"
#include "unordered_map"
#include <string>
#include <iomanip>
#include <numeric>
#include "cmath"

using namespace std;
#define double long double
#define int long long
#define all(a) a.begin(), a.end()
const int N = 2e5 + 50;
const int mod = 998244353;
int T[4 * N];
int lazy[4 * N];
int ten[N];
int nine;
int n, q;

int place(int d, int pos) {
	return (d * ten[pos]) % mod;
}

int place(int l, int r, int val) {
	return (((val * ten[l]) % mod * (ten[r - l + 1]-1+mod)%mod) % mod * nine) % mod;
}

void build(int v, int tl, int tr) {
	if (tl == tr) {
		T[v] = place(1, tl);
		return;
	}

	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid);
	build(v << 1 | 1, mid + 1, tr);

	T[v] = T[v << 1] + T[v << 1 | 1];
	T[v] %= mod;
}

void push(int v, int tl, int tr) {
	if (lazy[v] == -1)
		return;
	lazy[v << 1] = lazy[v << 1 | 1] = lazy[v];
	lazy[v] = -1;
	int mid = (tl + tr) >> 1;

	T[v << 1] = place(tl, mid, lazy[v << 1]);
	T[v << 1 | 1] = place(mid + 1, tr, lazy[v << 1 | 1]);

}

void upd(int v, int tl, int tr, int l, int r, int val) {
	if (tl == l && tr == r) {
		T[v] = place(l, r, val);
		lazy[v] = val;
		return;
	}
	push(v, tl, tr);
	int mid = (tl + tr) >> 1;

	if (l <= mid)
		upd(v << 1, tl, mid, l, min(r, mid), val);
	if (r > mid)
		upd(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, val);

	T[v] = T[v << 1] + T[v << 1 | 1];
	T[v] %= mod;
}

int binpow(int a, int b) {
	int ret = 1;

	while (b) {
		if (b & 1) {
			ret *= a;
			ret %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}

	return ret;
}

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

	nine = binpow(9, mod - 2);

	cin >> n >> q;

	ten[0] = 1;

	for (int i = 1; i <= n; i++) {
		ten[i] = (ten[i - 1] * 10) % mod;
	}

	for (int i = 0; i < 4 * N; i++)
		lazy[i] = -1;

	build(1, 0, n - 1);

	while (q--) {
		int l, r, d;
		cin >> l >> r >> d;

		--l, --r;

		l = n - 1 - l;
		r = n - 1 - r;
		swap(l, r);
		upd(1, 0, n - 1, l, r, d);

		cout << T[1] << '\n';
	}

}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n + 1), b(n);

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

  ll sum = 0;
  for (int i = 0; i < n; i++) {
    int c = min(a[i], b[i]);
    a[i] -= c;
    b[i] -= c;
    sum += c;

    int d = min(a[i + 1], b[i]);
    a[i + 1] -= d;
    b[i] -= d;
    sum += d;
  }
  cout << sum << endl;
}

Measured memory_bytes: 1024
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

const int purp = 18;

pii p[maxn];
int ST[purp + 1];
int cnt[maxn][purp + 1];

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

    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
	string s;
	cin >> s;
	ll a = 0;
	int seen = -1;
	for(char c : s){
	    if(c == '.'){
		seen = 0;
	    }
	    else{
		if(seen >= 0)
		    seen++;
		a*=10;
		a+= c - '0';
	    }
	}
	if(seen == -1)
	    seen = 0;
	while(seen < 9){
	    a*=10, seen++;
	}
	if(a == 0){
	    p[i].F = p[i].S = purp;
	}
	else{
	    while(a % 2 == 0)
		p[i].F++, a/=2;
	    while(a % 5 == 0)
		p[i].S++, a/=5;
	}	
    }
    sort(p, p+n);
    int pt = 0;
    for(int i = 0; i < n; i++){
	while(pt <= min(purp, p[i].F))
	    ST[pt] = i, pt++;
    }
    while(pt <= purp){
	ST[pt] = n;
	pt++;
    }    
    for(int i = n-1; i >= 0; i--){
	for(int j = 0; j <= purp; j++)
	    cnt[i][j] = cnt[i+1][j];
	for(int j = min(purp, p[i].S); j >= 0; j--)
	    cnt[i][j]++;
    }
    
    ll ans = 0;
    for(int i = 0; i < n; i++){
	int s = max(i + 1, ST[max(int(0), purp - p[i].F)]);
	ans+= cnt[s][max(int(0), purp - p[i].S)];
    }
    return cout << ans << endl, 0;
}


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

using ll = long long;
#define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
mint COMB(ll n, ll r) {
  mint ret = 1;
  for(ll i=0; i<r; ++i) ret *= n-i;
  for(ll i=1; i<=r; ++i) ret /= i;
  return ret;
}
int in() {int x; cin>>x; return x;}
string stin() {string s; cin>>s; return s;}
/***** MAIN *****/
signed main() {
  int n = in();
  int k = in();
  ++n;
  mint ans = 0;
  REPS(i,k,n+1) {
    ans += i*(n-i)+1;
  }
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
 
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
 
    ll n, c, k;
    cin >> n >> c >> k;
    map<ll, ll> t;
    rep(i, n) {
        ll T;
        cin >> T;
        ++t[T];
    }
 
    ll res = 0;
    ll left = 0;
    ll current = 0;
    for(auto itr = t.begin(); itr != t.end(); ++itr){
        ll time = itr->first;
        ll num = itr->second;
        if(left == 0){
            res += num / c;
            current += num % c;
            if(current) left = time;
            else left = 0;
        }
        else{
            if(time - left <= k){
                current += num;
                if(current/c) {
                    res += current / c;
                    current %= c;
                    if(current) left = time;
                    else left = 0;
                }
            }
            else{
                ++res;
 
                res += num / c;
                current = num % c;
                if(current) left = time;
                else left = 0;
            }
        }
    }
 
    if(current) res += (current + c - 1) / c;
 
    cout << res << endl;
    
 
    return 0;
}

Measured memory_bytes: 6528
public class Main {
  public static void main(String[] args) {
    int s = new java.util.Scanner(System.in).nextInt();
    int m = s / 60;
    int r = s % 60;
    int h = m / 60;
    int n = m % 60;
    System.out.println(h + ":" + n + ":" + r);
  }
}

Measured memory_bytes: 26184
#include<stdio.h>

int Max(int input[], int size);
int Min(int input[], int size);



int main()
{
	int x;
	int answer;
	int size = 0;
	int input[100] = { NULL };
	
	scanf("%d", &size);
	
	for (int i=0; i < size; i++)
	{
		scanf("%d", &input[i]);
	}

	answer = Max(input, size) - Min(input, size);


	printf("%d", answer);


	return 0;
}

int Max(int input[], int size)
{
	int max = 0;
	for (int i = 0; i < size; i++)
	{
		if (max < input[i])
		{
			max = input[i];
		}
	}
	return max;
}

int Min(int input[], int size)
{
	int min = 1e10;
	for (int i = 0; i < size; i++)
	{
		if (min > input[i])
		{
			min = input[i];
		}
	}
	return min;
}

Measured memory_bytes: 128
n = int(input())
x = list(map(int, input().split()))
x_sort = x.copy()
x_sort.sort()
row = x_sort[n//2 - 1]
high = x_sort[n//2]

for i in range(n):
    if x[i] <= row:
        print(high)
    else:
        print(row)


Measured memory_bytes: 26180
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	int n,x;
	cin>>x>>n;
    map<int,int>m;
    for(int i=0;i<n;i++)
    {
    	int x;
    	cin>>x;
    	m[x]=1;
	}
	int ans=0,val=1005;
    for(int i=0;i<=200;i++)
    {
    	if(m[i]==0&&abs(i-x)<val)
    	val=abs(i-x),ans=i;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::fixed;
using std::pair;
using std::make_pair;
using std::string;
using std::vector;
using std::list;
using std::map;
using std::set; // insert erase find count
using std::queue;
using std::priority_queue;
using std::stack;
/* c++11
#include <tuple>
using std::tuple; 
using std::make_tuple;
using std::get; // tuple std::get<NUM>(t); (0 <= NUM <= 2)
 */

typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, pair<int, int> > PIII;

void print_pq(priority_queue<PIII> pq) {
    while (!pq.empty()) {
        cout << -pq.top().first << " ";
        cout << pq.top().second.first << " ";
        cout << pq.top().second.second << endl;
        pq.pop();
    }
}

void move(priority_queue<PIII> &table, VI &infected) {
    while (!table.empty()) {
        int from = table.top().second.first;
        int to = table.top().second.second;
        if (infected[from] == 1) {
            infected[to] = 1; 
        }
        table.pop();
    }
    return;
}

int count (VI &infected) {
    int ret = 0; 
    for (int i = 0; i < (int)(infected.size()); i++) {
        if (infected[i] == 1) {
            ret++; 
        }
    }
    return ret;
}

int main(void) {
    int n;
    int m;
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0) {
            break;
        }
        priority_queue<PIII> table;
        VI infected(n, false);
        infected[0] = true;
        for (int i = 0; i < m; i++) {
            int t;
            int s;
            int d;
            cin >> t >> s >> d;
            table.push(make_pair(-t, make_pair(s - 1, d - 1))); 
        }
        move(table, infected);
        cout << count(infected) << endl;
    }
    return 0;
}

Measured memory_bytes: 3524
x=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(x[int(input())-1])

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

int main() 
{
    int n;
    cin >> n;
    
    int maxh = 0;
    rep(i,n) {
        int h;
        cin >> h;
        if (h+1 < maxh) {
            cout << "No" << endl;
            return 0;
        }
        maxh = max(maxh, h);
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define LIMIT(d_in, d_min, d_max) max(d_min, min(d_max, d_in))
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	int N;
	cin >> N;

	if (N == 7 || N == 5 || N == 3)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#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;

int main()
{
	int X;
	cin >> X;
	int p, ans = 1;
	for (int i = 2; i < X; ++i)
	{
		int temp = i*i;
		while(temp <= X)
		{
			ans = max(ans,temp);
			temp *= i;
		}
	}
	cout << ans << 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<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
    int n;cin>>n;
    string s,t;
    cin>>s>>t;
    rep(i,n){
        for(int j=0;j<n-i;++j){
            if(s[i]==t[j]){
                bool a=true;
                for(int k=0;k<n-i;++k){
                    if(s[i+k]!=t[j+k]){
                        a=false;
                    }
                }
                if(a){
                    cout<<2*n-(n-i)<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<2*n<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int a,b;
  int i,flag=0;
  scanf("%d %d",&a,&b);
  
  for(i=1;i<1500;i++){
    if(a==i*8/100 && b==i*10/100){
      printf("%d",i);
      flag++;
      break;
    }
  }
  if(flag==0)
    printf("-1");
}

Measured memory_bytes: 128
MOD=int(1e9+7)
n,k=map(int,input().split())
a=sorted(map(int,input().split()))
fac=[1]
for i in range(1,n):
    fac.append((fac[-1]*i)%MOD)

def comb(n,k):
    return (fac[n]*pow(fac[k],MOD-2,MOD)%MOD)*pow(fac[n-k],MOD-2,MOD)%MOD
res=0
for i in range(n-k+1):
    res +=((a[n-1-i]-a[i])*comb(n-1-i,k-1)%MOD)
    res %=MOD
    
print(res)

Measured memory_bytes: 14416
/** Which of the favors of your Lord will you deny ? **/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define F first
#define S second

#define ALL(x)      (x).begin(), (x).end()
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#ifndef ONLINE_JUDGE
#define DBG(x)      cout << __LINE__ << " says: " << #x << " = " << (x) << endl
#else
#define DBG(x)
#endif

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 2e5+7;

int main()
{
    optimizeIO();

    int tc =1 ;

    while(tc--)
    {
        int x;
        cin>>x;

        if(x>=400 && x<=599) cout<<8<<endl;
        if(x>=600 && x<=799) cout<<7<<endl;
        if(x>=800 && x<=999) cout<<6<<endl;
        if(x>=1000 && x<=1199) cout<<5<<endl;
        if(x>=1200 && x<=1399) cout<<4<<endl;
        if(x>=1400 && x<=1599) cout<<3<<endl;
        if(x>=1600 && x<=1799) cout<<2<<endl;
        if(x>=1800 && x<=1999) cout<<1<<endl;
    }

    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}




Measured memory_bytes: 3644
def Isort(a,n):
    for i in range(1,n):
        v = a[i]
        j = i-1
        while j>=0 and a[j]>v:
            a[j+1] = a[j]
            j-=1
        a[j+1] = v
        print(*a)
        
    
n = int(input())
a = list(map(int, input().split()))
print(*a)
Isort(a,n)


Measured memory_bytes: 5980
max_value = 10 ** 18


N = int(input())
A = list(map(int, input().split(' ')))

if 0 in A:
    result = 0
else:
    result = A.pop(0)
    for i in A:
        result = result * i
        if result > max_value:
            result = -1
            break

print(result)


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

long dp[3000][3000][2];

long solve(int start, int end, int minimize, long a[]) {
	if(start > end) return 0;
	if(dp[start][end][minimize] != -1) return dp[start][end][minimize];
	if(minimize) {
		return dp[start][end][minimize] = 
				min(solve(start + 1, end, minimize ^ 1, a) - a[start],
					solve(start, end - 1, minimize ^ 1, a) - a[end]);
	}
	return dp[start][end][minimize] = 
				max(solve(start + 1, end, minimize ^ 1, a) + a[start],
					solve(start, end - 1, minimize ^ 1, a) + a[end]);
}

int main() {
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	long a[n];
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	memset(dp, -1, sizeof dp);
	cout<<solve(0, n - 1, 0, a);
	return 0;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    Scd(N);

    vi a(N);
    vi b(N);
    vi c(N);
    Rep(i,N) Scd(a[i]), a[i]--;
    Rep(i,N) Scd(b[i]);
    Rep(i,N-1) Scd(c[i]);

    int ans = b[a[0]];
    Repe(i,N,1){
        if( a[i] - a[i-1] == 1 ) ans += c[a[i-1]];
        ans += b[a[i]];
    }

    printf ("%d\n", ans );

    return 0;
}





Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vcha;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)

int main() {
	string s, t;
	cin >> s >> t;
	cout << t << s << endl;
	return 0;
}

// abc : 141 , aoj : ITP1_6_D
//sort, abs, swap, reverse, max, min
//__gcd, substring, erase, push_back,stoll、stoi

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

int main () {
  int N ;
  cin >> N ;
  vector<int> line(N) ;
  for(int i = 0 ; i < N ; i++ ) cin >> line[i] ;
  
  int i = 0 ;
  int ans = 0 ;
  while(1) {
    if(i==N-1&&line[i]==0) break ;
    if(line[i]==0) {
      i++ ;
      continue ;
    }
    ans++ ;
    int j = 0 ;
    while(1){
      if(line[i+j]==0) break ;
      line[i+j]--;
      j++ ;
      if(j==N) break ;
    }
  }
  cout << ans << endl ;
}

Measured memory_bytes: 256
n= int(input())
ans= ''
trans= {}
for x in range(1, 27):
	trans[x]= chr(x+96)

while n!=0:
	if n%26==0:
		ans= 'z'+ ans
		n= n//26-1
	else:
		ans= trans[n%26] + ans
		n= n//26
print(ans)

Measured memory_bytes: 9180
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;


const int INF = 10000000;
const long long INFL = (1LL<<40);
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

template< typename T >
struct edge{
    int src, to;T cost;
    edge(int to,T cost) :src(-1),to(to),cost(cost){}
    edge(int src, int to, T cost) :src(src),to(to),cost(cost){}edge
    &operator=(const int &x){
        to =x;
        return *this;
    }
    operator int() const{ return to;}
};



int main() {
    int n,m;cin>>n;
    vector<string>s(n);cin>>s;cin>>m;
    vector<string>t(m);cin>>t;
    
    int maxs = 0;
    for(auto st:s){
        int score = 0;
        for(auto i:s){
            if(st==i) score++;
        }
        for(auto j:t){
            if(st==j)score--;
        }
        maxs = max(maxs,score);
    }
    cout<<maxs<<endl;
    
    
    return 0;
}







Measured memory_bytes: 256
n,y=map(int,input().split())
c=0
for i in range(0,n+1):
    for j in range(0,n-i+1):
        a=y-1000*i-5000*j
        if a%10000==0 and i+j+a//10000==n:
            print(a//10000,j,i)
            exit()
print(-1,-1,-1)

Measured memory_bytes: 40940
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
//N^4的dp，折半变为N^2logN

#define NUM 1005

enum Type{
	A,
	B,
	C,
	D,
};

int N;
ll V;
ll input[NUM][4];
//Type type_array[4] = {A,B,C,D};
map<ll,ll> AB,CD;

int main(){

	scanf("%d %lld",&N,&V);
    
	for(int i = 0; i < 4; i++){
		for(int k = 0; k < N; k++){
			scanf("%lld",&input[k][i]);
		} 
	}

	//AとBの組合わせ
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			AB[input[i][A]+input[k][B]]++;
		}
	}

	//CとDの組合せ
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			CD[input[i][C]+input[k][D]]++;
		}
	}

	ll ans = 0;
	map<ll,ll>::iterator it = AB.begin();

	ll num_AB,num_CD;

	while (it != AB.end()){
	   num_AB = it->first;
	   num_CD = V-num_AB;
	   ans += AB[num_AB]*CD[num_CD];
	   it++;
	}

	printf("%lld\n",ans);

	return 0;
}

 


Measured memory_bytes: 190696
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

const int MAXN = 100000 + 10;

int N;
int a[MAXN];

int Work()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i ++)
		scanf("%d", &a[i]);
	int ma = a[0], mi = a[0];
	for (int i = 0; i < N; i ++)
	{
		ma = max(ma, a[i]);
		mi = min(mi, a[i]);
	}
	if (ma - mi >= 2)
		return 0;

	if (mi == ma)
	{
		return (mi == N - 1) || (mi <= N / 2);
	}

	int dandu = 0;
	for (int i = 0; i < N; i ++)
		if (a[i] == mi)
			dandu ++;
	int budandu = N - dandu;

	if (budandu == 0)
		return (mi == N - 1);
	if (budandu == 1)
		return 0;

	int posmin = dandu + 1;
	int posmax = dandu + budandu / 2;
	return (posmin <= ma && ma <= posmax);
}

int main()
{
	printf(Work() ? "Yes\n" : "No\n");
	return 0;
}

Measured memory_bytes: 512
s = input()
a = []
for i in range(len(s)) :
	if s[i] == '0' :
		a.append(0)
		
	elif s[i] =='1' :
		a.append(1)
	elif s[i] == 'B' :
		if len(a)>0 :
			a.pop()
print(''.join(map(str,a)))

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

using I = long long;
using U = unsigned long long;

using F = long double;

template <typename T> using Vec = vector<T>;
template <typename K, typename V> using HashMap = unordered_map<K, V>;
template <typename T> using HashSet = unordered_set<T>;
template <typename T> using PQueue = priority_queue<T>;
template <typename T> using Uq = unique_ptr<T>;

using StrView = string_view;

auto solve(Vec<I> const H, Vec<I> const M, I const K) -> void {
  I start = H[0] * 60 + M[0];
  I end = H[1] * 60 + M[1];
  I result = end - start - K;
  if (result < 0) {
    result = 0;
  }
  cout << result << "\n";
}

auto main() -> int {
  Vec<I> H(2);
  Vec<I> M(2);
  for (I i = 0; i < 2; ++i) {
    scanf("%lld", &H[i]);
    scanf("%lld", &M[i]);
  }
  I K;
  scanf("%lld", &K);
  solve(move(H), move(M), K);
  return 0;
}


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

typedef long long ll;

#define REP(i, N) for (int i = 0; i < (int)(N); i++)

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

const ll MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    
    bool flg = true;
    ll ans = 1LL;
    ll x = 0, y = 0, z = 0;
    REP(i,N){
        if ( x == y and y == z and A[i] == x ){
            ++x;
            ans = ( ans * 3LL ) % MOD;
        } else if ( x == y and y != z ) {
            if ( A[i] == x ) {
                ++x;
                ans = ( ans * 2LL ) % MOD;
            } else if ( A[i] == z ) {
                ++z;
            } else {
                flg = false;
                goto OUT;
            }
        } else if ( y == z and x != y ) {
            if ( A[i] == x ) {
                ++x;
            } else if ( A[i] == y ) {
                ++y;
                ans = ( ans * 2LL ) % MOD;
            } else {
                flg = false;
                goto OUT;
            }
        } else if ( x!=y and y!=z and z!=x) {
            if ( A[i] == x ) {
                ++x;
            } else if ( A[i] == y ) {
                ++y;
            } else if ( A[i] == z ) {
                ++z;
            } else {
                flg = false;
                goto OUT;
            }
        } else {
            flg = false;
            goto OUT;
        }
    }
    OUT:

    if ( flg ){
        ans = ans % MOD;
        if ( ans < 0 ) ans += MOD;
        
        cout << ans << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 3776
A,B,C = map(int,input().split())
N = A*B*C
cmin = N
cmin = min(cmin,abs(2*(A//2)*B*C-N))
cmin = min(cmin,abs(2*(B//2)*C*A-N))
cmin = min(cmin,abs(2*(C//2)*A*B-N))
print(cmin)

Measured memory_bytes: 61648
#include<stdio.h>
#include<math.h>
#include<string.h>

int main()
{
	int K;
	int A, B;
	scanf("%d", &K);
	scanf("%d %d", &A, &B);
	
	int r;
	int c = 0;
	for(r=A; r<=B; r++){
		if(r % K == 0){
			c = 1;
			break;
		}
	}
	
	if(c == 0) printf("NG");
	else printf("OK");
	
	return 0;
	
}

Measured memory_bytes: 1736