akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#define rep(i,n) for(int i = 0;i<(n);++i)
typedef long long ll;
using namespace std;

// auto mod int

// https://youtu.be/L8grWxBlIZ4?t=9858

// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize

// https://youtu.be/8uowVvQ_-Mo?t=1329 : division

const int mod = 1000000007;

struct mint {

	ll x; // typedef long long ll;

	mint(ll x = 0) :x((x% mod + mod) % mod) {}

	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 {

		mint res(*this);

		return res += a;

	}

	mint operator-(const mint a) const {

		mint res(*this);

		return res -= a;

	}

	mint operator*(const mint a) const {

		mint res(*this);

		return res *= 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 {

		mint res(*this);

		return res /= a;

	}

};

// combination mod prime


struct combination {

	vector<mint> fact, ifact;

	combination(int n) :fact(n + 1), ifact(n + 1) {

		assert(n < mod);

		fact[0] = 1;

		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;

		ifact[n] = fact[n].inv();

		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;

	}

	mint operator()(int n, int k) {

		if (k < 0 || k > n) return 0;

		return fact[n] * ifact[k] * ifact[n - k];

	}

};

int main() {
	int x, y;
	cin >> x >> y;
	if ((x + y) % 3) {
		cout << 0 << endl;
		return 0;
	}
	int n = (x + y) / 3;
	x -= n; y -= n;
	if (x < 0 || y < 0) {
		cout << 0 << endl;
		return 0;
	}
	combination c(x + y);
	mint ans = c(x + y, x);
	cout << ans.x << endl;
	
	return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(10) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    vector<double> x(n), y(n);
    vector<char> d(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i] >> d[i];

    auto f = [&](const ld t) {
        pair<double, double> dx, dy;
        for (int i = 0; i < n; ++i) {
            double vx = x[i], vy = y[i];

            if (d[i] == 'R') vx += t;
            else if (d[i] == 'L') vx -= t;
            else if (d[i] == 'U') vy += t;
            else if (d[i] == 'D') vy -= t;

            if (i == 0) {
                dx = make_pair(vx, vx);
                dy = make_pair(vy, vy);
            }
            else {
                dx.first = min(dx.first, vx);
                dx.second = max(dx.second, vx);
                dy.first = min(dy.first, vy);
                dy.second = max(dy.second, vy);
            }
        }
        return (dx.second - dx.first) * (dy.second - dy.first);
    };

    double min_v = f(0), lb = 0, ub = 1e9;
    for (int i = 0; i < 200; ++i) {
        const double t1 = (2.0 * lb + ub) / 3.0;
        const double t2 = (lb + 2.0 * ub) / 3.0;

        min_v = min(min_v, f(t1));
        min_v = min(min_v, f(t2));

        if (f(t1) > f(t2)) lb = t1;
        else ub = t2;
    }

    cout << min_v << endl;

    return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int N, M;

struct edge {
    int to; // 次の頂点.
    int d;  // 距離.
    bool operator < (const edge &E) const { return d > E.d; }
};

int dist[101][101];    // 頂点(i, j) の 最短距離 を 保存.
vector<edge> graph[1001];

// https://ja.wikipedia.org/wiki/ダイクストラ法
// グラフを最良優先探索する.
// ※dijkstraの動作確認用.
// @param s: 今回探索する頂点番号.
// @return: 特に無し.
void dijkstra(int s) {
    
    // 1. 初期化.
    priority_queue<edge> pq;
    
    // 2. 始点設定.
    dist[s][s] = 0;
    pq.push({s, 0});

    // 3. キュー pq が 空になるまで, 探索.
    while(!pq.empty()){
        // 4. 探索を継続するために, 頂点を取得.
        int u = pq.top().to;
        int d = pq.top().d;
        pq.pop();
        
        // 5. より小さい距離が設定済みなら, Skip.
        if(dist[s][u] < d) continue;

        // 6. 各隣接する頂点について, 距離を確認し, 最短経路を更新.
        for(int i = 0; i < graph[u].size(); ++i){
            int nu = graph[u][i].to;
            int nd = d + graph[u][i].d;
            // 最短経路更新.
            if(dist[s][nu] > nd) dist[s][nu] = nd, pq.push({nu, nd});
        }
    }
}

int main() {

    // 1. 入力情報取得.
    scanf("%d %d", &N, &M);
    map<pair<int, int>, int> m; // 二頂点間の距離を保存.
    for(int i = 0; i < M; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        if(a > b) swap(a, b);
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
        m[{a, b}] = c;
    }
    
    // 2. 各二頂点間の最短経路を求める(ダイクストラ法).
    int ans = 0;
    for(int i = 0; i < 101; i++) for(int j = 0; j < 101; j++) dist[i][j] = INF;
    for(int i = 0; i < N - 1; i++){
        dijkstra(i);
        for(int j = i + 1; j < N; j++){
            // 始めに保存した二頂点間の距離が, 最短経路探索後の二頂点間の距離と異なっているのであれば, 
            // この辺は, 最短経路に含まれてないと判定.
            if(m[{i, j}] > 0 && m[{i, j}] != dist[i][j]) ans++;
            // printf("m[{%d, %d}]=%d dist[%d][%d]=%d\n", i, j, m[{i, j}], i, j, dist[i][j]);
        }
    }
    
    // 3. 出力 ～ 後処理.
    printf("%d\n", ans);
    return 0;
    
}

Measured memory_bytes: 640
#include<stdio.h>
#include<math.h>
int main(){
	int d,n,i,j,m,max=0;
	int a[201],b[201],c[201],t[201],dp[201][201]={0};
	scanf("%d%d",&d,&n);
	for(i=0;i<d;i++)scanf("%d",&t[i]);
	for(j=0;j<n;j++)scanf("%d%d%d",&a[j],&b[j],&c[j]);
	for(j=0;j<n;j++)for(i=0;i<d;i++)if(t[i]<a[j] || b[j]<t[i])dp[i][j]=-1;
	for(i=0;i<d;i++){
		for(j=0;j<n;j++){if(dp[i][j]!=-1){
				for(m=0;m<n;m++){if(dp[i+1][m]!=-1){
					if(dp[i+1][m]<abs(c[m]-c[j])+dp[i][j])dp[i+1][m]=abs(c[m]-c[j])+dp[i][j];
				}}
		}}
	}
	for(i=0;i<d;i++)for(j=0;j<n;j++)if(max<dp[i][j])max=dp[i][j];
	printf("%d\n",max);
	return 0;
}



Measured memory_bytes: 2048
#include<bits/stdc++.h>
#define ll long long
#define F(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define i64 int64_t
#define fi first
#define se second
using namespace std;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	ll x,res=0;
	cin>>x;res+=1000*(x/500);x%=500;res+=5*(x/5);
	cout<<res;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAXH 1000
#define MAXW 1000
#define MOD 1000000007

char grid[MAXH][MAXW+1];
int dp[MAXH][MAXW];
int h, w;


int main() {
  int i,j;
  int suma;
  int val;
  scanf("%d %d%*c",&h,&w);
  for (i=0; i<h; i++) {
    scanf("%s",grid[i]);
  }
  dp[0][0]=0;
  val=1;
  for (j=1; j<w; j++) {
    if (grid[0][j]=='.') {
      dp[0][j]=val;
    }
    else {
      dp[0][j]=-1; val=0;
    }
  }
  val=1;
  for (i=1; i<h; i++) {
    if (grid[i][0]=='.') {
      dp[i][0]=val;
    }
    else {
      dp[i][0]=-1; val=0;
    }
  }
  for (i=1; i<h; i++) {
    for (j=1; j<w; j++) {
      if (grid[i][j]!='#') {
        if (dp[i-1][j]==-1) {
          suma=0;
        }
        else {
          suma = dp[i-1][j];
        }
        if (dp[i][j-1]!=-1) {
          suma+=dp[i][j-1];
        }
        if (suma>MOD) {
          suma -= MOD;
        }
        dp[i][j]=suma;
      }
      else {
        dp[i][j]=-1;
      }
    }
  }

  printf("%d\n",dp[h-1][w-1]);
  return 0;
}

Measured memory_bytes: 8624
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)
    if m-2-ma>=k-1:
        tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)

Measured memory_bytes: 96104
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long k,a,b;
	cin>>k>>a>>b;
	k++;
	if(b<=a+1 || k<=a+1)
	{
		cout<<k<<'\n';
		return 0;
	}
	cout<<a+(k-a)/2*(b-a)+(k-a)%2<<'\n';
}


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

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

    vector<long long> v(N, 0);

    for(int i = 0; i < N; i++)
    {
        long long t;
        cin >> t;
        v[i] = t;
    }

    sort(v.begin(), v.end());

    int cnt = 0;
    for(int i = 0; i < v.size()-1; i++)
    {
        if(v[i] == v[i+1])
        {
            cnt += 2;
            i++;
        }
    }

    cout << N-cnt << endl;

    return 0;
}

Measured memory_bytes: 1024
import math

n, k = map(int, input().split())

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = pow(k//t,n,moddo)
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

print(ans)

Measured memory_bytes: 83788
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, R, G, perf;
  cin >> R >> G;
  a = R; // left is assigned? right is value?
  b = (2 * G) - a; // b = [ ], so left?
  perf = b;
  cout << perf << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long n,a,b,num,p;
int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	if (a+b>n) {
	  printf("%lld",min(n,a));
	  return 0;
	}
	num=(long long)n/(a+b);
	p=(long long)n%(a+b);
	if (!p) printf("%lld",(long long)num*a);
	else printf("%lld",(long long)num*a+min(p,a));
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<set>
#include<map>
#include<bitset>
#include<ctime>
#include<queue>
using namespace std;
#define int long long
#define pii pair <int, int>
#define XX first
#define YY second

// constants:
const int mn = 200005;
const int mod = 1000000007;
const long long inf = 4444444444444444444;
const int sminf = 1111111111;
const bool is_multitest = 0;
const bool is_interactive = 0;

// i/o methods:
const bool input_from_file = 0;
const bool output_to_file = 0;
#define filename ""
#define in_extension "inp"
#define out_extension "out"

// data preprocessing: (e.g.: divisor generating, prime sieve)
void preprocess()
{
  
}

// global variables:
bool n;
// main solution goes here:
void execute(int test_number)
{
  cin>>n;
  cout<<(!n);
}
// REMEMBER TO CHOOSE TEST METHODS
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS
// Solution by low_



















signed main()
{
#ifdef lowie
    if (!is_interactive)
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
#else
    if (input_from_file) freopen(filename"."in_extension, "r", stdin);
    if (output_to_file) freopen(filename"."out_extension, "w", stdout);
#endif
    if (!is_interactive)
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }

    preprocess();
    int ntest;
    if (is_multitest) cin >> ntest;
    else ntest = 1;

    for (int testno = 1; testno <= ntest; testno++)
    // use for instead of while to serve facebook hacker cup test format
    {
        execute(testno); // only start coding in this function, not in main
    }
}
// Template by low_
// Contact me via mail: ttuandung1803@gmail.com
// ...or codeforces: https://www.codeforces.com/profile/low_
// ...or linkedIn: https://www.linkedin.com/in/daniel-to-83045a19a/
// I use VS Code. Here's a JSON format for my template: https://pastebin.com/xH2yRdwx


Measured memory_bytes: 3640
from sys import stdin
a = int(stdin.readline().rstrip())
b = int(stdin.readline().rstrip())
c = int(stdin.readline().rstrip())
x = int(stdin.readline().rstrip())
y = 0

for p in range(a+1):
   if 500*p > x:
      break
   for q in range(b+1):
      if 500*p + 100*q > x:
         break
      for r in range(c+1):
         if 500*p + 100*q + 50*r > x:
            break
         if 500*p + 100*q + 50*r == x:
            y += 1

print(y)

Measured memory_bytes: 68824
while True:
    n = input().split(" ")
    H = int(n[0])
    W = int(n[1])
    
    if H == 0 and W == 0:
        break
    
    for i in range(W):
        print("#",end="")
    print()
    for j in range(H-2):
        print("#",end="")
        for k in range(W-2):
            print(".",end="")
        print("#",end="")
        print()
    for l in range(W):
        print("#",end="")
    print("\n")


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

signed main(void)
{
	int m1, m2, d1, d2;
	cin >> m1 >> d1 >> m2 >> d2;
	if (m1 != m2)
		cout << 1 << endl;
	else
		cout << 0 << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
if N%2==1:
    print(0)
else:
    n = N//2
    a = n
    cnt = 0
    while a>1:
        cnt += a//2
        a = a//2
    a = cnt
    b = n
    cnt = 0
    while b>1:
        cnt += b//5
        b = b//5
    b = cnt
    c = n
    cnt = 0
    while c>1:
        cnt += c//10
        c = c//10
    c = cnt
    n2 = a-c+n
    n5 = b-c
    print(c+min(n2,n5))

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

int main()
{
    int n;cin>>n;
    vector<ll> a(n);
    ll sum = 0;
    ll sum2 = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
        a[i] *= 2;
        if(i % 2 == 0) sum2 += a[i];
    }
    ll k = sum2 - sum;
    for(int i = 0; i < n; i++) {
        cout << k << " ";
        k = a[i] - k;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 2048
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
using namespace std;

int main() {
	ll n = 0, k = 0,ans = 0;
	ll kbaisu = 0;
	ll amari = 0;
	cin >> n >> k;
	kbaisu = n / k;
	if (k % 2 == 1) {
		//全部Kの倍数ならおｋ。
		cout << kbaisu * kbaisu * kbaisu << endl;
		return 0;
	}
	else {
		//全部Kの倍数または、全部kでわったあまりがk/2ならおｋ。
		for (int i = 1; i <= n; i++) {
			if (i%k == (k / 2)) {
				amari++;
			}
		}
		cout << (kbaisu * kbaisu * kbaisu) + (amari * amari * amari) << endl;
		return 0;
	}
	return 0;

}

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

int main(){

  int n, i, t, h, ans=1;
  double a, min, c;

  scanf("%d %d %lf %d", &n, &t, &a, &h);

  min=fabs(a-(t-h*0.006));

  for(i=1;i<n;i++){
    scanf("%d", &h);
    c=fabs(a-(t-h*0.006));
    if(min>c){
      min=c;
      ans=i+1;
    }
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
n,m=map(int,input().split())
L=[]
R=[]
for i in range(m):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
a=max(L)
b=min(R)
li=[i for i in range(a,b+1)]
print(len(li))



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

const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 5;

ll modpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b&1)
      res = (res * a) % MOD;
    a = (a * a) % MOD;
    b >>= 1;
  }
  return res;
}

ll f[MAXN];
ll invf[MAXN];

ll ncr(ll n, ll r) {
  if (r == 0 || n == r) return 1;
  return (((f[n] * invf[n-r]) % MOD) * invf[r]) % MOD;
}

int main() {
  int h, w, a, b;
  cin >> h >> w >> a >> b;
  f[0] = 1;
  for (int i = 1; i < MAXN; i++) {
    f[i] = (f[i-1] * i) % MOD;
    invf[i] = modpow(f[i], MOD-2);
  }
  ll res = 0;
  for (int i = b; i < w; i++) {
    int y1 = h - a - 1, x1 = i;
    int y2 = a - 1, x2 = w - i - 1;
    ll p = (ncr(x1 + y1, x1) * ncr(x2 + y2, x2)) % MOD;
    res = (res + p) % MOD;
  }
  cout << res << '\n';
}

Measured memory_bytes: 19236
#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5+5 , M = 998244353, OO = 0x3f3f3f3f;
typedef long long ll;
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);
const double Pii = 3.14159265359;
ll n;
ll a[N], b[N];

int main()
{
    FIO
    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 == 1) cout << b[n/2]-a[n/2]+1 << endl;
    else cout << b[n/2-1]+b[n/2]-a[n/2-1]-a[n/2]+1 << endl;
    return 0;
}


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

ll n;
string s;

string calc_ans(string fs) {
	for (ll i = 1; i < n - 1; ++i) {
		if ((s[i] == 'o') ^ (fs[i] == 'W') ^ (fs[i - 1] == 'S')) {
			fs.push_back('W');
		}
		else {
			fs.push_back('S');
		}
	}
	return fs;
}

bool check_ans(string ans) {
	if ((s[n - 1] == 'o') ^ (ans[n - 1] == 'W') ^ (ans[n - 2] == ans[0]))return false;
	if ((s[0] == 'o') ^ (ans[0] == 'W') ^ (ans[n - 1] == ans[1]))return false;
	return true;
}

int main() {
	cin >> n >> s;
	for (string fs : {"SS", "SW", "WS", "WW"}) {
		string ans = calc_ans(fs);
		if (check_ans(ans)) {
			cout << ans << endl;
			return 0;
		}
	}
	cout << -1 << endl;
}


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

int main(){
    int n, x;
    cin >> n >> x;
    int sum = 0;
    int minm = 2000;
    for(int i = 0; i < n; i++){
        int m;
        cin >> m;
        sum += m;
        if(minm > m) minm = m;
    }

    cout << n + (x-sum)/minm << endl;
    return 0;
}

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

#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;


int main()
{
    string s;
    cin >> s;
    if (s == "SUN") cout << 7 << endl;
    if (s == "MON") cout << 6 << endl;
    if (s == "TUE") cout << 5 << endl;
    if (s == "WED") cout << 4 << endl;
    if (s == "THU") cout << 3 << endl;
    if (s == "FRI") cout << 2 << endl;
    if (s == "SAT") cout << 1 << endl;
    return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn=1e5+5;
char s[maxn],t[maxn];
vector<int>pos[30];
int main()
{
	int lens,lent,cur=0;
	long long ans=0;
	vector<int>::iterator it;
	scanf("%s%s",s,t);
	lens=strlen(s);
	lent=strlen(t);
	for(int i=0;i<lens;i++)
		pos[s[i]-'a'].push_back(i+1);
	for(int i=0;i<lent;i++){
		if(!pos[t[i]-'a'].size())
			return puts("-1")&0;
		it=upper_bound(pos[t[i]-'a'].begin(),pos[t[i]-'a'].end(),cur);
		if(it==pos[t[i]-'a'].end()){
			ans+=lens-cur+pos[t[i]-'a'][0];
			cur=pos[t[i]-'a'][0];
		}else{
			ans+=*it-cur;
			cur=*it;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1024
# 1
# 4 8 16 32 64 128 256 512
# 9 27 81 243 729
# 14 64 256
# 25 125 625
# 36 216
# 49 343
# 64 512
# 81 729
# 100
# 121
# .. 
# 961

X = int(raw_input())

array = []
num=1
i=1
p=2
while i <= 31:
    p = 2
    while p < 9:
        tmp = pow(i, p);
        if tmp <= 1000:
            array.append(tmp)
        else:
            break

        p = p +1
    i = i+1
        
array.sort()
array.reverse()

#print array

for item in array:
    if X < item:
        continue
    else:
        print item
        break


Measured memory_bytes: 2568
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 1e18;
constexpr ll MOD = 998244353;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;
 
template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}
 
ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}
 
ll RepeatSquaring(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P%2==0){
        ll t = RepeatSquaring(N, P/2, M);
        return t*t % M;
    }
    return N * RepeatSquaring(N, P-1, M) % M;
}

int main() {
    int N;
    cin >> N;
    if(N % 10 == 3) {
        cout << "bon" << endl;
    }
    else if(N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8) {
        cout << "pon" << endl;
    }
    else {
        cout << "hon" << endl;
    }
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include<unordered_map>
#define ll long long
#define BUF 50
using namespace std;
ll MOD = 1e9 + 7;
ll A, B, H, N, M, L, K, P, Q, R, W, X, Y, Z;
ll ans = 0;

int main() {
	string S;
	cin >> S;
	bool flag = 0;
	if (S[0] == 'A') {
		int cn = 0, tmp;
		for (int i = 2; i < S.size() - 1; i++) {
			if (S[i] == 'C') {
				cn++; tmp = i;
			}
		}
		if (cn == 1) {
			int i;
			for (i = 1; i < S.size(); i++) {
				if (tmp == i)continue;
				if (S[i] >= 'a'&&S[i] <= 'z')continue;
				break;
			}
			if (i ==S.size())flag++;
		}
	}
	if (flag)cout << "AC";
	else cout << "WA";
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#define INF 1000000000
using namespace std;
typedef pair<int,int> pa;

int pri[5010],god[5010],dp[5010];
vector<int> pat[5010];

void bfs(int n,set<int> &can){
	queue<pa > que;
	pa tmp;
	can.clear();
	que.push(pa(0,n));
	while(!que.empty()){
		tmp=que.front();que.pop();
		if(god[n]<tmp.first||can.count(tmp.second)) continue;
		can.insert(tmp.second);
		for(auto it=pat[tmp.second].begin();it!=pat[tmp.second].end();it++){
			que.push(pa(tmp.first+1,*it));
		}
	}
}

int main(){
	int N,K;
	cin>>N>>K;
	for(int i=1;i<=N;i++){
		cin>>pri[i]>>god[i];
	}
	int a,b;
	for(int j=1;j<=K;j++){
		cin>>a>>b;
		pat[a].push_back(b);
		pat[b].push_back(a);
	}
	fill(dp,dp+N+1,INF);

	pa tmp;set<int> stmp;
	priority_queue<pa,vector<pa>,greater<pa>> pque;
	pque.push(pa(0,1));
	while(!pque.empty()){
		tmp=pque.top();pque.pop();
		if(dp[tmp.second]==INF){
			dp[tmp.second]=tmp.first;
			if(tmp.second==N) break;
			bfs(tmp.second,stmp);
			for(auto it=stmp.begin();it!=stmp.end();it++){
				if(dp[*it]==INF)pque.push(pa(pri[tmp.second]+tmp.first,*it));
			}
		}
	}

	cout<<dp[N]<<endl;
	return 0;
}

Measured memory_bytes: 69096
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <numeric>
#include <sstream>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main() {
#ifdef RUN_LOCAL
  ifstream in("../input.txt");
  cin.rdbuf(in.rdbuf());
#endif

  cin.tie(0);
  ios::sync_with_stdio(false);
  int k;
  cin >> k;
  int a, b;
  cin >> a >> b;
  for (int i = a; i <= b; ++i)
  {
    if (i % k == 0) {
      cout << "OK" << endl;
      return 0;
    }
  }

  cout << "NG" << endl;



  return 0;
}


Measured memory_bytes: 3124
N, A, B = map(int, input().split())

if abs(A - B) % 2 == 0:
    print(abs(A - B) // 2)
else:
    ans_1 = [min(N - min(A, B), max(A, B) - 1)]
    go_hasi_and_tame = min(A - 1, N - B) + 1
    ans_1.append(abs(1 - B - go_hasi_and_tame) // 2)
    ans_1.append(abs(N - (A - go_hasi_and_tame)) // 2)

    print(min(ans_1))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define mod 1000000007
#define ull unsigned ll
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pi acos(-1)
#define nui 100
#define INF 100000000000
 
#define F(i,a,n) for(ll i=a;i<n;i++)
#define B(i,a,n) for(ll i=n-1;i>=a;i--)
#define tc int t;cin>>t;while(t--)
#define tcf int t;cin>>t;for(int w=1;w<=t;w++)
 
 
 
using namespace std;
 
 
ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}
 
ll fermat_inv(ll y) {return binpow(y, mod - 2);}
 
/*vector<ll>adj[100001];
vector<bool>visited(100001, 0);
vector<ll>parent(100001, 0);
vector<ll>a(100001, 0);
 
void dfs(ll node)
{
    visited[node] = 1;
    for (auto i : adj[node])
    {
        if (!visited[i])
        {
            dfs(i);
            a[node] += a[i];
            parent[i] = node;
        }
    }
}*/
int main()
{
 
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    ll x;
    cin>>x;
    if(x>=30)
    {
        cout<<"Yes\n";
    }
    else
    {

        cout<<"No\n";
    }
 
    return 0;
 
 
 
 
 
}
 
 
 

Measured memory_bytes: 3632
#include <cstdio>
int n,a[]={0,1,2,12,84,770,8340,106400,1546888,25343766,461133960,232367169,627905865,632459808,928262728,919805769,382796331,887217496,639768068,869694124,205875097,205589953,487772376,239955313,998339621,31622834,902930073,146839084,449786840,982224660,865803735,21834818,721531716,26008837,471774471,69010090,700009308,776938882,645550477,526939604,142728157,654489641,128201240,185493259,789721045,977049419,589149550,700648836,25087729,874433491,352791804};
int main(){return scanf("%d",&n),printf("%d\n",a[n]),0;}

Measured memory_bytes: 128
x,y,a,b,c = map(int,input().split())
p = sorted([int(x) for x in input().split()])[::-1][:x]
q = sorted([int(x) for x in input().split()])[::-1][:y]
r = [int(x) for x in input().split()]
row = sorted(p+q+r)[::-1]
print(sum(row[:x+y]))

Measured memory_bytes: 27424
n,m= list(map(int, input().split()))
ab=[list(map(int,input().split())) for _ in range(n)]
cd=[list(map(int,input().split())) for _ in range(m)]
for a,b in ab:
    kyori=1000000007
    ans=0
    for i,v in enumerate(cd):
        now=abs(a-v[0])+abs(b-v[1])
        if kyori>now:
            kyori=now
            ans=i
    print(ans+1)

Measured memory_bytes: 3064
import java.util.*;

public class Main  {
    static int[] arr;
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        arr = new int[n];
        for (int i = 1; i <= n; i++) {
            arr[i - 1] = i;
        }

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {

            a[i] = in.nextInt();

        }

        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = in.nextInt();
        }

        if (eq(a, b)) {
            System.out.println(0);
            return;
        }

        int first = -1;
        int second = -1;


        int times = 1;

        while (true) {


            if (eq(a, arr)) {
                first = times;
            } else if (eq(b, arr)) {
                second = times;
            }

            if (first != -1 && second != -1) {
                break;
            }

            if (!nextPermutation()) {
                break;
            }
            times++;



        }

        System.out.println(Math.abs(first - second));


    }
    static boolean nextPermutation() {
        int i = arr.length - 1;
        while (i > 0 && arr[i - 1] >= arr[i]) {
            i--;
        }
        if (i <= 0) {
            return false;
        }
        int j = arr.length - 1;
        while (arr[j] <= arr[i - 1]) {
            j--;
        }
        swap(i-1, j);
        j = arr.length - 1;
        while (i < j) {
            swap(i, j);
            i++;
            j--;
        }
        return true;
    }//NP

    static void swap(int i, int j) {

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;

    }


    static boolean eq(int[] a, int[] b) {


        for (int i = 0; i < a.length; i++) {

            if (a[i] != b[i]) {
                return false;
            }

        }
        return true;


    }


}


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

#define mp make_pair
#define pb push_back

#define int int64_t

const int MOD = 1e9+7;
 
int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

 	int n;
 	cin>>n;
 	cout<<n*n;   

	return 0;
}

Measured memory_bytes: 256
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k = nm()
p = nl()

def exp(num):
  ret = (1+num)/2
  return ret

mx=0

pp = list(map(exp,p))
pd = [0]*(n+1)



for i in range(1,n+1):
  pd[i] = pd[i-1] + pp[i-1]




for i in range(n-k+1):
  mx = max(pd[i+k]-pd[i],mx)

print(mx)

Measured memory_bytes: 24804
#include<iostream>
using namespace std;
int A[100100],B[100100];
int main()
{
  int N;
  long long ans=0;
  cin>>N;
  for(int i=0;i<=N;i++)
    cin>>A[i];
 for(int i=0;i<N;i++)
   	cin>>B[i];
  for(int i=0;i<N;i++)
  {
    int h1=min(A[i],B[i]);
    ans+=h1;
    B[i]-=h1;
    int h2=min(A[i+1],B[i]);
    ans+=h2;
    A[i+1]-=h2;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1024
n, a, b = list(map(int, input().split()))

if (a-b) % 2 == 0:
    print(abs(a-b)//2)
else:
    x = ((a-1) + (b-1) + 1)//2
    y = ((n-a) + (n-b) + 1)//2
    print(min(x, y))


Measured memory_bytes: 3060
import itertools
import math
n = int(input())
x,y = [],[]
for _ in range(n):
  a,b = map(int,input().split())
  x.append(a)
  y.append(b)

pat = itertools.permutations(range(n),n)
distsum = 0
for k in pat:
  dist = 0
  for i in range(n-1):
    dist += ((x[k[i+1]]-x[k[i]])**2+(y[k[i+1]]-y[k[i]])**2)**(1/2)
  distsum += dist
print(distsum/math.factorial(n))

Measured memory_bytes: 9456
import collections

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]

ans = sum(A)
d = collections.defaultdict(int)

for key in A:
    d[key] += 1

for i in range(Q):
    b,c = BC[i][0],BC[i][1]
    ans += d[b]*(c-b)
    d[c] += d[b]
    d[b] = 0
    print(ans)

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

int main(){
    string s;cin>>s;
    int remains = 15 - s.size();
    int need_to_win = 8 - remains;
    int acc = 0;
    for (auto c: s){
        if (c == 'o'){
            acc++;
        }
    }
    if (acc >= need_to_win){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a+b==c || a+c==b || b+c==a)	{
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
/*
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int mint; //*/
#include <bits/stdc++.h>
#define  re(i,j,n) for(li i=(j);i<(n);i++)
#define  rep(i,n) re(i,0,(n))
#define  red(i,n) for(li i=n-1;i>=0;i--)
#define  all(a) begin(a),end(a)
#define  pb(a) push_back(a)
using namespace std;
typedef long int li;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<string> vs;
 
 
int main()
{
    int n;
    cin>>n;
    int a[n],sum=0;
    rep(i,n) cin>>a[i],sum+=a[i];
    if(sum%10) cout<<sum<<endl;
    else {
        sort(a,a+n);
        rep(i,n) if(a[i]%10) cout<<sum-a[i]<<endl, exit(0);
        cout<<0<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = sum(A)
D = make_divisors(D)[::-1]

for d in D:
    a = []
    for i in range(N):
        if A[i]%d != 0:
            a.append(A[i]%d)
    a.sort()
    b = [d-x for x in a]
    b.sort()

    c1 = [0]*(len(a)+1)
    for i in range(len(a)):
        c1[i] = a[i]+c1[i-1]
    c2 = [0]*(len(b)+1)
    for i in range(len(b)):
        c2[i] = b[i]+c2[i-1]

    k = float('inf')
    for i in range(len(a)):
        if c1[i] == c2[len(a)-2-i]:
            k = c1[i]
            break
    if k <= K:
        break
print(d)

Measured memory_bytes: 43612
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)
	s.Scan()
	n, _ := strconv.Atoi(s.Text())
	s.Scan()
	a, _ := strconv.Atoi(s.Text())
	s.Scan()
	b, _ := strconv.Atoi(s.Text())

	if n*a > b {
		fmt.Println(b)
	} else {
		fmt.Print(a * n)
	}
}


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

using namespace std;

const int MAXN = 1000;

int arr[MAXN+1];
int max(int p,int q){return p>q?p:q;
}

int main()
{
	int n,m,k,c;
	
	scanf("%d%d%d%d",&n,&m,&c,&k);
	
	int a = max(n,max(m,c));
	
	int base=1;
	for(int i=0;i<k;i++)
	{
		base*=2;
	}
	
	printf("%d",a*base+n+m+c-a);
	
	return 0;
}

Measured memory_bytes: 256
// c++include
#include <iostream>
#include <algorithm>
// cinclude
#include <stdio.h>
#include<string.h>
#include<math.h>
//c++標準ライブラリ
#include<vector>
#include<string>
//std使用<-namespace
using namespace std;

// define, typedef
#define rpt(i, n) for(ll i = 0; i < (n); i++)
typedef long long ll;

//素因数分解
vector<vector<ll>> factorsize(ll n) {
	vector<vector<ll>> res;
	for (ll i = 2; i * i <= n; i++) {
		if (n % i != 0) {
			continue;
		}
		else {
			vector<ll> fs{ i, 0 };
			while (n % i == 0) {
				n /= i;
				fs[1]++;
			}
			res.push_back(fs);
		}
	}
	if (n != 1) {
		vector<ll> gs{ n, 1 };
		res.push_back(gs);
	}
	return res;
}

// 最大公約数
ll gcd(ll a, ll b) {
	if (a % b == 0) {
		return b;
	}
	else {
		gcd(b, a % b);
	}
}

// main関数
int main(void) {
	ll a, b, tmp;
	cin >> a >> b;
	if (a <= b) {
		tmp = a;
		a = b;
		b = tmp;
	}
	ll c = gcd(a, b);
	vector<vector<ll>> fs;
	fs = factorsize(c);
	cout << fs.size() + 1;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define endl "\n"
#define all(a) a.begin(),a.end()
#define debug(x) cout << x << endl;
#define int long long
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
/* 	1) order_of_key (k) : Number of items strictly smaller than k .
	2) find_by_order(k) : K-th element in a set (counting from zero).
*/
using namespace __gnu_pbds;
using namespace std;
using LD = long double;

const int N = 5e5+1;
const int mod = 1e9+7;
const int INF = 1e18;
int row[8] = {1,1,0,-1,-1,-1,0,1};
int col[8] = {0,-1,-1,-1,0,1,1,1};

int n,q;
vector<int> segT(4*N);

bool cmp(pair<pair<int,int>,int>& A,pair<pair<int,int>,int>& B) {
	return A.ff.ss < B.ff.ss;
}

void update(int idx, int b, int e, int pos, int val) {
	if(b == e) {
		segT[idx] += val;
		return;
	}
	int mid = b+e>>1;
	if(pos <= mid)
		update(idx<<1,b,mid,pos,val);
	else
		update(idx<<1|1,mid+1,e,pos,val);
	segT[idx] = segT[idx<<1] + segT[idx<<1|1];
}

int query(int idx, int b, int e, int L, int R) {
	if(b > R or e < L)
		return 0;
	if(b >= L and e <= R)
		return segT[idx];
	int mid = b+e>>1;
	return query(idx<<1,b,mid,L,R) + query(idx<<1|1,mid+1,e,L,R);
}

void solve() {
	cin >> n >> q;
	vector<int> pos(n);
	
	for(int i=0;i<n;i++)
		cin >> pos[i];
		
	vector<pair<pair<int,int>,int>> vp(q);
	vector<int> ans(q);
	
	map<int,int> prev;
	
	for(int i=0;i<q;i++) {
		cin >> vp[i].ff.ff >> vp[i].ff.ss;
		vp[i].ff.ff--;
		vp[i].ff.ss--;
		vp[i].ss = i;
	}
	
	sort(all(vp),cmp);
	
	int j = 0;
	for(int i=0;i<n;i++) {
		
		if(prev.find(pos[i]) != prev.end()) {
			//cout << prev[pos[i]] << endl;
			update(1, 0, N-1, prev[pos[i]], -1);
		}
		
		update(1, 0, N-1, i, 1);
		
		while(j < q and vp[j].ff.ss == i) {
			ans[vp[j].ss] = query(1,0,N-1,vp[j].ff.ff,vp[j].ff.ss);
			j++;
		}
		
		prev[pos[i]] = i;
	}
	for(int i=0;i<q;i++)
		cout << ans[i] << endl;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1,i = 1;
    //cin >> t;
    while(t--) {
        //cout << "Case #" << i << ": ";
        solve();
        //i++;
    }
    return 0;
}


Measured memory_bytes: 70264
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> P;

#define y first
#define x second

const int INF = 1000000000;
const int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };

char map[1024][1024];
P start;
P goal[10];
int h, w, n;

int cheese(P s, int hp);

int main()
{
	scanf("%d %d %d", &h, &w, &n);
	for (int i = 1; i <= h; i++) scanf("%s", &map[i][1]);
	
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++){
			if (map[i][j] == 'S') start = P(i, j);
			if ('1' <= map[i][j] && map[i][j] <= '9'){
				goal[map[i][j] - '0'] = P(i, j);
			}
		}
	}
	printf("%d\n", cheese(start, 1));
}

int cheese(P s, int hp)
{
	queue<P> q;
	static int d[1024][1024];
	
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++){
			d[i][j] = INF;
		}
	}
	
	q.push(s);
	d[s.y][s.x] = 0;
	while (!q.empty()){
		P p = q.front(); q.pop();
		
		if (p == goal[hp]){
			if (hp == n) return d[p.y][p.x];
			int tmp = d[p.y][p.x];
			return tmp + cheese(p, hp + 1);
		}
		for (int i = 0; i < 4; i++){
			P np(p.y + dy[i], p.x + dx[i]);
			
			if (0 < np.y && np.y <= h && 0 < np.x && np.x <= w && map[np.y][np.x] != 'X' && d[np.y][np.x] == INF){
				q.push(np);
				d[np.y][np.x] = d[p.y][p.x] + 1;
			}
		}
	}
}

Measured memory_bytes: 6060
x,y = [int(i) for i in input().split()]
ans =[]

for i in range(x+1):
    if not ans:
        for j in range(x-i+1):
            if 10000*i + j*5000 + (x-i-j)*1000 == y:
                ans = [i,j,x-i-j]
                break
    else:
        break

if ans:
    print(ans[0],ans[1],ans[2])
else:
    print('-1 -1 -1')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

//二部グラフかぁ
const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

pair<int, int> E[400001];
int H[100001], D[100001];
bool dame[100001];
void dfs(int p, int d, int rt) {
	if (D[p]) {
		if ((d + D[p]) & 1) dame[rt] = true;
		return;
	}
	D[p] = d;
	for (int i = H[p]; i; i = E[i].second) {
		dfs(E[i].first, d + 1, rt);
	}
}

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


	int N = getint(), M = getint();
	rep(i, M) {
		int a = getint(), b = getint();
		E[i + i + 1] = mp(a, H[b]);
		H[b] = i + i + 1;
		E[i + i + 2] = mp(b, H[a]);
		H[a] = i + i + 2;
	}

	ll x = 0, y = 0, z = 0;
	rep1(i, N) {
		if (!D[i]) {
			dfs(i, 1, i);
			if (!H[i]) z++;
			else if (dame[i]) y++;
			else x++;
		}
	}
	co(x* x + (x + y) * (x + y) + 2 * N * z - z * z);

	Would you please return 0;
}

Measured memory_bytes: 6144
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
long long GCD(long long a, long long b)
{
    if (b == 0)
        return a;
    return GCD(b, a % b);
}
long long LCM(long long a, long long b)
{
    return a * b / GCD(a, b);
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    V vec(n);
    rep(i,n)cin>>vec[i];
    V dp(n, 1e18);
    rep(i,n){
        ll k=lower_bound(all(dp), vec[i])-dp.begin();
        dp[k] = vec[i];
    }
    rep(i,n){
        if(dp[i]==1e18){
            cout << i << endl;
            return 0;
        }
    }
    cout<<n<<endl;
}



Measured memory_bytes: 4416
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using mii = map<int, int>;
const int INF = 1e9;
const ll LINF = 1e18;
#define MP(a,b) make_pair((a),(b))
#define MT(...) make_tuple(__VA_ARGS__)

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

#define ALL(x) (x).begin(),(x).end()
#define IN(type,a) type a;cin >> a
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define COUT(x) cout << (x) << endl
#define DCOUT(x,n) cout << fixed << setprecision(n) << (x) << endl

int main() {
    IN(int, n);
    int c = 0;
    REPS(i, n){
        if (to_string(i).length()%2 == 1) {
            c++;
        }
    }
    COUT(c);
}




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

#define mx 500008

#define pii pair<int,int>
#define pi acos(-1.0)
#define pb push_back
#define ss second
#define ff first
typedef long long int ll;
///adjacent move
int fx[4]={0,+1,0,-1};
int fy[4]={+1,0,-1,0};
///knight
ll prime[mx];

vector<pii>v[mx];
double d(int x1,int x2,int y1,int y2)
{
    double x=(x1-x2);
    x=x*2;
    double y=(y1-y2);
    y*=2;
    return sqrt(x+y);
}
int main()
{
    int t=1;

    while(t--){
        ll n,k;
        cin>>n;
        string s="7";
        cin>>s;
        int ans=0;
        int i=0;
        int j=s.size()-1;
        while(i<j){
            if(s[i]=='W' && s[j]=='R'){
                ans++;

                i++;j--;
            }
            else if(s[i]=='R'){
                i++;
            }
            else if(s[j]=='W'){
                j--;
            }

        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 15452
#include <stdio.h>
#include <string.h>

int main(){
    int h,w;
    char c[105][105];
    char ret[210][210];
    char ch;

    scanf("%d %d", &h, &w);
    for(int i = 0; i < h; ++i){
        scanf("%s", c[i]);
    }

    int k = 0;
    for(int i = 0; i < h; ++i){
        strcpy(ret[k], c[i]);
        strcpy(ret[k+1], c[i]);
        k+=2;
    }

    for(int i = 0; i < 2*h; ++i){
        printf("%s\n", ret[i]);
    }

    return 0;
}

Measured memory_bytes: 1696
#include <iostream>
typedef long long ll;
using namespace std;
int main() {
    int n, p;
    cin >> n >> p;
    int a[100];
    bool all_even = true;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        if(a[i]%2) all_even = false;
    }
    if(all_even) {
        if(p==1) cout << '0' << endl;
        else if(p==0) {
            ll ans=1;
            for(int i=0; i<n; i++) ans *= 2;
            cout << ans << endl;
        }
    } else {
        ll ans=1;
        for(int i=0; i<n-1; i++) ans *= 2;
        cout << ans << endl;
    }
    return 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DEBUG(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/10/17  Problem: AOJ 0381 / Link: https://onlinejudge.u-aizu.ac.jp/challenges/search/volumes/0381  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL ans = 0LL;

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

	int a, b; cin >> a >> b;
	ans = abs(b - a);
	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 3172
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  998244353
#define rep(i,a,n) for(int i=a;i<n;i++)
#define N 300005
#define vi vector<int>
#define all(v) v.begin(),v.end()


signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int n;
   cin>>n;
   while(n>0)
   {
       if(n%10==7)
       {
           cout<<"Yes"<<endl;
           return 0;
       }
       n/=10;
   }
   cout<<"No"<<endl;
}


Measured memory_bytes: 3656
# -*- coding: utf-8 -*-
x, n = map(int,input().split())
p = [int(i) for i in input().split()]

tmp = 2000
ans = 2000
for i in range(-50, 105):
    if not i in p:
        if tmp > abs(x - i):
            tmp = abs(x - i)
            ans = i
print(ans)


Measured memory_bytes: 9048
#include<cstdio>
#include<cctype>

int main(){
    char ch;
    
    while(1){
        scanf("%c", &ch);
        
        if(islower(ch)){
            printf("%c", toupper(ch));
        }else if(isupper(ch)){
            printf("%c", tolower(ch));
        }else{
            printf("%c", ch);
        }
        
        if (ch =='\n'){
            break;
        }
    }
    return 0;
        
}


Measured memory_bytes: 2568