akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
typedef long long lint;

lint cng(lint a)
{
  lint y = 0;
  for(int i = 1; a > 0; i*=10){
    lint x = a % 10;
    if(x == 1)
      x = 3;
    else if(x == 2)
      x = 5;
    else if(x == 3)
      x = 7;
    y += i * x;
    a /= 10;
  }
  //cout << y << endl;
  return y;
}

bool check_753(lint a)
{
  bool f1 = false, f2 = false, f3 = false;
  while(a > 0){
    lint x = a % 10;
    //if(x == 0) return false;
    if(x == 1) f1 = true;
    if(x == 2) f2 = true;
    if(x == 3) f3 = true;
    a /= 10;
  }
  if(f1 && f2 && f3)
    return true;
  else
    return false;
}

lint adder_753(lint a)
{
  lint y = 0;
  lint c = 0;
  lint dig = 1;
  for(int i = 1; a > 0; i*=10){
    lint x = a % 10 + c;
    if(x == 4){
      c = 1;
      x = 1;
    }else{
      c = 0;
    }
    a /= 10;
    y += x * i;
    dig = i;
  }
  y += dig * 10 * c;
  return y;
}

int main(void)
{
  lint N;
  cin >> N;
  lint cnt = 0;
  for(lint i = 123; cng(i) <= N; i=adder_753(i+1)){
    if(check_753(i)){
      cnt++;
      //cout << cng(i) << endl;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define INF 10000000000
#define mod 1000000007
#define X 1000000
typedef long long int ll;
ll finv[X];
ll fac[X];
ll inv[X];
ll u(const void *a, const void *b){return *(ll*)a-*(ll*)b;}
ll d(const void *a, const void *b){return *(ll*)b-*(ll*)a;}
ll z(ll a){
  if(a<0)return -a;
  return a;
}
ll min(ll a,ll b){
  if(a>b)return b;
  return a;
}
ll max(ll a,ll b){
  if(a>b)return a;
  return b;
}
ll gcd(ll a,ll b){
  if(!b)return a;
  return gcd(b,a%b);
}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int kt(ll a){
  int sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
int ks(ll a){
  int sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
ll nCr(int n,int k){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for (int i=2;i<X;i++){
    fac[i]=fac[i-1]*i%mod;
    inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    finv[i]=finv[i-1]*inv[i]%mod;
  }
  return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
int main(void){
  int a[4];
  FOR(4)scanf("%d",&a[i]);
  PRN(a[3]==1);
  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long min = Long.MAX_VALUE;

		for (int i = 1; i <= Math.sqrt(N); i++) {
			if (N %i ==0) {
				long let = i + (N/i) - 2;
				if (min > let) {
					min = let;
				}
			}
		}
		System.out.println(min);
	}

}

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

#define print cout <<
#define printl(s) cout << s << endl;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

const ll modseed = pow(10,9) + 7;

template <typename T>
vector<T> getValues(int num){
    vector<T> values(num);
    for(int i=0;i<num;i++){
        cin >> values.at(i);
    }
    return values;
}

ll calculateMod(ll n, ll expo, ll modSeed){
  ll ret = 1;
  rep(i, expo){
    ret *= n;
    ret = ret%modSeed;
  }
  return ret;
}

int main(){
    ll N;
    cin >> N;
    auto inputs = getValues<ll>(N);
    vector<ll> steps(N,0);
    ll ans = 0;
    rep(i, N){
      if(i==0){
        continue;
      }
      ll maenohito = steps.at(i-1) + inputs.at(i-1);
      ll sub = inputs.at(i) - maenohito;
      if(sub < 0){
        steps.at(i) = -sub;
        ans += steps.at(i);
      }
    }
    printl(ans);
}


Measured memory_bytes: 6436
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    map<int,int> mp;
    for(int i = 0; i < n; i++){
        cin >> p[i];
        mp[p[i]] = i;
    }

    set<int> st;
    st.insert(mp[n]);
    ll ans = 0;
    for(int i = n-1; i > 0; i--){
        auto itr = st.insert(mp[i]);
        auto itr_org = itr;
        int l1, l2, r1, r2;
        if(itr.first == st.begin()){
            l2 = -1; l1 = -1;
        }else if(--itr.first == st.begin()){
            l2 = -1; l1 = *itr.first;
        }else{
            l1 = *itr.first;
            l2 = *(--itr.first);
        }

        itr = itr_org;
        if(itr.first == --st.end()){
            r1 = n; r2 = n;
        }else if(++itr.first == --st.end()){
            r1 = *itr.first; r2 = n;
        }else{
            r1 = *itr.first;
            r2 = *(++itr.first);
        }
        ans += ll(i)*(l1-l2)*(r1-mp[i]);
        ans += ll(i)*(r2-r1)*(mp[i]-l1);

    }


    cout << ans << endl;
    return 0;

}


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

using namespace std;
#define all(a)a.begin(),a.end()
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using V = vector<ll>;
using P = pair<ll,ll>;
using G=vector<V>;

int main()
{
   int s,w;cin >>s>>w;
   bool flg=true;
   if(s<=w)flg=false;
   if(!flg)puts("unsafe");
   else puts("safe");
    return 0;
}


Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			
			int H = sc.nextInt();
			int W = sc.nextInt();
			
				if(H == W && H == 0)break;
				
				for(int i=0;i<H;i++) {
					for(int j=0;j<W;j++) {
						
						if(i == 0 || i == H-1) {
							System.out.print("#");
						}else {
							if(j == 0 || j == W-1) {
							System.out.print("#");
							}else {
								System.out.print(".");
							}
						}
					}
					System.out.println();
				}
				System.out.println();
		}
		sc.close();

	}

}


Measured memory_bytes: 35328
n, m = map(int, input().split())

compe = []
for _ in range(n):
    a = int(input())
    compe.append(a)

vote = [0] * n
for _ in range(m):
    b = int(input())
    for i, c in enumerate(compe):
        if c <= b:
            vote[i] += 1
            break

print(vote.index(max(vote)) + 1)


Measured memory_bytes: 5616
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {n: usize, a:[usize;n]};

    let mut index = 0;
    let mut x = 1;
    let mut t = false;

    while true {
        let mut b = false;
        for i in index..n {
            if x == a[i] {
                index = i;
                x += 1;
                t = true;
                b = true;
                break;
            }
        }
        if index == n - 1 || !t || !b {
            break;
        }
    }

    if t {
        println!("{}", n - x + 1);
    } else {
        println!("-1");
    }
}


Measured memory_bytes: 4780
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        
        int[] x=new int[3];
        x[0]=sc.nextInt();
        x[1]=sc.nextInt();
        x[2]=sc.nextInt();
        
        Arrays.sort(x);
        
        int ans=0;
        
        if((x[2]*2-x[1]-x[0])%2!=0){
            x[0]++;
            x[2]++;
            ans++;
        }
        
        ans += (x[2]*2-x[1]-x[0])/2;
        System.out.println(ans);
    }
}


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

using namespace std;

#define int long long
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int,int> PI;
typedef pair<int,pair<int,int>> PII;
static const int INF=1010000000000000017LL;
static const double eps=1e-12;
static const double pi=3.14159265358979323846;
static const int dx[4]={1,-1,0,0};
static const int dy[4]={0,0,1,-1};
static const int ddx[8]={1,-1,0,0,1,1,-1,-1};
static const int ddy[8]={0,0,1,-1,1,-1,1,-1};

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

int N,K;
int A[200005];

signed main(){
    cin>>N>>K;
    for(int i=0;i<N;++i)cin>>A[i];
    for(int i=K;i<N;++i){
        if(A[i]>A[i-K])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    
}

Measured memory_bytes: 5184
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  int a[m];
  int t=0;
  for(int i=0; i<m; i++){
    cin >> a[i];
    t = t + a[i];
  }
  int ans=0;
  ans = n - t;
  if(ans<0){
    cout << "-1" << endl;
    return 0;
  }else if(ans>=0){
    cout << ans << endl;
    return 0;
  }
}


Measured memory_bytes: 3668
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

signed main()
{
    int N;
    scanf("%lld", &N);
    vector<int> v(5);

    for (int i = 0; i < 5; i++)
    {
        scanf("%lld", &v[i]);
    }

    int minele = *min_element(v.begin(), v.end());

    int ans = N % minele == 0 ? N / minele + 4 : N / minele + 5;
    printf("%lld\n", ans);
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    H, W, K = map(int, input().split())
    S = [tuple(map(int, list(input()))) for _ in range(H)]

    ans = 10 ** 9
    for bit in range(1 << (H-1)):
        canSolve = True
        order = [0] * (H + 1)
        tmp_ans = 0
        for i in range(H):
            if bit & 1 << i:
                order[i+1] = order[i] + 1
                tmp_ans += 1
            else:
                order[i+1] = order[i]
        sum_block = [0] * (H + 1)
        for w in range(W):
            one_block = [0] * (H + 1)
            overK = False
            for h in range(H):
                h_index = order[h]
                one_block[h_index] += S[h][w]
                sum_block[h_index] += S[h][w]
                if one_block[h_index] > K:
                    canSolve = False
                if sum_block[h_index] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                tmp_ans += 1
                sum_block = one_block
            if tmp_ans >= ans:
                canSolve = False
                break
        if canSolve:
            ans = tmp_ans
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 41820
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#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> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;


int main() {
    int n;
    cin >> n;
    vi p(n);
    rep(i, n) cin >> p[i];
    
    int minv = p[0];
    int ans = 1;
    for (int i=1;i<n;i++){
        if (minv >= p[i]){
            ans ++;
            minv = p[i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<vector>
#define ll long long int
using namespace std;
int n, m;
int g[100][100]={0};
int visit[100]={0};
int v_num=0;

void dfs(int v) {
  visit[v]=1;
  v_num++;
  for(int i=1; i<=n; i++) {
    if(g[v][i]==1 and visit[i]==0) {
      dfs(i);
    }
  }
}

int main(void) {
  vector< pair<int, int> >e;
  int x, y;
  int ans=0;
  cin>>n>>m;
  
  for(int i=0; i<m; i++) {
    cin>>x>>y;
    e.push_back({x, y});
    g[x][y]=1;
    g[y][x]=1;
  }
  for(auto it=e.begin(); it!=e.end(); it++) {
    x=(*it).first;
    y=(*it).second;
    g[x][y]=0;
    g[y][x]=0;
    fill(visit, visit+n+1, 0);
    v_num=0;
    dfs(1);
    g[x][y]=1;
    g[y][x]=1;
    if(n!=v_num) ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
var ans = "Yes"
var (preT, preX, preY) = (0, 0, 0)
for _ in 0..<Int(readLine()!)! {
  let input = readLine()!.characters.split(" ").map{Int(String($0))!}
  let (t, x, y) = (input[0], input[1], input[2])
  let (dt, dx, dy) = (t - preT, abs(x - preX), abs(y - preY))
  let tmp = dt - (dx + dy)
  if tmp < 0 || tmp % 2 > 0 {
    ans = "No"
  }
  (preT, preX, preY) = (t, x, y)
}
print(ans)

Measured memory_bytes: 4080
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>

#define rep(i, n) for (int i = 0; i < (n); ++i)

typedef long long ll;

using namespace std;

int main() {
    int n;
    cin >> n;
    int p[n];
    rep(i, n) cin >> p[i];

    int ans = 0;
    rep(i, n-2) {
        if ((p[i] < p[i+1] && p[i+1] <= p[i+2]) 
             || (p[i] >= p[i+1] && p[i+1] > p[i+2])) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
a,b,c,x,y = map(int,input().split())
ans = 0
if (a+b) >= (2*c):
  ans += 2*c*min(x,y)
  if (x > y) and (a > 2*c):
    ans += 2*c*(x-y)
  elif (x > y) and (a <= 2*c):
    ans += a*(x-y)
  elif (x < y) and (b > 2*c):
    ans += 2*c*(y-x)
  elif (x < y) and (b <= 2*c):
    ans += b*(y-x)
else:
  ans += a*x+b*y

print(ans)

Measured memory_bytes: 3064
_,*a=$<.map{|x|x.split.map(&:to_i).sort}
n=_[0]
p [0,1].map{|k|
  a[1].map{|i|a[k*2].bsearch_index{|x|x>~-k+i}||n}
}.transpose.map{|x,y|x*(n-y)}.inject(:+)

Measured memory_bytes: 29876
using System;
// using System.Collections.Generic;
// using System.Globalization;
// using System.IO;
// using System.Linq;
// using System.Text;
// using System.Text.RegularExpressions

class Program
{
    static void Main()
    {
        int r = int.Parse(Console.ReadLine());
        Console.WriteLine(3 * Math.Pow(r, 2));
        return;
    }
}

Measured memory_bytes: 27592
#include<iostream>
using namespace std;
int main(){
    int n,i=0,f;
    char s[101];
    cin>>n;
    cin>>s;
    if(n%2==0){
        for(i=0;i<n/2;i++){
            if(s[i]==s[i+n/2]){
                f=1;
            }
            else{
                f=0;
                break;
            }
        }
        if(f==1){
            cout<<"Yes";
        }
        else cout<<"No";
    }
    else cout<<"No";
    return 0;
}

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

int main(int argc,char** argv){
  int A,B,C,X,Y;
  int num_a=0;
  int num_b=0;
  int num_c=0;
  cin >> A >> B >> C >> X >> Y;
  if(C*2 < A + B){
    num_c = 2 * min(X,Y);
    if(X>Y){
      if(A < C * 2){
        num_a = X-Y;
      }else{
        num_c += 2 * (X - Y);
      }
    }
    if(Y>X){
      if(B < C * 2){
	num_b = Y-X;
      }else{
	num_c += 2 * (Y - X);
      }
    }
  }else{
    num_a = X;
    num_b = Y;
  }
  cout << num_a * A + num_b * B + num_c * C << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define X first
#define Y second

using namespace std;

const double EPS = 1e-9;

struct Rect{
	double l, t, r, b;
	bool contain(const Rect &rc){
		return l - EPS < rc.l &&
			t - EPS < rc.t &&
			r + EPS > rc.r &&
			b + EPS > rc.b;
	}
	double S(){
		return (r - l)*(b - t);
	}
};

int n;
Rect rect[500];
double x[500], y[500];

int main(){
	cout.setf(ios::fixed);
	cout.precision(2);
	int t = 1;
	while (cin >> n, n){
		rep(i, n){
			double xx, yy, rr;
			cin >> xx >> yy >> rr;
			rect[i] = Rect{ xx - rr, yy - rr, xx + rr, yy + rr };
			x[i * 2] = xx - rr, x[i * 2 + 1] = xx + rr;
			y[i * 2] = yy - rr, y[i * 2 + 1] = yy + rr;
		}
		sort(x, x + 2 * n);
		sort(y, y + 2 * n);

		double ans = 0;
		rep(i, 2 * n - 1) rep(j, 2 * n - 1) {
			Rect r = {x[i], y[j], x[i+1], y[j+1]};
			int cnt = 0;
			rep(k, n){
				if (rect[k].contain(r)) ++cnt;
			}
			if (cnt > 0) ans += r.S();
		}
		cout << t++ << " " <<  ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1320
N = int(input())
tt = map(int, input().split())
vv = map(int, input().split())

v_now = 0
v_max = [v_now]
for t, v in reversed(list(zip(tt, vv))):
    for i in range(t * 2):
        if v_now + 0.5 <= v:
            v_now += 0.5
        else:
            v_now = min(v_now, v)
        v_max.append(v_now)
v_max = v_max[::-1]

v = 0
total = 0
for i in range(len(v_max) - 1):
    v0 = v_max[i]
    v1 = v_max[i+1]
    if v + 0.5 <= v1:
        if v < v0:
            total += (v + v + 0.5) * 0.25
            v += 0.5
        else:
            total += v * 0.5
    elif v > v1:
        total += (v + v - 0.5) * 0.25
        v -= 0.5
        assert v == v1, '%s %s'%(v,v1)
    else:
        total += v * 0.5
print(total)

Measured memory_bytes: 3756
from math import gcd
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

for ss in s:
    dp[ss] += 1

A = max(s)
pairwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False

if pairwise:
    print("pairwise coprime")
    exit()

res = s[0]
for ss in s:
    res = gcd(res, ss)
print("setwise coprime" if res == 1 else "not coprime")


Measured memory_bytes: 194560
#include <iostream>
#define llint long long int
#define MOD 1000000007

using namespace std;

/*
llint pow(llint a, llint b)
{
	if(b == 0) return 1;
	
	if(b % 2){
		a = ((a % MOD) * (pow(a, b - 1) % MOD)) % MOD;
	}
	else{
		a = ((pow(a, b / 2) % MOD) * (pow(a, b / 2) % MOD)) % MOD;
	}
	return a;
}
*/

int N;
string S[2];

int main(void)
{
	cin >> N;
	cin >> S[0] >> S[1];
	
	int prev = -1;
	llint ans = 1;
	
	for(int i = 0; i < N; i++){
		
		if(S[0][i] == S[1][i]){
			if(prev == -1) ans *= 3;
			if(prev == 0) ans *= 2;
			prev = 0;
		}
		else{
			if(prev == -1) ans *= 6;
			if(prev == 0) ans *= 2;
			if(prev == 1) ans *= 3;
			prev = 1;
			i++;
		}
		
		ans %= MOD;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{			
	char s[101];
	int indc=-1,indf=-1,i;
	scanf("%s",s);
	for(i=0;i<strlen(s);i++){
		if(s[i]=='C'&&indc==-1)indc=i;
		if(s[i]=='F')indf=i;
	}
	if(indf!=-1&&indc!=-1&&indc<indf)printf("Yes");
	else printf("No");
	return 0;
}   


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

using namespace std;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<int> vi(N);
    for(int i = 0; i < N; ++i){
        cin >> vi[i];
    }

    if (N <= 1){
        cout << 0 << "\n";
        return 0;
    }

    /*
    vector<int> dp(N);

    dp[0] = 0, dp[1] = abs(vi[1] - vi[0]);

    for(int i = 2; i < N ; ++i){

        dp[i] = min (abs(vi[i] - vi[i-1]) +  dp[i-1], abs(vi[i] - vi[i-2])+ dp[i-2]);
    }

    */
    int d1 = 0, d2 = abs(vi[1] - vi[0]), d3 = 0;

    for(int i = 2; i < N;  ++i){
        d3 = min (abs(vi[i] - vi[i-1]) + d2 , abs(vi[i] - vi[i-2]) + d1);
        d1 = d2 ;
        d2 = d3;
    }

    cout << d2 << "\n";

    
    
    
 
    
    return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  vector<int> P(M), Y(M);
  for (int i = 0; i < M; i++) {
    cin >> P[i] >> Y[i];
  }

  map<int, int> cnt;
  vector<int> idx(M);
  for (int i = 0; i < M; i++) {
    idx[i] = i;
  }
  sort(idx.begin(), idx.end(), [&](int a, int b) { return Y[a] < Y[b]; });

  vector<pair<int, int>> res(M);
  for (auto i : idx) {
    res[i] = make_pair(P[i], cnt[P[i]]++);
  }

  for (int i = 0; i < M; i++) {
    cout << setfill('0') << right << setw(6) << res[i].first << setw(6)
         << res[i].second + 1 << '\n';
  }
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  cout << n*n*n << endl;
  return 0;
}

Measured memory_bytes: 764
# WARN: Require mod number m is prime number
class ModComb:
    # For nCr mod m
    def __init__(self, n_max, m):
        self._n_max = n_max
        self._m = m
        self._mod_facts = [1] * (n_max+1)       # list of n! mod m
        self._mod_inv_facts = [1] * (n_max+1)   # list of inverse r! mod m

        if not m >= 3:
            raise ValueError('Require mod number m >= 3')

        # Calc n_max! mod m
        for i in range(2, n_max+1):
            self._mod_facts[i] = self._mod_facts[i-1] * i % m

        # Calc inverse r! mod m
        self._mod_inv_facts[n_max] = pow(self._mod_facts[n_max], m-2, m)
        for i in range(n_max-1, 1, -1):
            self._mod_inv_facts[i] = self._mod_inv_facts[i+1] * (i+1) % m

    def calc(self, n, r):
        # Return nCr mod m
        if n > self._n_max:
            raise Exception('n is larger than n_max')

        if r == 0:
            return 1

        m = self._m
        return self._mod_facts[n] * self._mod_inv_facts[r] * self._mod_inv_facts[n-r] % m


# n^p % mod
def modPower(mod, n, p):
    ret = 1
    for i in range(p):
        ret = ret*n % mod
    return ret


# Expected value of the number of all games when M-th non-even game occurs
def expectedGameNum(mod, C, M):
    return M*100*pow(100-C, mod-2, mod) % mod


# Probability of ending game when M-th non-even game occurs
def probEndGame(mod, modcomb, A, B, M, N):
    winA = modcomb.calc(M-1, N-1) * \
            (modPower(mod, A, N) * pow(modPower(mod, 100, N), mod-2, mod) % mod) * \
            (modPower(mod, B, M-N) * pow(modPower(mod, 100, M-N), mod-2, mod) % mod) % mod
    winB = modcomb.calc(M-1, N-1) * \
            (modPower(mod, B, N) * pow(modPower(mod, 100, N), mod-2, mod) % mod) * \
            (modPower(mod, A, M-N) * pow(modPower(mod, 100, M-N), mod-2, mod) % mod) % mod
    return (winA + winB) % mod

def main():
    MOD = 10**9+7
    N, A, B, C = map(int, input().split())
    N_MAX = 100000
    modcomb = ModComb(N_MAX*2, MOD)
    denomi100minusC = pow(100-C, MOD-2, MOD)
    modpowerA = [1] * (N+1)
    for i in range(1, N+1):
        modpowerA[i] = modpowerA[i-1] * A % MOD
    modpowerB = [1] * (N+1)
    for i in range(1, N+1):
        modpowerB[i] = modpowerB[i-1] * B % MOD
    modpower100 = [1] * (N+1)
    for i in range(1, N+1):
        modpower100[i] = modpower100[i-1] * 100 % MOD
    modpowerAB = [1] * (N+1)
    for i in range(1, N+1):
        modpowerAB[i] = modpowerAB[i-1] * (A+B) % MOD
    ans = 0
    for i in range(N, 2*N):
        prob_winA = modcomb.calc(i-1, N-1) * \
                (modpowerA[N] * pow(modpowerAB[N], MOD-2, MOD) % MOD) * \
                (modpowerB[i-N] * pow(modpowerAB[i-N], MOD-2, MOD) % MOD) % MOD
        prob_winB = modcomb.calc(i-1, N-1) * \
                (modpowerB[N] * pow(modpowerAB[N], MOD-2, MOD) % MOD) * \
                (modpowerA[i-N] * pow(modpowerAB[i-N], MOD-2, MOD) % MOD) % MOD
        prob_end_game = (prob_winA + prob_winB) % MOD
        ans += i*100*denomi100minusC % MOD * prob_end_game
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 36684
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

int main()
{
    int n,m,k,a,b,x,y;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;

    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>A[i];

    for(int i=1;i<=n;i++)
        mx = max(mx,A[i]);

    for(int i=1;i<=n;i++)
        if(mx==A[i])cnt++;

    if(cnt>=2){

        for(int i=1;i<=n;i++)
            cout<<mx<<"\n";
    }
    else {

        int mx1 = 0;

        for(int i=1;i<=n;i++){
            if(mx==A[i])continue;
            mx1 = max(mx1,A[i]);
        }

        for(int i=1;i<=n;i++)
            if(mx==A[i])cout<<mx1<<"\n";
            else cout<<mx<<"\n";
    }
    return 0;
}


Measured memory_bytes: 2432
K, N = map(int, input().split())
A = list(map(int, input().split()))

dis = [0] * N

for i in range(N-1):
    dis[i] = A[i+1] - A[i]
    
dis[N-1] = K - A[N-1] + A[0]

print(K-max(dis))

Measured memory_bytes: 77260
#include<iostream>
#include<utility>

using namespace std;

int bubbleSort(int *A, int n) {
	bool flag = true;
	int count=0;
	while(flag) {
		flag=false;
		for(int j=n-1; j>0; j--) {
			if(A[j]<A[j-1]) {
				swap(A[j], A[j-1]);
				flag=true;
				count++;
			}
		}
	}
	return count;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, A[100];
	cin>>n;
	for(int i=0; i<n; i++) cin>>A[i];
	int count = bubbleSort(A, n);
	cout<<A[0];
	for(int i=1; i<n; i++) cout<<' '<<A[i];
	cout<<'\n'<<count<<'\n';
	return 0;
}



Measured memory_bytes: 3192
#include <iostream>

using namespace std;

int cnt=0;

void insertionSort(int a[],int n,int g){
  for(int i=g;i<=n-1;i++){
    int v=a[i];
    int j=i-g;
    while(j>=0&&a[j]>v){
      a[j+g]=a[j];
      j=j-g;
      cnt++;
    }
    a[j+g]=v;
  }
}
void reverse(int a[],int n){
  for(int i=0;i<n/2;i++){
    int t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t;
  }
}
int main(){
  int n;
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++)
    cin >> a[i];
  int g[1000];
  g[0]=1;
  int i=0;
  while(g[i]<=n){
    g[i+1]=3*g[i]+1;
    i++;
  }
  int m=i;
  reverse(g,m);
  for(int i=0;i<m;i++)
    insertionSort(a,n,g[i]);
  cout << m << '\n';
  for(int i=0;i<m;i++){
    if(i) cout << " " << g[i];
    else cout << g[i];
  }
  cout << '\n';
  cout << cnt <<'\n';
  for(int i=0;i<n;i++)
    cout << a[i] << '\n';
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

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

const int INF = 1000000000;
const int MOD = 1000000007;
const double eps = 1e-9;

int main(int argc, char *argv[]) {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int n; cin >> n;
    int ans = 0, tmp = INF;
    rep(i, n) {
        int s; cin >> s;
        ans += s;
        if (s % 10) tmp = min (tmp, s);
    }
    if (tmp == INF) cout << 0 << endl;
    else if (ans % 10) cout << ans << endl;
    else cout << ans - tmp << endl;
    return 0;
}

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

bool check(string s){
    int l = s.length();
    bool res = true;
    // cout << l << endl;
    for(int i = 0; i <= (l - 1)/2; ++i){
        if(s[i] == s[l - 1 - i]){
           continue;
        }
        res = false;
    }    
    return res;  
}

int main() {
  string s;
  cin >> s;
  
  int n = s.length();
  
  // 前半
  string s_b = s.substr(0, (n - 1)/2);
    
  // 後半
  string s_a = s.substr((n + 1)/2);
    
  if(check(s_a) && check(s_b) && (s_a == s_b)){
      cout << "Yes" << endl;
  }else{
      cout << "No" << endl;
  }
  
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int n;
	int count = 0;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int num = i, digit = 0;
		while (num != 0) {
			num /= 10;
			digit++;
		}
		if (digit % 2 == 1) count++;
	}
	
	cout << count << endl;

	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i-1 for i in range(N)]
B.sort()

ave1,ave2 = B[N//2],B[N//2-1]
ans1,ans2 = 0,0
for i in range(N):
    ans1 += abs(B[i]-ave1)
    ans2 += abs(B[i]-ave2)
print(ans1)

Measured memory_bytes: 26020
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep2(i, a, b) for(int i = (a); i <= (b); ++i)
#define ll long long

main() {
    while(1) {
        ll n, x, y;
        cin >> n >> x >> y;
        if(!n) return 0;
        string s = "LR";
        x--, y--;
        vector<int> v(n);
        rep(i, n) {
            v[i] = (x < (1LL << (n - 1 - i)));
            if(v[i])
                x = x ^ ((1LL << (n - 1 - i)) - 1);
            else
                x -= 1LL << (n - 1 - i);
        }
        for(int i = n - 1; i + 1; --i) {
            int t = (y < (1LL << i) ^ v[i]) > 0;
            if(y >= (1LL << i)) {
                y ^= 1LL << i;
                if(t) y ^= (1LL << i) - 1;
            } else if(!t)
                y ^= (1LL << i) - 1;
            cout << s[t];
        }
        cout << endl;
    }
}


Measured memory_bytes: 3020
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long long INF = 1e18;
//const ll mod = 1000000007;
struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<ll> Size;
    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1); Size.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0, Size[i] = 1;
    }

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

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

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        Size[x] += Size[y];
        return true;
    }

    ll size(int x){
        return Size[root(x)];
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;
    UnionFind uni(N);
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        uni.merge(a, b);
    }
    ll ans = 0;
    for(ll i = 0; i < N; i++) {
        chmax(ans, uni.size(i));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6364
import java.util.*;
import java.text.DecimalFormat;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		Random rn = new Random();
		DecimalFormat df = new DecimalFormat("#,###.##");

		int N = sc.nextInt();
		sc.nextLine();
		String S = sc.nextLine(), answer = "No";

		if(S.substring(0,(N/2)).equals(S.substring(N/2)))
			answer = "Yes";


		System.out.println(answer);
	}
}

Measured memory_bytes: 21588
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("src/xxxyyyy/input.txt"));
			System.setOut(new PrintStream(new FileOutputStream("src/xxxyyyy/result.txt")));
		} catch (FileNotFoundException e) {
		}
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String s = sc.next();
			int array[] = new int[10];
			for(int i = 0; i < 10; i++)
			{
				array[i] = s.charAt(i) - '0';
			}
			for(int row = 1; row < 10; row++) {
				int next[] = new int[10];
				for(int i = 0; i < 10 - row; i++)
				{
					next[i] = (array[i] + array[i + 1]) % 10;
				}
				array = next;
			}
			System.out.println(array[0]);
		}
	}
	
	void debug(Object... os) {
		System.err.println(deepToString(os));
	}
}

Measured memory_bytes: 11000
/// Kazuki Hoshino


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define rep1(i, a, b) for(int i =a; i >=b; i--)
#define f first
#define ss second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
//#define endl '\n'
typedef tree<
int,
null_type,less<int>,
rb_tree_tag,tree_order_statistics_node_update>
ordered_set;


int n,a[202020],t=1,ans;
multiset<int> s;

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

//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);


cin >> n;
for(int i=1;i<n+1;i++){
       cin >> a[i];
       s.insert(a[i]);
}
sort(a+1,a+n+1);
for(int i=n;i>=1;i--){
       bool flag = false;
       if(s.find(a[i])==s.end())continue;
       auto itt = s.lower_bound(a[i]);
       s.erase(itt);
       for(int j=40;j>=0;j--){
              int k = (t<<j);
              //cout << k << " " << i << endl;
              auto it=s.lower_bound(k - a[i]);
              if(it!=s.end() && *it == k-a[i] ){
                     ans++;
                //     cout << a[i] << endl;
                     s.erase(it);
                     flag = true;
                     break;
              }
       }
       if(!flag)s.insert(*itt);
}

cout << ans << endl;



return 0;}
///....


Measured memory_bytes: 11264
// inputに入力データ全体が入る
function Main(input) {
	input = input.split(" "); // 1行目がinput[0], 2行目がinput[1], …に入る
	// ここに処理を書く
	var N = input[0];
    var A = input[1];
    var B = input[2];
    
    var tax = B;
    var train = N * A;

    var result = train <= tax ? train : tax;
	
	// console.logは標準出力に1行出力します (自動的に最後に改行が入ります)
    // console.log(result);
    console.log(result);
}


// ※この行以降は編集しない (標準入力から一度に読み込みMainを呼び出します)
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
#include <iostream>
#include <math.h>

using namespace std;

int main() {
  
  int n;
  cin >> n;
  int arr[n];
  for(int i = 0; i<n; i++){
    cin >> arr[i];
  }
  int sum = 0;
  for(int j = 0; j < n; j++){
    for(int k = j+1; k<n; k++){
      sum = sum + arr[j]*arr[k];
      //cout << sum << "\n";
    }
  }
  cout << sum;
}

Measured memory_bytes: 3152
#include <iostream>
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ll n,suff[200100],cnt[200100],suffval[200100],a[200100];

int main()
{
    ll m;
    cin >> n >> m;
    for(ll i = 0; i<n; i++)  cin >> a[i],cnt[a[i]]++;
    sort(a, a + n);
    for(ll i = 1e5; i>=0; i--)  suff[i] = cnt[i] + suff[i + 1];
    for(ll i = 1e5; i>=0; i--)  suffval[i] = suffval[i + 1] + (cnt[i] * i);
    ll Start = 0, End = 2e5 , canSum = 0;
    while(Start <= End){
        ll mid = (Start + End)/2;
        ll needSum = mid + 1;
        ll Res = 0;
        for(ll i = 0;i<n;i++){
          Res+=(suff[max((ll)0 , needSum - a[i])] - (needSum - a[i] <= a[i] ? cnt[a[i]] : 0));
          if(needSum - a[i] <= a[i])  Res+=cnt[a[i]];
        }
        if(Res <= m)  canSum = mid , End = mid - 1;
        else  Start = mid + 1;
    }
    ll Ans = 0;
    canSum++;
    for(ll i = 0;i<n;i++){
        Ans+=suffval[max((ll)0 , canSum - a[i])];
        ll Ways = 0;
        Ways+=(suff[max((ll)0 , canSum - a[i])] - (canSum - a[i] <= a[i] ? cnt[a[i]] : 0));
        if(canSum - a[i] <= a[i])  Ways+=cnt[a[i]];
        m-=Ways;
        Ans+=a[i] * Ways;
    }
    cout << Ans + m * (canSum - 1);
    return 0;
}


Measured memory_bytes: 5632
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	ll n;
	cin>>n;
	string s;
	set<string>a;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		a.insert(s);
	}
	cout<<a.size()<<endl;
}


Measured memory_bytes: 19120
N, Y = map(int,input().split())
A = B = C = -1
for a in range(N+1):
    for b in range(N+1-a):
        c=N-a-b
        if 10000*a+5000*b+1000*c==Y:
            A = a
            B = b
            C = c
            
print(A, B, C)

Measured memory_bytes: 3060
from collections import defaultdict

N = int(input())
dic = defaultdict(int)

for i in range(1, N+1):
    num_str = str(i)
    if int(num_str[-1]) == 0:
        continue
    else:
        dic[(int(num_str[0]), int(num_str[-1]))] += 1

ans = 0
for i in range(1,10):
    for j in range(1,10):
        if (i,j) in dic and (j,i) in dic:
            ans += dic[(i,j)] * dic[(j,i)]
print(ans)


Measured memory_bytes: 3316
import Control.Applicative
import Control.Monad
import Data.List

main = do
  n <- readLn
  as <- replicateM n getLine
  m <- readLn
  bs <- replicateM m getLine
  print $ solve as bs

solve :: [String] -> [String] -> Int
solve as bs = let
  cs = as \\ bs
  in if null cs then 0 else maximum $ map length $ group $ sort cs


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

int main() {
  long long a,b,k;
  cin>>a>>b>>k;
  
  if(a >= k)
    cout<<(a-k)<<" "<<b<<endl;
  else if(b >= k-a)
    cout<<0<<" "<<(b - (k-a))<<endl;
  else
    cout<<0<<" "<<0<<endl;
  
  return 0;
}


Measured memory_bytes: 256
use std::fs::File;
use std::io::{stdout, BufWriter, Read, Write};
use std::thread;

fn main() {
    thread::Builder::new()
        .stack_size(32 * 1024 * 1024) // 32MB
        .spawn(run)
        .unwrap()
        .join()
        .unwrap();
}

/// ローカル環境なら _in.txt から入力を受ける
fn read_input() -> String {
    let stdin = std::io::stdin();
    let mut s = String::new();
    match option_env!("LOCAL") {
        Some(_) => File::open("src/_in.txt")
            .expect("File not found")
            .read_to_string(&mut s)
            .unwrap(),
        None => stdin.lock().read_to_string(&mut s).unwrap(),
    };
    s
}

fn run() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    let input = read_input();
    let mut input = input.split_whitespace();

    let k: i64 = input.next().unwrap().parse().unwrap();
    let x: i64 = input.next().unwrap().parse().unwrap();

    let ret: String = ((x - k + 1)..(x + k))
        .map(|i| i.to_string())
        .collect::<Vec<String>>()
        .join(" ");

    writeln!(out, "{}", ret).ok();
}


Measured memory_bytes: 8572
#define onlycc ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;

ll a, b, c, d;

int main()
{
    onlycc;
    cin >> a >> b >> c >> d;

    ll m = a*c;
    m = max(m, a*d);
    m = max(m, b*c);
    m = max(m, b*d);

    cout << m;

    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int fa[1000100],st[1000100],a[1000100],js[1000100],tim;
bool vis[1000100];
vector <int> des[1000100];
void dfs(int s)
{
	for (int k=0;k<des[s].size();k++) if (!vis[des[s][k]]) dfs(des[s][k]);
	tim++;
	for (int k=0;k<des[s].size();k++) if (!vis[des[s][k]]) js[a[des[s][k]]]=tim;
	for (a[s]=0;;a[s]++) if (js[a[s]]!=tim) break;
}
int main()
{
	int n,top=0;scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d",&fa[i]);des[fa[i]].push_back(i);}
	int now=1;while (!vis[now]) {st[++top]=now;vis[now]=true;now=fa[now];}
	int p=1;while (st[p]!=now) p++;st[top+1]=st[p];
	if ((top-p)&1) {printf("POSSIBLE\n");return 0;}
	memset(vis,0,sizeof(vis));
	for (int i=p;i<=top;i++) vis[st[i]]=true;
	for (int i=p;i<=top;i++) dfs(st[i]);
	for (int i=p;i<=top;i++) if (a[st[i]]!=a[st[i+1]]) {printf("POSSIBLE\n");return 0;}
	printf("IMPOSSIBLE\n");
}

Measured memory_bytes: 38272
N = int(input())

abc = [[0, 0, 0]]
for _ in range(N):
    a, b, c = map(int, input().split())
    abc.append([a, b, c])

dp = [[0 for _ in range(3)] for _ in range(N + 1)]

# 0=A,1=B, 2=C
for i in range(1, N + 1):
    if i == 1:
        dp[i][0] = abc[1][0]
        dp[i][1] = abc[1][1]
        dp[i][2] = abc[1][2]
    else:
        dp[i][0] = max(dp[i - 1][1] + abc[i][0], dp[i - 1][2] + abc[i][0])
        dp[i][1] = max(dp[i - 1][0] + abc[i][1], dp[i - 1][2] + abc[i][1])
        dp[i][2] = max(dp[i - 1][0] + abc[i][2], dp[i - 1][1] + abc[i][2])

print(max(dp[-1]))


Measured memory_bytes: 101540
#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<iomanip>
#define BUG puts("no bug")
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define PER(a,b,c) for(int a=b;a>=c;a--)
#define lb(a) (a&(-a))
#define pp (p<<1)
#define ppp (p<<1|1)
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
using namespace std;
const int MAXN=1e6+5;
int n,m,t;
int v[MAXN];
int vis[MAXN];
int main(){
    cin>>n>>m;
    int ans=0;
    REP(i,1,n){
        cin>>v[i];
        vis[i]=1;
    }
    REP(i,1,m){
        int a,b;
        cin>>a>>b;
        if(v[a]>=v[b])vis[b]=0;
        if(v[a]<=v[b])vis[a]=0;
    }
    REP(i,1,n){
        if(vis[i])ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 3976
h,w = map(int,input().split())
raw = []
for _ in range(h):
  raw.append(input())
ans = [[0 for _ in range(w)] for _ in range(h)]
#print(raw)
#print(ans)
for x in range(h):
  tmp = 0
  for y in range(w):
    if raw[x][y] == '.':
      tmp += 1
    else:
      for j in range(tmp):
        ans[x][y-j-1] += tmp
      tmp = 0
  for j in range(tmp):
    ans[x][y-j] += tmp
for y in range(w):
  tmp = 0
  for x in range(h):
    if raw[x][y] == '.':
      tmp += 1
    else:
      for i in range(tmp):
        ans[x-i-1][y] += tmp
      tmp = 0
  for i in range(tmp):
    ans[x-i-1][y] += tmp
can = []
for x in range(h):
  can.append(max(ans[x]))
print(max(can)-1)

Measured memory_bytes: 100696
import java.util.*
     
    fun main(args: Array<String>) {
        val sc = Scanner(System.`in`)
        val k = sc.nextLong()
        val n = sc.nextLong()
        val a = (0 until n).map { sc.next().toLong() }
        println(problem160c(k, n, a))
    }
     
    fun problem160c(k: Long, n: Long, a: List<Long>): Long {
        var max = a[0]
        var maxI = -1
        for (i in 1 until a.size) {
            val tmp = a[i] - a[i - 1]
            if (max < tmp) maxI = i
            max = Math.max(max, tmp)
        }
        if (max <= k - a.last()+a[0]) maxI = -1
        if (maxI == -1) {
            return a.last() - a[0]
        }
        return a[maxI - 1] + k - a[maxI]
    }

Measured memory_bytes: 56360
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

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

int main(){
    std::ios::sync_with_stdio(false);
    string s;
    cin >> s;
    cout << (s == "ABC" ? "ARC" : "ABC") << endl;
}

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

int main(){

	long long  i,j,k,n,c=0;
	cin>>n;
	long long  a[n];
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	for(i=1;i<n;i++){
		if(a[i]<a[i-1]){
			c += a[i-1]-a[i];
			a[i] = a[i-1]; 
		}
	}
	cout<<c;
}

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

using namespace std;

int xd(string s)
{
    for (int i=0; i<s.size(); ++i)
        if (s[i]!=s[s.size()-i-1]) return(0);
    return(1);
}

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    string x1="", x2="";
    for (int i=0; i<=(n-1)/2-1; ++i) x1+=s[i];
    for (int i=(n+3)/2-1; i<n; ++i) x2+=s[i];
    if (xd(s) && xd(x1) && xd(x2)) cout << "Yes"; else cout << "No";
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<math.h>
#include<utility>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >>c;
    int res = 0;

    for(int i = a; i<=b;i++){
        if(c%i == 0) res++;
    }
    cout << res << endl;
}


Measured memory_bytes: 3100
s=input()

tmp1 = ''
tmp2 = ''
for i in range(len(s)):
  if i % 2 == 0:
    tmp1 += '0'
    tmp2 += '1'
  else:
    tmp1 += '1'
    tmp2 += '0'

diff_tmp1 = 0
diff_tmp2 = 0
for i in range(len(s)):
  if tmp1[i] != s[i]:
    diff_tmp1 += 1
  elif tmp2[i] != s[i]:
    diff_tmp2 += 1
print(min(diff_tmp1,diff_tmp2))

Measured memory_bytes: 9272
#include <bits/stdc++.h>
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
#define Maxn 1000000 + 10
using namespace std;
int N;
string S;
int result=0;
int solve(int t)
{
    char o=S[t];
    while (t<N)
    {
        t++;
        if(S[t]!=o)
        {
            /* cout<<t<<" "<<S[t]<<endl; */
            result+=1;
            return t;
        }
    }  
    return t;
}
int main()
{
    cin>>N;
    cin>>S;
    int len=0;
    while (len<N)
    {
        len=solve(len);
    }
    
    cout<<result<<endl;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    n--;
    for(int i = n; i >= 0; i--){
        ll r = a + i * d - (n - i) * c;
        ll l = r - (d - c) * n;
        if(b >= l && b <= r){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rpd(i,a,b) for(register int i=a;i>=b;--i)
#define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
typedef long long ll;
const int N=5e5+5;
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;int a[N];string s;ll ans;
ll work(int k){return 1LL*k*(k+1)/2LL;}
int main(){
	cin>>s;s=s+' ';int now=0;
	for(int i=0;s[i+1];i+=1){
		if(s[i]!=s[i+1]){
			a[++m]=i-now+1;
			now=i+1;
		}
	}
	if(s[0]=='>'){ans+=work(a[1]);rep(i,1,m-1)a[i]=a[i+1];m-=1;}
	rep(i,1,m/2){
		ans+=work(a[i*2-1]-1);
		ans+=work(a[i*2]-1);
		ans+=max(a[i*2-1],a[i*2]);
	}
	if(m%2==1)ans+=work(a[m]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1816
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        long H = long.Parse(ReadLine());
        int n = 0;
        while (H > 0)
        {
            H /= 2;
            n++;
        }

        long ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans = ans * 2 + 1;
        }
        WriteLine(ans);
    }
}


Measured memory_bytes: 27520
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,N) for(int i=0;i<N;i++)

long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;

int main(){

int N;
cin>>N;



bool exist[26]={};
int ans=0;
rep(i,N){
    char c;
    cin>>c;
    if(!exist[c-'A']){
        ans++;
        exist[c-'A']=true;
    }
}
if(ans==3){
    cout<<"Three"<<endl;
}
else{
    cout<<"Four"<<endl;
}
 return 0;
}
/*
6
G W Y P Y W

Four

9
G W W G P W P G G

Three

8
P Y W G Y W Y Y

Four
*/

Measured memory_bytes: 256